MindOpt对于混合整数线性规划问题如何建模优化(python语言)

简介

MindOpt是一款高效的优化算法软件包，求解算法实现了线性规划(LP)、混合整数线性规划(MILP)、二次规划(QP)，可以支持命令行、c、c++、java和python调用。接下来我们将发布一系列文章，讲述各个语言如何使用 MindOpt 来求解数学规划问题。

本篇文章是系列文章的第二篇，下文会分享小编个人对混合整数线性规划的定义，然后举一个例题，最后将对使用 MindOpt Python 语言的 API 来建模以及求解 混合整数线性规划问题示例 中的问题以及展示求解的结果。

如何获取MindOpt求解器

求解器安装包的发布渠道。请大家:

1. 前往 https://www.aliyun.com/product/ai/opt 来下载求解器软件。
2. 在阿里云上获取免费授权码:
   • 请大家迁移到“云鉴权”自助申请licenseKey，配置fl_client.ini。新的“云鉴权”不需要绑定机器ID，只要阿里云账号并联网就好。
   关于求解器的使用文档，请参考：https://help.aliyun.com/document_detail/298219.htm

混合整数线性规划

我个人认为混合整数线性规划与线性规划的区别在于，线性规划在求解目标函数最优值的时候，决策变量是连续的，即可以是整数也可以是小数，但混合整数线性规划可能会有一个或者多个变量必须为整数。

比如经典的背包问题：

桌子上有一组物品，每个物品有自己的价值和重量，但是包的承重是有限的；我们要装什么物品，在包的重量承受范围内，包里总物品的价值最高？这个里面选择那个物品就是个整数，并不能是小数切开，比如一个吹风机不能切开只带一半走。

数学形式下的混合整数线性规划问题：

其中：

混合整数线性规划很多时候会更难求解。在求解的时候，可以用分支定界法、割平面法等，会切分成子问题调用线性规划（LP）求解模块。MindOpt在今年也发布了混合整数线性规划（MILP）的求解能力。接下来我会举个例子如何使用。

混合整数线性规划问题示例：

python代码示例：

   # 引入python包
from mindoptpy import *

if __name__ == "__main__":

    MDO_INFINITY = MdoModel.get_infinity()

    # Step 1.创建模型并更改参数。
    model = MdoModel()
    try:
        # Step 2. 输入模型。
        model.set_int_attr(MDO_INT_ATTR.MIN_SENSE, 1)
        
        # 添加变量。
        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.  解决问题并填充结果。
        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()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

详细代码解释如下：

第一步：创建模型

首先，我们必须建立一个空的模型

model = MdoModel()
1

第二步：MILP模型输入

• 接着我们利用Python API set_int_attr()将目标函数改为最小化

model.set_int_attr(MDO_INT_ATTR.MIN_SENSE, 1)
# 也可以选择这个模型属性model.set_int_attr("MinSense", 1) 数字1代表最小化，0代表最大化
1
2

• 再调用 add_var() 来添加四个优化变量，定义其下界、上界、名称和类型
  (0.0是新增变量的下界，10和MDO_INFINITY是上界，1.0为新变量的目标系数，
  None是包含非零元素的列对象，默认为None。""中是变量的名字，False代表不可指定是否为整数变量的布尔标志，因为第一个第二个第三个参数必须为整数所以他们的布尔标志为True)

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))
1
2
3
4
5

• 然后调用add_cons()来添加约束
  (1.0为新约束的左侧值，或临时线性对象。MDO_INFINITY和10为新约束的右侧值，或者一个约束名称的字符串。"c0、c1"为这条约束的名字。)

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")
1
2

第三步：求解MILP模型

模型输入后，我们接着用solve_prob()来求解问题。
并用display_results()呈现求解结果。

model.solve_prob()
model.display_results()
1
2

如果您觉得阅读数学公式案例很抽象，可以去我们云上建模求解平台的案例广场查看更多的案例哦
云上建模求解平台：https://opt.aliyun.com/

联系我们

钉钉群号：32451444
邮箱地址：solver.damo@list.alibaba-inc.com
更多更新通知：https://solver.damo.alibaba.com