基于CPLEX和C++语言求解优化问题的过程

蒋争明++关青苗

摘要：CPLEX 是目前世界上顶尖的求解线性规划、整数规划和某些非线性规划的软件包。它可以用 C、C++、JAVA、.NET 等多种计算机语言进行建模，考虑到C++语言的灵活性及其可扩展性，该文首先介绍CPLEX及其求解优化问题的原理，然后重点阐述如何利用CPLEX软件包编写C++程序来求解优化问题，对该问题进行讨论，具有重要的理论和实际价值。

关键词：CPLEX；优化问题

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）23-0049-02

1 概述

CPLEX是一种用于GAMS （一般代数建模系统）的求解器，用户可以将CPLEX 的优化求解器能与GAMS的高水平建模功能结合起来，CPLEX设计的理念是在最小的用户介入下快速的求解大型复杂问题。它可用于求解线性规划（Linear programming）问题、二次规划（quadratic programming）问题、二次约束规划（quadratically constrained programming）问题与混合整数规划（mixed integer programming）问题。可以处理数以百万计的约束（constraint）和变量（variable）的问题，并且由于其灵活性、高性能型和稳定性，一直备受业界人士的青睐。

开发人员只需要通过应用组件调用ILOG CPLEX算法就能实现交互式工作，从而完成数据的读写和优化问题的求解，ILOG CPLEX性能经调整后，我们就可以解决特定的问题。同时ILOG CPLEX算法在PRESOLVE算法的基础上，与它紧密集成，不需要用户整合，将大规模的问题可以转换为小规模的问题，从而缩短求解时间。而且ILOG CPLEX中每个优化器都有许多性能调整的选项，可以根据具体优化问题的需要，对相关性能进行调整。

2 ILOG CPLEX 求解原理

CPLEX求解线性规划和混合整数线性规划问题，能够处理数以百万计的变量和约束条件，开发人员通过组件库从其他编程语言调用CPLEX中的算法即可。常见的组件库包括C、C++、java、matlab和.net接。同时也可以直接使用ILOP CPLEX软件建模语言OPL CPLEX调用算法，CPLEX中的算法包括对偶单纯形算法、原始单纯算法、网络优化求解算法、闸算法和筛选算法。求解ILP问题采用的是CPLEX中的对偶单纯形法。单纯形法指的是从已知问题的可行解中通过迭代算法找出另外一个可行解，一直检查到满足最优化条件的解时为止。而对偶单纯形发指的是在满足对偶条件的前提下，通过迭代逐步找到求解原始问题的最优解。在每次迭代的过程中，始终要保持原始解的对偶可行性。

与其他纯线性规划相比，求解纯整数与混合整数规划问题需要更多的数学计算。就算是求解较少整数规划模型也需要耗费大量的时间来求解。对于只要有整数求解的问题，CPLEX通常采用分枝切割算法，即求解一系列LP子问题，求解MIP问题需要将问题分解为许多子问题，即使小型的MIP问题也需要大量的计算。

在求解线性规划问题时，需要大量的内存空间，即使CPLEX的内存管理非常有效，但是求解规模大的LP问题，内存不足仍然是需要考虑的问题之一。针对内存不足现象，CPLEX提供两种方法来解决，第一种是通过CPLEX自动调整，但是调整后将影响到计算的性能。自动调节是通过对可行解进行松弛，它是指查找器通过不协调约束来识别产生不可行的解，然后通过进一步执行纠正模型，继续运行并得到结果。为了实现这个目的可以采用显式松弛变量和其他模型结构建模型。具体的实现过程是通过FEASOPT选项，CPLEX接收一个不可行模型，并用最小化加权罚函数的方式选择性地松弛边界和约束，实质上是通过最小化的变化来达到结果的可行。另一种方法是增加因子重新分解的频率。

3 ILOG CPLEX优化软件的使用

协调技术（Concert Technology）是一个库函数，它提供应用程序接口（API）使CPLEX的许多优化器可以嵌套在C++、Java和Python程序中。具体的可视图如图1所示。在本文中，使用C++语言来编写应用程序，在C++中的对象通过协调技术与CPLEX对象和内核构建相连来建立与求解优化模型。C++对象可以包括两类：

1）建模对象是用来定义的优化问题。一般应用程序创建多个建模对象（Ilomodel）来表达优化问题。

2）Ilocplex对象是用来定义优化模型对象。一个Ilocplex对象从CPLEX优化器中读取一个模型并提取数据。然后ilocplex对象提取和查询信息解决方案。

协调技术是一个C++类库，协调技术的应用由许多相互作用的C++对象组成，其编程的基本思路如下：

1）搭建环境：通过在C++中定义一个IloEnv对象（env）来构建环境，它提供了优化时的存储器内存管理和性能提升。应用程序调用该对象截止时，需要将IloEnv对象释放。

2）创建模型：CPLEX C++通过IloModel对象来创建模型。创建模型后，应用程序就可以创建很多对象来定义的优化模型。

3）求解模型：通过Ilomodel创建优化模型后，需要定义一个Ilocplex对象，创建该对象时需要使用环境（env）最为参数。Ilocplex对象用于提出和解决模型。提取模型的一个方法是调用cplex.extract（model）。通过调用cplex.solve（）方法来解决所定义优化问题，cplex.solve（）函数将返回一个布尔变量来提示是否成功的找出一个可行解。

4）查询结果：成功的解决优化问题后，可以通过IloCplex：：getValue（IloNumVar var） const方法来查询一个变量或者一组变量的值和通过cplex.getValue（）来找出目标函数的值。

5）处理错误：为了增加Cplex C++的鲁棒性，应该在程序中添加避免错误的断言和不可以预见的错误和异常处理。协调技术提供了两种处理错误的防线。第一类包括简单程序错误。这类例子试图用空处理对象或不相容的长度来传递数组函数。第二种是无法避免的程序错误，如内存耗尽。数据需要太多的记忆，即使程序是正确的，这种错误通常在运行时检测。如果发生错误，C++将抛出异常。为了处理这些异常，CPLEX C++采用了一个try/catch层次的异常类，其来自与基类iloexception。

4 总结

本文主要介绍如何利用CPLEX软件包，编写C++程序来建模求解优化问题，为了使读者更加深入的了解CPLEX的求解过程，本文首先介绍CPLEX的求解原理，然后重点阐述C++编写建模程序的具体过程，其编程思路大致分为五步，即搭建环境、创建模型、求解模型、查询结果和处理异常。利用C++编写建模程序的优点是灵活性高，便于程序的扩充。

参考文献：

[1] CPLEX[EB/OL]. http：//baike.baidu.com/link？url=31PBxei42-tsCiiB_9GbOfy3QoktQKFk1C6z-fbNYxoaj0ntcEkiswP6Slc99-_qKF4qIkBg9KHi_R7Ew6of0a.

[2]刘均华，蓝伯雄. 基于CPLEX的原始——对偶嵌套分解算法[J]. 运筹与管理，2008（6）：1-5.

[3]孙岚. CPLEX在优化调度中的应用[J]. 福建电脑，2005（11）：42-43.

[4] 孙亮亮，刘炜，柴天佑. Tool Sequence Optimization Based on Three Logical Modes of Robot Control via CPLEX Optimization[J]. Journal of Shanghai Jiaotong University（Science），2011（4）：436-440.

[5] 王兴，孙晚华. 基于混合整数规划的配送中心选址研究[J]. 价值工程，2012（26）：15-17.