首页 文章详情

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

程序猿声 | 2868 2020-11-26 17:29 0 0 0
UniSMS (合一短信)


程序猿声

代码黑科技的分享区

 

一、前言

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

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

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

二、模型集合定义

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

2.1 读取数据

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

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

2.2 定义集合

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

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

然后你需要在程序中把这些集合给定义好了,然后把相应的数据填充进去,比如为所有节点的集合,为所有车辆集合,那么就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中,一个决策变量是一个对象来的,首先我们需要定义决策变量的数组,并分配数组的空间,比如的:

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(01, IloNumVarType.Int, "x["+i+"]["+j+"]["+k+"]");
        }
    }
}

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

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

模型中另一个决策变量类似,我就不写啦。

3.2 CPLEX的表达式

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

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

IloNumExpr expr = this.cplex.numExpr();

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

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

那为什么没有除呢?因为除是可以通过转换变成乘的!比如可以转换成,没毛病吧~

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

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

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

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,b类型的不同,这几个函数同样重载了很多版本,你写addGe(IloNumExpr, double)、addGe(IloNumExpr, IloNumExpr)、addGe(double, IloNumExpr)都是可以的。我放一个官方的介绍吧:

现在,我们来看看一个example,演示下如何添加约束(3.5):

首先,从哪着手呢?从右边开始:对于任意的,任意的,都要满足左边那个等式。两个循环是没跑了,然后在循环的最内层,把相关表达式给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是建立在一个清晰明了的模型基础之上的,如果你一开始的模型就设置得乱七八糟,这个过程写起来是很痛苦的。毕竟你要边写代码边修正模型,很可能写着写着就变成了一坨。。。

四、CPLEX求解

上面的模型建立完成以后,就可以调用solve()函数进行求解了,如果返回true,那么就找到了可行解(是的吧?我也不太清楚,可以去查查)。否则就是不可行解。

求解完成以后,获取一个变量的值可以采用CPLEX的getValue()函数,参数是你new出来的决策变量。

不过求解得到结果以后,是需要最好手动或者写个函数验算下,确保得到的解满足了所有约束。以及得到的目标值也是正确的。

总的来说,CPLEX已经为我们封装好了很多东西,大部分只需要动动手指就可以直接使用了。少部分可能需要查查库什么的,但是基本的时候已经非常简单了。最后,贴上两篇文章,大家可能会比较感兴趣,小编也建议大家结合起来看,效果会更好哦:

CPLEX出现'q1' is not convex?

干货|十分钟快速掌握CPLEX求解VRPTW数学模型(附JAVA代码及CPLEX安装流程)

快点个赞关注我们。获取更多精彩内容吧~大家帮忙点个在看,让更多小伙伴知道吧~


推荐阅读:

干货 | 想学习优化算法,不知从何学起?

干货 | 运筹学从何学起?如何快速入门运筹学算法?

干货 | 学习算法,你需要掌握这些编程基础(包含JAVA和C++)

干货 | 算法学习必备诀窍:算法可视化解密

干货 | 模拟退火、禁忌搜索、迭代局部搜索求解TSP问题Python代码分享

记得点个在看支持下哦~
good-icon 0
favorite-icon 0
收藏
回复数量: 0
    暂无评论~~
    Ctrl+Enter