专栏首页程序猿声手把手教你用CPLEX求解一个数学模型(Java版)

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

程序猿声

代码黑科技的分享区

一、前言

小编有个小伙伴,隔三差五就过来跟我说:这个模型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是建立在一个清晰明了的模型基础之上的,如果你一开始的模型就设置得乱七八糟,这个过程写起来是很痛苦的。毕竟你要边写代码边修正模型,很可能写着写着就变成了一坨。。。

四、CPLEX求解

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

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

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

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

CPLEX出现'q1' is not convex?

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

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

记得点个在看支持下哦~

本文分享自微信公众号 - 程序猿声(ProgramDream),作者:邓发珩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-11-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 干货 | cplex介绍、下载和安装以及java环境配置和API简单说明

    最近学习列生成算法,需要用到优化求解器。所以打算学习一下cplex这个商业求解器。

    用户1621951
  • 【CPLEX教程03】java调用cplex求解一个TSP问题模型

    前面我们已经搭建好cplex的java环境了,相信大家已经跃跃欲试,想动手写几个模型了。今天就来拿一个TSP的问题模型来给大家演示一下吧~

    短短的路走走停停
  • 修正重发【CPLEX教程03】JAVA调用cplex求解一个TSP模型详解

    前面我们已经搭建好cplex的java环境了,详情可以看干货 | cplex介绍、下载和安装以及java环境配置和API简单说明,相信大家已经跃跃欲试,想动手写...

    短短的路走走停停
  • 干货 | 运筹学、数学规划、离散优化求解器大PK,总有一款适合你

    CPLEX 是IBM公司的一个优化引擎。软件IBM ILOG CPLEX Optimization Studio中自带该优化引擎。该软件具有执行速度快、其自带的...

    用户1621951
  • 【CPLEX教程01】Cplex介绍,下载和安装Cplex

    最近学习列生成算法,需要用到优化求解器。所以打算学习一下cplex这个商业求解器。

    短短的路走走停停
  • 【CPLEX教程02】配置Cplex的Java环境以及API说明

    因为小编一般用的C++和Java比较多,而且现在开发大型算法用这类面向对象的编程语言也方便得多。基于上面的种种考虑,加上时间和精力有限,所以就暂时只做C++和J...

    短短的路走走停停
  • 干货 | Branch and Price算法求解VRPTW问题(附JAVA代码分享)

    前两天小编刚忙完手头上的事情,闲了下来,然后顺便研究了一下Branch and Price的算法。刚好,国内目前缺少这种类型算法的介绍和代码实现,今天就给大家分...

    用户1621951
  • 运筹学教学|Berders decomposition (二)应用实例及算法实现(附源代码及详细的代码注释)

    我们在运筹学教学|Benders decomposition(一)技术介绍篇中已经介绍了Benders Decomposition的基本原理,下面为大家提供具体...

    用户1621951
  • 运筹学教学|Benders Decomposition (二)应用实例及算法实现(附源代码及详细的代码注释)

    我们在运筹学教学|Benders Decomposition(一)技术介绍篇中已经介绍了Benders Decomposition的基本原理,下面为大家提供具体...

    用户1621951

扫码关注云+社区

领取腾讯云代金券