凌波微步是段誉所习得的上乘轻功功法，学习这门上乘轻功有那么一个约束条件，它需要对易经八卦等知识有了解，甚至可以说是精通。混合整数线性规划问题也有那么一点相似，那就是这个线性问题求解的结果需要有一个或者多个变量整数这么一个约束条件。下文我们将会重点讲述如何使用MindOpt C++ 语言的API来建模优化混合整数线性规划。
MindOpt Python、C、C++语言求解LP、MILP、QP问题系列
- Python: 线性规划LP问题、混合整数线性规划MILP问题、二次规划QP问题
- C : 线性规划LP问题、混合整数线性规划MILP问题、二次规划QP问题
- C++ : 线性规划LP问题、混合整数线性规划MILP问题(本篇)、二次规划QP问题
下载安装
用户可以点这里下载安装MindOpt优化求解器
开通算法服务控制台(免费的)
数学公式下的混合整数线性规划问题：
定义
我个人认为混合整数线性规划与线性规划的区别在于，线性规划在求解目标函数最优值的时候，决策变量是连续的，即可以是整数也可以是小数，但混合整数线性规划可能会有一个或者多个变量必须为整数。
- 不要小看只是多了一个为整数的约束，它会导致问题在很多时候会有更多的变数，这样计算起来就更加复杂。打一个简单的比喻，女朋友想吃你做的饭，那么你就在网上选菜，她会告诉你想吃什么(玉米啊、排骨啊、豆腐等等)，然后给了你一百的资金，就这样你带着这些条件选择各种食材，但发现在一百块的条件下，最后想买点大葱时钱不够了，但大葱不可能切一半给你，这样你就得重新选择其他食材的数量完成订菜。
- 还有经典的背包问题：桌子上有一组物品，每个物品有自己的价值和重量，但是包的承重是有限的；我们要装什么物品，在包的重量承受范围内，包里总物品的价值最高？这个里面选择那个物品就是个整数，并不能是小数切开，比如一个吹风机不能切开只带一半走。
混合整数线性规划在求解的时候，可以用分支定界法、割平面法等，会切分成子问题调用线性规划（LP）求解模块。MindOpt在今年也发布了混合整数线性规划（MILP）的求解能力。接下来我会举个数学算例如何使用。
数学算例
混合整数线性规划问题示例：
是不是看着数学算例很抽象？那么我们来举个例子带入：假设工厂有一种原材料，可以生产多种零件毛坯，但每种零件的生产方式也有多种，每种生产零件的方式可以得到不同零件的毛坯数以及每种零件的需要量，但需要其中一种零件生产必需为整数，我们要做的就是用MindOpt来帮助生产工人计算要怎么生产才能达到零件所需要的数量，所花费的原材料又最少。
MindOpt和C++下的建模优化
核心使用的几个APIs是：
MdoModel model; model.setIntAttr(MDO_INT_ATTR::MIN_SENSE, MDO_YES); model.addCons(1.0, MDO_INFINITY, 1.0 * x[0] + 1.0 * x[1] + 2.0 * x[2] + 3.0 * x[3], "c0"); model.addCons(1.0, 1.0, 1.0 * x[0] - 1.0 * x[2] + 6.0 * x[3], "c1"); model.solveProb(); model.displayResults();
下面是完整的例子，可复制存为MdoMiloEx1.cpp文件。
#include <iostream> #include <vector> /*引入头文件*/ #include "MindoptCpp.h" using namespace mindopt; int main(void) { /*------------------------------------------------------------------*/ /* Step 1. 创建模型并更改参数。 */ /*------------------------------------------------------------------*/ /* 创建一个空模型 */ MdoModel model; try { /*------------------------------------------------------------------*/ /* Step 2. 输入模型。. */ /*------------------------------------------------------------------*/ /* 改为最小化问题 */ /*通过 mindopt::MdoModel::setIntAttr() 将目标函数设置为 最小化*/ model.setIntAttr(MDO_INT_ATTR::MIN_SENSE, MDO_YES); /* 添加变量 */ /*调用 mindopt::MdoModel::addVar() 来添加四个优化变量，定义其下界、上界、名称和类型*/ std::vector<MdoVar> x; x.push_back(model.addVar(0.0, 10.0, 1.0, "x0", MDO_YES)); x.push_back(model.addVar(0.0, MDO_INFINITY, 1.0, "x1", MDO_YES)); x.push_back(model.addVar(0.0, MDO_INFINITY, 1.0, "x2", MDO_YES)); x.push_back(model.addVar(0.0, MDO_INFINITY, 1.0, "x3", MDO_NO)); /* 添加约束 */ /*通过 mindopt::MdoModel::addCons()来添加约束*/ model.addCons(1.0, MDO_INFINITY, 1.0 * x[0] + 1.0 * x[1] + 2.0 * x[2] + 3.0 * x[3], "c0"); model.addCons(1.0, 1.0, 1.0 * x[0] - 1.0 * x[2] + 6.0 * x[3], "c1"); /*------------------------------------------------------------------*/ /* Step 3. 解决问题并填充结果。 */ /*------------------------------------------------------------------*/ /* 调用 mindopt::MdoModel::solveProb() 求解优化问题， 并通过 mindopt::MdoModel::displayResults() 查看优化结果 */ model.solveProb(); model.displayResults(); } catch (MdoException & e) { std::cerr << "===================================" << std::endl; std::cerr << "Error : code <" << e.getResult() << ">" << std::endl; std::cerr << "Reason : " << model.explainResult(e.getResult()) << std::endl; std::cerr << "===================================" << std::endl; return static_cast<int>(e.getResult()); } return static_cast<int>(MDO_OKAY); }
MindOpt求解的结果
运行MdoMiloEx1.cpp文件的步骤
linux和Mac系统在命令行输入以下代码 cd <MDOHOME>/<VERSION>/examples/CPP make -f Makefile all ./MdoMiloEx1
windows系统本例是在Visual Studio上运行，版本为2019
#运行方式与前文 一致，只需要修改文件就好；把MdoLoEx1.cpp换成MdoMiloEx1.cpp
如上文所述，运行MdoMiloEx1.cpp文件，得到求解的结果如下所示，/**/号里面是我添加的注释。
Model summary. /*模型摘要*/ - Num. variables : 4 - Num. constraints : 2 - Num. nonzeros : 7 - Num. integer vars. : 3 - Bound range : [1.0e+00,1.0e+01]限制范围 - Objective range : [1.0e+00,1.0e+00]目标范围 Branch-and-cut method started. /*分支切割方法*/ Model summary. - Num. variables : 4 - Num. constraints : 2 - Num. nonzeros : 7 - Bound range : [1.0e+00,1.0e+01] - Objective range : [1.0e+00,1.0e+00] - Matrix range : [1.0e+00,6.0e+00] Presolver started. Presolver terminated. Time : 0.005s Simplex method started. Iteration Objective Dual Inf. Primal Inf. Time 0 0.00000e+00 0.0000e+00 1.3102e+00 0.04s 2 5.55556e-01 0.0000e+00 0.0000e+00 0.06s Postsolver started. /*单纯形法开始*/ Simplex method terminated. Time : 0.051s 2 5.55556e-01 0.0000e+00 0.0000e+00 0.08s 2 5.55556e-01 0.0000e+00 0.0000e+00 0.09s 2 5.55556e-01 0.0000e+00 0.0000e+00 0.10s 2 5.55556e-01 0.0000e+00 0.0000e+00 0.11s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.12s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.14s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.14s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.15s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.17s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.18s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.18s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.19s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.20s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.21s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.22s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.22s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.23s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.25s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.25s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.26s Branch-and-cut method terminated. Time : 0.567s Optimizer summary. - Optimizer used : Branch-and-cut method /*显示最终使用分支切割方法*/ - Optimizer status : OPTIMAL - Total time : 0.624s Solution summary. Primal solution - Objective : 1.0000000000e+00 /*目标函数最优解*/
联系我们
钉钉群号：32451444
邮箱地址：solver.damo@list.alibaba-inc.com
更多更新通知：https://solver.damo.alibaba.com
