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 };
完整源代码请参考 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_WARMSTART"
35#define MODEL_SENSE "ModelSense"
36#define SOL_COUNT "SolCount"
37#define STATUS "Status"
38#define OBJ_VAL "ObjVal"
39#define X "X"
40
41int main(void)
42{
43 /* Variables. */
44 MDOenv *env;
45 MDOmodel *m;
46 double obj, x;
47 int i, solcount, status;
48
49 /* Model data. */
50 int row1_idx[] = { 0, 1, 2, 3 };
51 double row1_val[] = { 1.0, 1.0, 2.0, 3.0 };
52 int row2_idx[] = { 0, 2, 3 };
53 double row2_val[] = { 1.0, -1.0, 6.0 };
54
55 /*------------------------------------------------------------------*/
56 /* Step 1. Create a model and change the parameters. */
57 /*------------------------------------------------------------------*/
58 CHECK_RESULT(MDOemptyenv(&env));
59 CHECK_RESULT(MDOstartenv(env));
60 CHECK_RESULT(MDOnewmodel(env, &m, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
61
62 /*------------------------------------------------------------------*/
63 /* Step 2. Input model. */
64 /*------------------------------------------------------------------*/
65 /* Change to minimization problem. */
66 CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MINIMIZE));
67
68 /* Add variables. */
69 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, 10.0, MDO_INTEGER, "x0"));
70 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 2.0, 0, MDO_INFINITY, MDO_INTEGER, "x1"));
71 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_INTEGER, "x2"));
72 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x3"));
73
74 /* Add constraints. */
75 CHECK_RESULT(MDOaddconstr(m, 4, row1_idx, row1_val, MDO_GREATER_EQUAL, 1.0, "c0"));
76 CHECK_RESULT(MDOaddconstr(m, 3, row2_idx, row2_val, MDO_EQUAL, 1.0, "c1"));
77
78 /* Add an initial solution */
79 int var_idx_start = 0;
80 int var_num = 4;
81 double var_val[] = { 1.0, 0.0, 0.0, 0.0 };
82 CHECK_RESULT(MDOsetdblattrarray(m, "Start", var_idx_start, var_num, &(*var_val)));
83
84 /*------------------------------------------------------------------*/
85 /* Step 3. Solve the problem . */
86 /*------------------------------------------------------------------*/
87 CHECK_RESULT(MDOoptimize(m));
88
89 /*------------------------------------------------------------------*/
90 /* Step 4. Retrive model status and objective. */
91 /* For MIP(MILP,MIQP, MIQCP) problems, if the solving process */
92 /* terminates early due to reasons such as timeout or interruption, */
93 /* the model status will indicate termination by timeout (or */
94 /* interruption, etc.). However, suboptimal solutions may still */
95 /* exist, making it necessary to check the SolCount property. */
96 /*------------------------------------------------------------------*/
97 CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
98 CHECK_RESULT(MDOgetintattr(m, SOL_COUNT, &solcount));
99 if (status == MDO_OPTIMAL || status == MDO_SUB_OPTIMAL || solcount != 0)
100 {
101 CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
102 printf("The optimal objective value is %f\n", obj);
103 for (int i = 0; i < 4; ++i)
104 {
105 CHECK_RESULT(MDOgetdblattrelement(m, X, i, &x));
106 printf("x[%d] = %f\n", i, x);
107 }
108 }
109 else
110 {
111 printf("No feasible solution.\n");
112 }
113
114
115 /*------------------------------------------------------------------*/
116 /* Step 4. Free the model. */
117 /*------------------------------------------------------------------*/
118 RELEASE_MEMORY;
119
120 return 0;
121}
以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. */
66 /*------------------------------------------------------------------*/
67 model.optimize();
68
69 /*------------------------------------------------------------------*/
70 /* Step 4. Retrive model status and objective. */
71 /* For MIP(MILP,MIQP, MIQCP) problems, if the solving process */
72 /* terminates early due to reasons such as timeout or interruption, */
73 /* the model status will indicate termination by timeout (or */
74 /* interruption, etc.). However, suboptimal solutions may still */
75 /* exist, making it necessary to check the SolCount property. */
76 /*------------------------------------------------------------------*/
77 if (model.get(MDO_IntAttr_Status) == MDO_OPTIMAL || model.get(MDO_IntAttr_Status) == MDO_SUB_OPTIMAL ||
78 model.get(MDO_IntAttr_SolCount) != 0)
79 {
80 cout << "Optimal objective value is: " << model.get(MDO_DoubleAttr_ObjVal) << "." << endl;
81 cout << "Decision variables:" << endl;
82 int i = 0;
83 for (auto v : x)
84 {
85 cout << "x[" << i << "] = " << v.get(MDO_DoubleAttr_X) << endl;
86 }
87 }
88 else
89 {
90 cout<< "No feasible solution." << endl;
91 }
92 }
93 catch (MDOException& e)
94 {
95 cout << "Error code = " << e.getErrorCode() << endl;
96 cout << e.getMessage() << endl;
97 }
98 catch (...)
99 {
100 cout << "Error during optimization." << endl;
101 }
102
103 return static_cast<int>(MDO_OKAY);
104}
5.2.7.2. 读取mst文件¶
用户可以通过从 .mst 文件读取初始解来热启动 MindOpt ：
编程语言 |
方法 |
C |
|
C++ |
|
JAVA |
|
Python |
|
.mst 文件由若干行“变量名 变量值”组成，例如：
1x0 1
2x1 0
3x2 0
MindOpt 读入 .mst 文件后，即完成变量初始值的设置，用户不需要再手动设置。
用户可以在 .mst 文件中列出所有变量的初始值，也可以仅列出部分变量的初始值；若同一变量名在文件中出现多次，以最后一次为准。
备注
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 # Step 4. Retrive model status and objective.
56 # For MIP(MILP,MIQP, MIQCP) problems, if the solving process
57 # terminates early due to reasons such as timeout or interruption,
58 # the model status will indicate termination by timeout (or
59 # interruption, etc.). However, suboptimal solutions may still
60 # exist, making it necessary to check the SolCount property.
61 if model.status == MDO.OPTIMAL or model.status == MDO.SUB_OPTIMAL or model.solcount !=0:
62 print(f"Optimal objective value is: {model.objval}")
63 print("Decision variables: ")
64 for v in x:
65 print(f"x[{v.VarName}] = {v.X}")
66 else:
67 print("No feasible solution.")
68 except MindoptError as e:
69 print("Received Mindopt exception.")
70 print(" - Code : {}".format(e.errno))
71 print(" - Reason : {}".format(e.message))
72 except Exception as e:
73 print("Received other exception.")
74 print(" - Reason : {}".format(e))
75 finally:
76 # Step 4. Free the model.
77 model.dispose()