手把手教你用CPLEX求解一个数学模型（Java版）

短短的路走走停停

发布于 2020-12-03 11:27:15

8.2K1

发布于 2020-12-03 11:27:15

文章被收录于专栏：程序猿声

程序猿声

代码黑科技的分享区

一、前言

小编有个小伙伴，隔三差五就过来跟我说：这个模型CPLEX怎么写呢？我说我不是给你讲过好多次？他说CPLEX太复杂了，俺没学过学不会呢。其实对于很多刚入行的小伙伴来说，CPLEX算不上友好，就连学习资料都不知道去哪里看，不像Excel或者Word，百度一下出来好多资料。

其实吧，这玩意儿并没有大家想的那么难，尤其是简单使用CPLEX求解一个模型的话，用来用去都是那几个函数而已。下面小编来给大家好好理一下，看完相信你也能用CPLEX跑一下论文上的模型啦。

当然啦，为了方便小编还是选择大家熟悉的Java平台，用Python也是可以的，处理数据可能还更方便。但是我们一般都是用Java写的算法，因此就统一平台啦。我们今天以一个最经典的VRPTW arc-flow model为例，手把手给大家演示下，CPLEX其实并不是那么的难用。

二、模型集合定义

运行一个模型之前，首先要定义模型中用到的一些参数和集合，如果这些都没有，是无从谈起的。因此没有的话第一步是要先生成这些数据哦。

2.1 读取数据

首先，你需要在程序中定义相关的变量（通常的做法是写一个instance的类，把算例的数据读进来，放到成员变量上。）比如：

至于你怎么定义怎么写都无所谓啦，反正你知道这些数据对应模型的哪些参数就可以啦。

2.2 定义集合

其实小编发现，大家之所以觉得写模型难，还有一个原因就是自己建模的时候纯粹瞎搞。很多集合啊，参数啊，范围啊都没有想清楚，到写代码的时候就各种凌乱了。。。

好了回到我们的正题，刚刚读入了算例。接下来我们需要定义模型中需要用到的集合，这些集合是哪些集合呢？就是我指出来的这些：

然后你需要在程序中把这些集合给定义好了，然后把相应的数据填充进去，比如

\mathscr{N}

为所有节点的集合，

\mathscr{V}

为所有车辆集合，那么就for一下填充就好啦：

for(i = 0; i < inst.nbCust + 2; ++i){
   this.N.add(i);
}

for(i = 0; i < inst.nbVeh; ++i){
    this.K.add(i);
}

当然了，在程序中不用定义这些集合也能实现我们的模型，这样做只是为了让程序更清晰，不至于到后面杂乱无章，debug起来也无从下手。

三、CPLEX建模

做完数据的定义，基本上就成功50%了。就像追女孩纸一样，当你喜欢她的时候就成功了50%，当她再喜欢你的时候，就100%成功了。现在我们就来完成剩下的50%。

在CPLEX中，你只需要知道以下三点，就能轻松驾驭一个数学模型啦：

决策变量定义
添加优化目标
添加约束

想想也是哦，一个数学模型无非就是由决策变量、优化目标和约束组成嘛。下面我们来一个一个讲解。

不过，在此之前，我们先new一个CPLEX的对象出来，并设置一些参数：

this.cplex = new IloCplex();
this.cplex.setParam(IloCplex.Param.Simplex.Tolerances.Optimality, 1e-9);
this.cplex.setParam(IloCplex.Param.MIP.Tolerances.MIPGap, 1e-9);
this.cplex.setParam(IloCplex.DoubleParam.TimeLimit, 3600);
this.cplex.setOut(null);

第一第二句是求解精度相关的设置。倒数第二句表示设置求解时间为3600s，比较常用。最后一句是告诉CPLEX不要输出那些乱七八糟的东西，太烦啦！

3.1 决策变量的定义

首先是模型中有哪些变量，通通得定义出来。在CPLEX的Java API中，一个决策变量是一个对象来的，首先我们需要定义决策变量的数组，并分配数组的空间，比如

x_{ijk}

的：

this.x = new IloNumVar[n+1][n+1][v];

IloNumVar这个表示它是一个num也就是数值类型的变量，就是可以为浮点数也可以为整数。这里我们只分配了数组空间，接下来还需要为里面的每个引用分配一个对象（分配了房子，再给它发媳妇！）：

//分配内存
//x 0-1变量 [n+1][n+1][v];
for(int i = 0; i < n+1; ++i){
    for(int j = 0; j < n+1; ++j){
        for(int k = 0; k < v; ++k){
            x[i][j][k] = cplex.numVar(0, 1, IloNumVarType.Int, "x["+i+"]["+j+"]["+k+"]");
        }
    }
}

