Gurobi求解器使用实例

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

工程上的算法问题

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

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

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

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

求解器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求解器包含哪些算法