5.2.7. MILP的热启动¶
在求解混合整数规划问题时，用户可以将已知的可行解输入模型，作为模型的初始解，通常可以起到加速求解的效果，称为热启动(Warm-Start)。
MindOpt 提供了两种方式来对优化模型进行热启动：设置变量的 Start 属性，以及，直接从 .mst 文件读取初始解。
MindOpt 不仅支持基于完整的初始解进行热启动，也支持基于部分解进行热启动，即用户可以只设置部分变量的初始值。
当求解器成功热启动， MindOpt 会给出类似 “accept new sol: obj 1 bnd vio 0 int vio 0 mipgap 1 time 0” 的提示信息，表示求解器成功加载目标函数值为1的初始解，否则提示 “initial solution is not accepted”。
5.2.7.1. 设置变量start属性¶
用户可以通过设置变量的 Start 属性来热启动 MindOpt ：
编程语言 |
方法 |
C |
|
C++ |
|
JAVA |
|
Python |
|
以C为例：
67 /* Add variables. */
68 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, 10.0, MDO_INTEGER, "x0"));
69 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 2.0, 0, MDO_INFINITY, MDO_INTEGER, "x1"));
70 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_INTEGER, "x2"));
71 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x3"));
72
73 /* Add constraints. */
74 CHECK_RESULT(MDOaddconstr(m, 4, row1_idx, row1_val, MDO_GREATER_EQUAL, 1.0, "c0"));
75 CHECK_RESULT(MDOaddconstr(m, 3, row2_idx, row2_val, MDO_EQUAL, 1.0, "c1"));
76
77 /* Add an initial solution */
78 int var_idx_start = 0;
79 int var_num = 4;
80 double var_val[] = { 1.0, 0.0, 0.0, 0.0 };
81 CHECK_RESULT(MDOsetdblattrarray(m, "Start", var_idx_start, var_num, &(*var_val)));
完整源代码请参考 MdoMiloWarmstart.c
1/**
2 * Description
3 * -----------
4 *
5 * Mixed Integer Linear optimization (row-wise input).
6 *
7 * Formulation
8 * -----------
9 *
10 * Minimize
11 * obj: 1 x0 + 2 x1 + 1 x2 + 1 x3
12 * Subject To
13 * c0 : 1 x0 + 1 x1 + 2 x2 + 3 x3 >= 1
14 * c1 : 1 x0 - 1 x2 + 6 x3 = 1
15 * Bounds
16 * 0 <= x0 <= 10
17 * 0 <= x1
18 * 0 <= x2
19 * 0 <= x3
20 * Integers
21 * x0 x1 x2
22 * End
23 */
24
25#include <stdio.h>
26#include <stdlib.h>
27#include "Mindopt.h"
28
29/* Macro to check the return code */
30#define RELEASE_MEMORY \
31 MDOfreemodel(m); \
32 MDOfreeenv(env);
33#define CHECK_RESULT(code) { int res = code; if (res != 0) { fprintf(stderr, "Bad code: %d\n", res); exit(res); } }
34#define MODEL_NAME "MILP_01"
35#define MODEL_SENSE "ModelSense"
36#define STATUS "Status"
37#define OBJ_VAL "ObjVal"
38#define X "X"
39
40int main(void)
41{
42 /* Variables. */
43 MDOenv *env;
44 MDOmodel *m;
45 double obj, x;
46 int status, i;
47
48 /* Model data. */
49 int row1_idx[] = { 0, 1, 2, 3 };
50 double row1_val[] = { 1.0, 1.0, 2.0, 3.0 };
51 int row2_idx[] = { 0, 2, 3 };
52 double row2_val[] = { 1.0, -1.0, 6.0 };
53
54 /*------------------------------------------------------------------*/
55 /* Step 1. Create a model and change the parameters. */
56 /*------------------------------------------------------------------*/
57 CHECK_RESULT(MDOemptyenv(&env));
58 CHECK_RESULT(MDOstartenv(env));
59 CHECK_RESULT(MDOnewmodel(env, &m, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
60
61 /*------------------------------------------------------------------*/
62 /* Step 2. Input model. */
63 /*------------------------------------------------------------------*/
64 /* Change to minimization problem. */
65 CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MINIMIZE));
66
67 /* Add variables. */
68 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, 10.0, MDO_INTEGER, "x0"));
69 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 2.0, 0, MDO_INFINITY, MDO_INTEGER, "x1"));
70 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_INTEGER, "x2"));
71 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x3"));
72
73 /* Add constraints. */
74 CHECK_RESULT(MDOaddconstr(m, 4, row1_idx, row1_val, MDO_GREATER_EQUAL, 1.0, "c0"));
75 CHECK_RESULT(MDOaddconstr(m, 3, row2_idx, row2_val, MDO_EQUAL, 1.0, "c1"));
76
77 /* Add an initial solution */
78 int var_idx_start = 0;
79 int var_num = 4;
80 double var_val[] = { 1.0, 0.0, 0.0, 0.0 };
81 CHECK_RESULT(MDOsetdblattrarray(m, "Start", var_idx_start, var_num, &(*var_val)));
82
83 /*------------------------------------------------------------------*/
84 /* Step 3. Solve the problem and populate optimization result. */
85 /*------------------------------------------------------------------*/
86 CHECK_RESULT(MDOoptimize(m));
87 CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
88 if (status == MDO_OPTIMAL)
89 {
90 CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
91 printf("The optimal objective value is %f\n", obj);
92 for (int i = 0; i < 4; ++i)
93 {
94 CHECK_RESULT(MDOgetdblattrelement(m, X, i, &x));
95 printf("x[%d] = %f\n", i, x);
96 }
97 }
98 else
99 {
100 printf("No feasible solution.\n");
101 }
102
103
104 /*------------------------------------------------------------------*/
105 /* Step 4. Free the model. */
106 /*------------------------------------------------------------------*/
107 RELEASE_MEMORY;
108
109 return 0;
110}
以C++为例：
47 /* Add variables. */
48 std::vector<MDOVar> x;
49 x.push_back(model.addVar(0.0, 10.0, 1.0, MDO_INTEGER, "x0"));
50 x.push_back(model.addVar(0.0, MDO_INFINITY, 2.0, MDO_INTEGER, "x1"));
51 x.push_back(model.addVar(0.0, MDO_INFINITY, 1.0, MDO_INTEGER, "x2"));
52 x.push_back(model.addVar(0.0, MDO_INFINITY, 1.0, MDO_CONTINUOUS,"x3"));
53
54 /* Add constraints. */
55 model.addConstr(1.0 * x[0] + 1.0 * x[1] + 2.0 * x[2] + 3.0 * x[3], MDO_GREATER_EQUAL, 1.0, "c0");
56 model.addConstr(1.0 * x[0] - 1.0 * x[2] + 6.0 * x[3], MDO_EQUAL, 1.0, "c1");
57
58 /* Add an initial solution */
59 x[0].set(MDO_DoubleAttr_Start, 1);
60 x[1].set(MDO_DoubleAttr_Start, 0);
61 x[2].set(MDO_DoubleAttr_Start, 0);
62 x[3].set(MDO_DoubleAttr_Start, 0);
完整源代码请参考 MdoMiloWarmstart.cpp
1/**
2 * Description
3 * -----------
4 *
5 * Mixed Integer Linear optimization (row-wise input).
6 *
7 * Formulation
8 * -----------
9 *
10 * Minimize
11 * obj: 1 x0 + 2 x1 + 1 x2 + 1 x3
12 * Subject To
13 * c0 : 1 x0 + 1 x1 + 2 x2 + 3 x3 >= 1
14 * c1 : 1 x0 - 1 x2 + 6 x3 = 1
15 * Bounds
16 * 0 <= x0 <= 10
17 * 0 <= x1
18 * 0 <= x2
19 * 0 <= x3
20 * Integers
21 * x0 x1 x2
22 * End
23 */
24
25#include <iostream>
26#include <vector>
27#include "MindoptCpp.h"
28
29using namespace std;
30
31int main(void)
32{
33 /*------------------------------------------------------------------*/
34 /* Step 1. Create a model and change the parameters. */
35 /*------------------------------------------------------------------*/
36 MDOEnv env = MDOEnv();
37 MDOModel model = MDOModel(env);
38
39 try
40 {
41 /*------------------------------------------------------------------*/
42 /* Step 2. Input model. */
43 /*------------------------------------------------------------------*/
44 /* Change to minimization problem. */
45 model.set(MDO_IntAttr_ModelSense, MDO_MINIMIZE);
46
47 /* Add variables. */
48 std::vector<MDOVar> x;
49 x.push_back(model.addVar(0.0, 10.0, 1.0, MDO_INTEGER, "x0"));
50 x.push_back(model.addVar(0.0, MDO_INFINITY, 2.0, MDO_INTEGER, "x1"));
51 x.push_back(model.addVar(0.0, MDO_INFINITY, 1.0, MDO_INTEGER, "x2"));
52 x.push_back(model.addVar(0.0, MDO_INFINITY, 1.0, MDO_CONTINUOUS,"x3"));
53
54 /* Add constraints. */
55 model.addConstr(1.0 * x[0] + 1.0 * x[1] + 2.0 * x[2] + 3.0 * x[3], MDO_GREATER_EQUAL, 1.0, "c0");
56 model.addConstr(1.0 * x[0] - 1.0 * x[2] + 6.0 * x[3], MDO_EQUAL, 1.0, "c1");
57
58 /* Add an initial solution */
59 x[0].set(MDO_DoubleAttr_Start, 1);
60 x[1].set(MDO_DoubleAttr_Start, 0);
61 x[2].set(MDO_DoubleAttr_Start, 0);
62 x[3].set(MDO_DoubleAttr_Start, 0);
63
64 /*------------------------------------------------------------------*/
65 /* Step 3. Solve the problem and populate optimization result. */
66 /*------------------------------------------------------------------*/
67 model.optimize();
68 if(model.get(MDO_IntAttr_Status) == MDO_OPTIMAL)
69 {
70 cout << "Optimal objective value is: " << model.get(MDO_DoubleAttr_ObjVal) << "." << endl;
71 cout << "Decision variables:" << endl;
72 int i = 0;
73 for (auto v : x)
74 {
75 cout << "x[" << i << "] = " << v.get(MDO_DoubleAttr_X) << endl;
76 }
77 }
78 else
79 {
80 cout<< "No feasible solution." << endl;
81 }
82 }
83 catch (MDOException& e)
84 {
85 cout << "Error code = " << e.getErrorCode() << endl;
86 cout << e.getMessage() << endl;
87 }
88 catch (...)
89 {
90 cout << "Error during optimization." << endl;
91 }
92
93 return static_cast<int>(MDO_OKAY);
94}
5.2.7.2. 读取mst文件¶
用户可以通过从 .mst 文件读取初始解来热启动 MindOpt ：
编程语言 |
方法 |
C |
|
C++ |
|
JAVA |
|
Python |
|
.mst 文件由若干行“变量名 变量值”组成，例如：
1x0 1
2x1 0
3x2 0
MindOpt 读入 .mst 文件后，即完成变量初始值的设置，用户不需要再手动设置。
用户可以在 .mst 文件中列出所有变量的初始值，也可以仅列出部分变量的初始值；若同一变量名在文件中出现多次，以最后一次为准。
Note
MindOpt 的 write 方法将解保存到 .mst 文件时，会忽略所有连续变量。如果用户希望保存所有变量的信息，请将结果保存到 .sol 文件。
以Python为例，从已有的 .mst 文件读入初始解进行热启动：
38 # Add variables.
39 x = []
40 x.append(model.addVar(0.0, 10.0, 1.0, 'I', "x0"))
41 x.append(model.addVar(0.0, float('inf'), 2.0, 'I', "x1"))
42 x.append(model.addVar(0.0, float('inf'), 1.0, 'I', "x2"))
43 x.append(model.addVar(0.0, float('inf'), 1.0, 'C', "x3"))
44
45 # Read an initial solution from mst file
46 model.read("solution.mst")
47
48 # Add constraints.
49 model.addConstr(1.0 * x[0] + 1.0 * x[1] + 2.0 * x[2] + 3.0 * x[3] >= 1, "c0")
50 model.addConstr(1.0 * x[0] - 1.0 * x[2] + 6.0 * x[3] == 1, "c1")
51
52 # Step 3. Solve the problem and populate optimization result.
53 model.optimize()
完整源代码请参考 mdo_milo_ws.py
1"""
2/**
3 * Description
4 * -----------
5 *
6 * Mixed Integer Linear optimization (row-wise input).
7 *
8 * Formulation
9 * -----------
10 *
11 * Minimize
12 * obj: 1 x0 + 2 x1 + 1 x2 + 1 x3
13 * Subject To
14 * c0 : 1 x0 + 1 x1 + 2 x2 + 3 x3 >= 1
15 * c1 : 1 x0 - 1 x2 + 6 x3 = 1
16 * Bounds
17 * 0 <= x0 <= 10
18 * 0 <= x1
19 * 0 <= x2
20 * 0 <= x3
21 * Integers
22 * x0 x1 x2
23 * End
24 */
25"""
26from mindoptpy import *
27
28if __name__ == "__main__":
29
30 # Step 1. Create a model.
31 model = Model("MILP_WS")
32
33 try:
34 # Step 2. Input model.
35 # Change to minimization problem.
36 model.modelsense = MDO.MINIMIZE
37
38 # Add variables.
39 x = []
40 x.append(model.addVar(0.0, 10.0, 1.0, 'I', "x0"))
41 x.append(model.addVar(0.0, float('inf'), 2.0, 'I', "x1"))
42 x.append(model.addVar(0.0, float('inf'), 1.0, 'I', "x2"))
43 x.append(model.addVar(0.0, float('inf'), 1.0, 'C', "x3"))
44
45 # Read an initial solution from mst file
46 model.read("solution.mst")
47
48 # Add constraints.
49 model.addConstr(1.0 * x[0] + 1.0 * x[1] + 2.0 * x[2] + 3.0 * x[3] >= 1, "c0")
50 model.addConstr(1.0 * x[0] - 1.0 * x[2] + 6.0 * x[3] == 1, "c1")
51
52 # Step 3. Solve the problem and populate optimization result.
53 model.optimize()
54
55 if model.status == MDO.OPTIMAL:
56 print(f"Optimal objective value is: {model.objval}")
57 print("Decision variables: ")
58 for v in x:
59 print(f"x[{v.VarName}] = {v.X}")
60 else:
61 print("No feasible solution.")
62 except MindoptError as e:
63 print("Received Mindopt exception.")
64 print(" - Code : {}".format(e.errno))
65 print(" - Reason : {}".format(e.message))
66 except Exception as e:
67 print("Received other exception.")
68 print(" - Reason : {}".format(e))
69 finally:
70 # Step 4. Free the model.
71 model.dispose()