其中cplex.numVar()这个函数呢就为我们new了一个数值变量的对象出来，我这里贴上官方的解释好啦：

如果你有不同类型的变量，指定下第三个参数IloNumVarType就好啦：

模型中另一个决策变量

s_{ik}

类似，我就不写啦。

3.2 CPLEX的表达式

首先来看一个概念：表达式是什么呢？呐，类似于我圈出来的这些：

开始的时候，一般需要new一条IloNumExpr类型的空表达式出来，然后慢慢去填充它：

IloNumExpr expr = this.cplex.numExpr();

创建空表达式可以通过numExpr()函数哦：

在CPLEX的JavaAPI中呢，涉及到CPLEX对象的一些表达式，是不能直接通过Java自带的+-*/进行运算的。需要通过CPLEX提供sum()、diff()、prod()函数进行加、减、乘的操作。

那为什么没有除呢？因为除是可以通过转换变成乘的！比如

a/b=c

可以转换成

a = bc

，没毛病吧~

其中，sum()、diff()、prod()这些函数在CPLEX的库中重载了很多版本，也就是说你sum(IloNumExpr, double)、sum(IloNumExpr, IloNumExpr)、sum(double, IloNumExpr)都是可以识别的，那么我就贴一个出来给大家看看就好啦：

sum()、diff()也是类似的，不过需要注意的是diff()时要注意区分是谁减去谁哦。现在表达式有了，我们来看看怎样通过sum()、diff()、prod()这些函数，实现模型中的式子。以目标那个式子为例：

\sum_{k \in K}\sum_{i \in \mathscr{N}} \sum_{j \in \mathscr{N}} c_{ij}x_{ijk}

有三个求和符号，那么肯定得来三个循环啦：

IloNumExpr objExpr = this.cplex.numExpr();
for(k : this.K){
    for(i : this.N){
        for(j : this.N){
            IloNumExpr subExpr = this.cplex.prod(c[i][j], this.x[i][j][k]);
            obj = this.cplex.sum(obj, subExpr);
        }
    }
}

可能这一句obj = this.cplex.sum(obj, subExpr);大家有点晕，其实很简单，就是obj和subExpr相加，得到一个新的表达式，再赋值给obj。那么这样就能实现累加的效果了，大部分的求和表达式都可以写成这种形式哦。

3.3 添加目标和约束

好了，知道了表达式，添加目标和约束就变得非常简单啦。首先是目标的添加，CPLEX中提供了两个函数：addMinimize()和addMaximize()分别用以添加最小化目标和最大化目标。根据自己的需要调用就好，当然这两个函数也是有很多重载的版本，我就放一个最常用的给大家看看吧：

参数就是一个IloNumExpr类型的表达式，比如可以直接把上面的objExpr给add进来，是不是很简单呢！

对于添加约束，CPLEX也提供了三个函数，我这里写成一个表格方便大家查看：

method	作用
addGe(a, b)	添加约束
addLe(a, b)	添加约束
addEq(a, b)	添加约束

a \ge b

addLe(a, b)添加约束

a \le b

addEq(a, b)添加约束

a = b

根据a，b类型的不同，这几个函数同样重载了很多版本，你写addGe(IloNumExpr, double)、addGe(IloNumExpr, IloNumExpr)、addGe(double, IloNumExpr)都是可以的。我放一个官方的介绍吧：

现在，我们来看看一个example，演示下如何添加约束（3.5）：

首先，从哪着手呢？从右边开始：对于任意的

h \in C

，任意的

k \in V

，都要满足左边那个等式。两个循环是没跑了，然后在循环的最内层，把相关表达式给addEq就好了：

for(h : this.C){
    for(k : this.V){
        //这里要开始写表达式啦
        IloNumExpr subExpr1 = this.cplex.numExpr();
        IloNumExpr subExpr2 = this.cplex.numExpr();
        for(i : this.N){
            subExpr1 = this.cplex.sum(subExpr1, this.x[i][h][k]);
            subExpr2 = this.cplex.sum(subExpr1, this.x[h][j][k]);
        }
        cplex.addEq(subExpr1, subExpr2);
    }
}

怎样，是不是很简单呢？当然了，这个easy是建立在一个清晰明了的模型基础之上的，如果你一开始的模型就设置得乱七八糟，这个过程写起来是很痛苦的。毕竟你要边写代码边修正模型，很可能写着写着就变成了一坨。。。