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

MDOsetdblattrarray()

C++

MDOVar::set()

JAVA

MDOVar::setAttr()

Python

Var::setAttr()

以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

MDOread()

C++

MDOModel::read()

JAVA

MDOModel::read()

Python

Model::read()

.mst 文件由若干行“变量名 变量值”组成,例如:

1x0 1
2x1 0
3x2 0

MindOpt 读入 .mst 文件后,即完成变量初始值的设置,用户不需要再手动设置。 用户可以在 .mst 文件中列出所有变量的初始值,也可以仅列出部分变量的初始值;若同一变量名在文件中出现多次,以最后一次为准。

Note

MindOptwrite 方法将解保存到 .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()