下文我们将讲述小编对线性规划的理解以及展示两个算例，和使用 MindOpt C 语言的 API 来建模以及求解 混合整数线性规划示例 中的问题。
(混合整数线性规划定义、算数例题都是与前文python语言的混合整数线性规划问题是一致的，已经阅读了前文可以忽略，直接点击目录进阶算例阅读建模优化代码。)
MindOpt Python、C、C++语言求解LP、MILP、QP问题系列
- Python: 线性规划LP问题、混合整数线性规划MILP问题、二次规划QP问题
- C : 线性规划LP问题、混合整数线性规划MILP问题(本篇)、二次规划QP问题
- C++ : 线性规划LP问题、混合整数线性规划MILP问题、二次规划QP问题
下载安装
用户可以点这里下载安装MindOpt优化求解器，免费的。找不到安装步骤点这里。
(官网https://opt.aliyun.com有更多信息等着您哟!)
混合整数线性规划
我个人认为混合整数线性规划与线性规划的区别在于，线性规划在求解目标函数最优值的时候，决策变量是连续的，即可以是整数也可以是小数，但混合整数线性规划可能会有一个或者多个变量必须为整数。
比如经典的背包问题：桌子上有一组物品，每个物品有自己的价值和重量，但是包的承重是有限的；我们要装什么物品，在包的重量承受范围内，包里总物品的价值最高？这个里面选择那个物品就是个整数，并不能是小数切开，比如一个吹风机不能切开只带一半走。
数学形式下的混合整数线性规划问题：
混合整数线性规划很多时候会更难求解。在求解的时候，可以用分支定界法、割平面法等，会切分成子问题调用线性规划（LP）求解模块。MindOpt在今年也发布了混合整数线性规划（MILP）的求解能力。接下来我会举个例子如何使用。
案例
和上篇 线性规划 一样，我们对于混合线性规划问题示例 做一个假设，把它当作一个生活中实际的例子，而不是数学公式这么抽象。
假设工厂有一种原材料，可以生产多种零件毛坯，但每种零件的生产方式也有多种，每种生产零件的方式可以得到不同零件的毛坯数以及每种零件的需要量，但需要其中一种零件生产必需为整数，那么要怎么生产才能达到零件所需要的数量，所花费的原材料又最少。
数学算例
混合整数线性规划问题示例：
C语言+MindOpt代码实现
核心使用的几个APIs是：
MDO_CHECK_CALL(Mdo_createMdl(&model)) MDO_CHECK_CALL(Mdo_setIntAttr(model, MDO_INT_ATTR_MIN_SENSE, MDO_YES)) MDO_CHECK_CALL(Mdo_addRow(model, 1.0, MDO_INFINITY, 4, row1_idx, row1_val, "c0")); MDO_CHECK_CALL(Mdo_addRow(model, 1.0, 1.0, 3, row2_idx, row2_val, "c1")); MDO_CHECK_CALL(Mdo_solveProb(model)); Mdo_displayResults(model);
#关于更多API的详细使用方式，请参考 C 接口函数
下面是完整的例子，可复制存为MdoMiloEx1.c文件。
/*引入头文件*/ /* 检查返回码的宏 */ int main(void) { /* 变量 */ char str[1024] = { "\0" }; MdoMdl * model = NULL; MdoResult code = MDO_OKAY; MdoStatus status = MDO_UNKNOWN; const int row1_idx[] = { 0, 1, 2, 3 }; const double row1_val[] = { 1.0, 1.0, 2.0, 3.0 }; const int row2_idx[] = { 0, 2, 3 }; const double row2_val[] = { 1.0, -1.0, 6.0 }; /*------------------------------------------------------------------*/ /* Step 1. 创建模型并更改参数。 */ /*------------------------------------------------------------------*/ /* 创建一个空模型。 */ MDO_CHECK_CALL(Mdo_createMdl(&model)); /*------------------------------------------------------------------*/ /* Step 2. 输入模型。 */ /*------------------------------------------------------------------*/ /* 改成最小化问题。 */ /*通过 Mdo_setIntAttr() 将目标函数设置为 最小化 */ MDO_CHECK_CALL(Mdo_setIntAttr(model, MDO_INT_ATTR_MIN_SENSE, MDO_YES)); /* 添加变量。 */ /*调用 Mdo_addCol() 来添加四个优化变量，定义其下界、上界、名称和类型*/ MDO_CHECK_CALL(Mdo_addCol(model, 0.0, 10.0, 1.0, 0, NULL, NULL, "x0", MDO_YES)); MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x1", MDO_YES)); MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x2", MDO_YES)); MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x3", MDO_NO)); /* 添加约束。 * 请注意，这里的非零元素是按行顺序输入的。 *调用 Mdo_addRow() 来输入约束 */ MDO_CHECK_CALL(Mdo_addRow(model, 1.0, MDO_INFINITY, 4, row1_idx, row1_val, "c0")); MDO_CHECK_CALL(Mdo_addRow(model, 1.0, 1.0, 3, row2_idx, row2_val, "c1")); /*------------------------------------------------------------------*/ /* Step 3. 解决问题并填充结果。 */ /*------------------------------------------------------------------*/ /* 调用 Mdo_solveProb() 求解优化问题，并通过 Mdo_displayResults() 查看优化结果 */ MDO_CHECK_CALL(Mdo_solveProb(model)); Mdo_displayResults(model); /*------------------------------------------------------------------*/ /* Step 4. 释放模型。 */ /*------------------------------------------------------------------*/ /* 调用 Mdo_freeMdl() 来释放内存 */ Mdo_freeMdl(&model); return (int)code; }
MindOpt求解的结果
如何编译及运行MdoMiloEx1.c文件
#运行方式与前文线性规划一致，只需要修改文件就好；把MdoLoEx1.c换成MdoMiloEx1.c
windows系统本例是在Visual Studio上运行，版本为2019
/*linux和mac系统直接在命令行输入*/ cd <MDOHOME>/<VERSION>/examples/C make -f Makefile all ./MdoMiloEx1
然后运行MdoMiloEx1.c 文件后，得到求解的结果如下所示，/**/号里面是我添加的注释。
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. /*分支切割方法*/ Original model: nrow = 2 ncol = 4 nnz = 7 Tolerance: primal = 1e-06 int = 1e-05 mipgap = 0.0001 mipgapAbs = 1e-06 Parallelism: root=1, tree=2 tree id 0 node 0 accept a new sol: obj 1 (heur) bnd vio 0 int vio 0 mipgap 1e+100 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.003s Simplex method started. /*单纯形法*/ Iteration Objective Dual Inf. Primal Inf. Time 0 0.00000e+00 0.0000e+00 2.0000e+00 0.02s 2 5.55556e-01 0.0000e+00 0.0000e+00 0.02s Postsolver started. Simplex method terminated. Time : 0.014s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.03s Branch-and-cut method terminated. Time : 0.062s Optimizer summary. /*求解器最终选择的优化方法以及求解消耗的时间*/ - Optimizer used : Branch-and-cut method /*分支和切割方法*/ - Optimizer status : OPTIMAL - Total time : 0.087s Solution summary. - Primal objective : 1.0000000000e+00 /*目标函数最优解*/ - Dual bound : 5.5555555556e-01
联系我们
钉钉：damodi
邮箱地址：solver.damo@list.alibaba-inc.com
