本篇文章是系列文章的第二篇，下文会分享小编个人对混合整数线性规划的定义，然后举一个例题，最后将对使用 MindOpt Python 语言的 API 来建模以及求解 混合整数线性规划问题示例 中的问题以及展示求解的结果。
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）的求解能力。接下来我会举个例子如何使用。
例子
和上篇 线性规划一样，我们对于混合线性规划问题示例 做一个假设，把它当作一个生活中实际的例子，而不是数学公式这么抽象。
假设工厂有一种原材料，可以生产多种零件毛坯，但每种零件的生产方式也有多种，每种生产零件的方式可以得到不同零件的毛坯数以及每种零件的需要量，但需要其中一种零件生产必需为整数，那么要怎么生产才能达到零件所需要的数量，所花费的原材料又最少。
数学算例
混合整数线性规划问题示例：
Python+MindOpt代码实现
核心使用的几个APIs是：
model = MdoModel() model.set_int_attr(MDO_INT_ATTR.MIN_SENSE, 1) x.append(model.add_var(0.0, 10.0, 1.0, None, "x0", True)) model.add_cons(1.0, MDO_INFINITY, 1.0 * x[0] + 1.0 * x[1] + 2.0 * x[2] + 3.0 * x[3], "c0") model.solve_prob() model.display_results()
下面是完整的例子，可复制存为test_MILP.py文件。
# 引入python包 from mindoptpy import * if __name__ == "__main__": MDO_INFINITY = MdoModel.get_infinity() # Step 1.创建模型并更改参数。 model = MdoModel() try: # Step 2. 输入模型。 # 改为最小化问题。 # 通过 mindoptpy.MdoModel.set_int_attr() 将目标函数设置为 最小化 model.set_int_attr(MDO_INT_ATTR.MIN_SENSE, 1) # 添加变量。 # 调用 mindoptpy.MdoModel.add_var() 来添加四个优化变量， # 定义其下界、上界、名称和类型 x = [] x.append(model.add_var(0.0, 10.0, 1.0, None, "x0", True)) x.append(model.add_var(0.0, MDO_INFINITY, 1.0, None, "x1", True)) x.append(model.add_var(0.0, MDO_INFINITY, 1.0, None, "x2", True)) x.append(model.add_var(0.0, MDO_INFINITY, 1.0, None, "x3", False)) # 添加约束。 # 注意这里的非零元素是按行顺序输入的。 model.add_cons(1.0, MDO_INFINITY, 1.0 * x[0] + 1.0 * x[1] + 2.0 * x[2] + 3.0 * x[3], "c0") model.add_cons(1.0, 1.0, 1.0 * x[0] - 1.0 * x[2] + 6.0 * x[3], "c1") # Step 3. 解决问题并填充结果。 # 调用 mindoptpy.MdoModel.solve_prob() 求解优化问题， # 并用 mindoptpy.MdoModel.display_results() 来查看优化结果 model.solve_prob() model.display_results() # 调用 mindoptpy.MdoModel.get_status() 来检查求解器的优化状态， # 并通过 mindoptpy.MdoModel.get_real_attr() 和 # mindoptpy.MdoVar.get_real_attr() 来获取目标值和最优解。 status_code, status_msg = model.get_status() if status_msg == "OPTIMAL": print("Optimizer terminated with an OPTIMAL status (code {0}).".format(status_code)) print("Primal objective : {0}".format(round(model.get_real_attr(MDO_REAL_ATTR.PRIMAL_OBJ_VAL), 2))) for curr_x in x: print(" - x[{0}] : {1}".format(curr_x.get_index(), round(curr_x.get_real_attr(MDO_REAL_ATTR.PRIMAL_SOLN), 2))) else: print("Optimizer terminated with a(n) {0} status (code {1}).".format(status_msg, status_code)) except MdoError as e: print("Received Mindopt exception.") print(" - Code : {}".format(e.code)) print(" - Reason : {}".format(e.message)) except Exception as e: print("Received exception.") print(" - Reason : {}".format(e)) finally: # Step 4. 释放模型。 model.free_mdl()
MindOpt求解的结果
然后运行代码，如命令行中执行python test_MILP.py 后，得到求解的结果如下所示，#号后面是我添加的注释。
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.000s Simplex method started. #使用了单纯形法 Iteration Objective Dual Inf. Primal Inf. Time 0 0.00000e+00 0.0000e+00 1.3102e+00 0.00s 2 5.55556e-01 0.0000e+00 0.0000e+00 0.00s Postsolver started. Simplex method terminated. Time : 0.001s 2 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 2 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 2 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 2 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s 0 5.55556e-01 0.0000e+00 0.0000e+00 0.01s Branch-and-cut method terminated. Time : 0.016s Optimizer terminated with an OPTIMAL status (code 1). Primal objective : 1.0 - x[0] : 1.0 - x[1] : -0.0 #决策变量们的最佳取值，即X0取值为1，其他为0 - x[2] : -0.0 - x[3] : 0.0 Optimizer summary. - Optimizer used : Branch-and-cut method - Optimizer status : OPTIMAL - Total time : 0.016s Solution summary. Primal solution #目标函数最优解，即目标最小值是1 - Objective : 1.0000000000e+00
联系我们
钉钉：damodi
邮箱地址：solver.damo@list.alibaba-inc.com
