首页>软件资讯>常见问题

常见问题

Gurobi求解器使用实例

发布时间:2024-05-07 14:05:58人气:31

对于从事工程的同学来说,求解器应该属于比较陌生的一个领域。一是工程层面要解决的算法问题本身偏少;二是工程上涉及的算法问题相对简单,还到不了要使用求解器的程度。我们项目最近刚好要进行工程算法的重构,我才了解到解决算法问题可以使用求解器,并感受到求解器解决问题不仅简单易懂,而且高效稳定。

工程上的算法问题

对于衡量工程上算法性能的指标就两个:时间复杂度和空间复杂度。现在云计算的硬件资源配置已经越来越好,空间复杂度已经不是一个问题,所以算法的性能指标主要就是时间复杂度。

为了优化算法达到更好的性能,工程上设计了各种不同的数据存储结构:数组,链表,哈希表,堆,队列,树,图等等,并基于不同的数据结构设计了不同的算法:穷举,二分法,递归,回溯,分治,深度优先,广度优先,动态规划等等。

要深入理解这些算法,并灵活运用到工作中,不是一朝一夕能够达成,至少你要把《数据结构》《算法导论》相关的书籍重新再梳理一遍,这些底层知识都是比较难啃的骨头。

求解器好像就为你打开了一扇门,不需要你再去深挖这些算法知识,它在底层把这些都进行了封装,暴露给用户简单易懂的上层应用接口,让用户面向场景编程而不是算法编程。


求解器Gurobi使用实例

下面我使用工程算法和求解器Gurobi来解决同一个算法问题(KM)。

求解器解决方案如下:

ini复制代码import gurobi.*;


import java.util.Random;


public class KM {


    public static void main(String[] args) throws GRBException {

        int orderNum = 3;

        int carNum = 2;

        double[][] orderCarMatrix = new double[orderNum][carNum];


        Random random = new Random();

        for(int orderIndex=0; orderIndex<orderNum; orderIndex++) {

            for (int carIndex=0; carIndex<carNum; carIndex++) {

                orderCarMatrix[orderIndex][carIndex] = random.nextInt(5);

                System.out.print(orderCarMatrix[orderIndex][carIndex]+" ");

            }

            System.out.println();

        }


        GRBEnv env = new GRBEnv();

        GRBModel model = new GRBModel(env);

        model.set(GRB.StringAttr.ModelName, "km");


        //定义求解器变量

        GRBVar[][] xArr = new GRBVar[orderNum][carNum];

        for(int orderIndex=0; orderIndex<orderNum; orderIndex++) {

            for (int carIndex=0; carIndex<carNum; carIndex++) {

                xArr[orderIndex][carIndex] = model.addVar(0.0, 1.0, 0.0, GRB.BINARY,"od-"+orderIndex+"-"+carIndex);

            }

        }


        //定义求解器的目标

        GRBLinExpr object = new GRBLinExpr();

        for(int orderIndex=0; orderIndex<orderNum; orderIndex++) {

            for (int carIndex=0; carIndex<carNum; carIndex++) {

                object.addTerm(orderCarMatrix[orderIndex][carIndex], xArr[orderIndex][carIndex]);

            }

        }

        model.setObjective(object, GRB.MAXIMIZE);//定义目标


        //定义求解器约束条件

        for(int orderIndex=0; orderIndex<orderNum; orderIndex++) {

            GRBLinExpr conStr1 = new GRBLinExpr();

            for (int carIndex=0; carIndex<carNum; carIndex++) {

                conStr1.addTerm(1,xArr[orderIndex][carIndex]);

            }

            model.addConstr(conStr1, GRB.LESS_EQUAL, 1.0, "order"+orderIndex); //确保一个订单只能被一个车匹配

        }



        for(int carIndex=0; carIndex<carNum; carIndex++) {

            GRBLinExpr conStr2 = new GRBLinExpr();

            for (int orderIndex=0; orderIndex<orderNum; orderIndex++) {

                conStr2.addTerm(1,xArr[orderIndex][carIndex]);

            }

            model.addConstr(conStr2, GRB.LESS_EQUAL, 1.0, "car"+carIndex); //确保一个车只能被一个订单匹配

        }


        model.optimize(); //求解


        System.out.println("Obj: " + model.get(GRB.DoubleAttr.ObjVal)); //输出目标值


        model.dispose();

        env.dispose();


    }


}


从两种解决方案对比来看:


求解器编写的代码简单、易理解

由于支持的算法较简单、两种解决方案的求解效率差不多

求解器可扩展更好,求解问题就三个步骤,定义变量、定义目标数学模型、制定约束条件,每一个步骤都可以无限扩展。


虽然求解器使用非常方便并且高效,但是费用却是相当昂贵,一般小企业可能都承受不起,基本都是按照服务器的数量进行收费的,一台服务器就得几十万。



上一条:Gurobi +Python 高效数学规划及建模实例

下一条:gurobi求解器包含哪些算法