5.5. 约束不可行性分析¶
在对实际应用中的优化问题进行建模求解的过程中，往往会遇到问题不可行的情况。而不可行问题必然是由某些约束互相之间冲突导致的，如何分析问题的不可行性并识别出导致冲突的关键约束成为求解器应用的重要一环。
这类导致问题不可行的最小约束子集被称为不可约不可行系统 (IIS, irreduciable infeasible system)。MindOpt 设计了用来计算 IIS 的 API，用户可以通过利用该 API 来对不可行问题进行分析。再依据此对 IIS 中的约束进行修正或移除，可以使得优化问题变得可行，以便于更好地对实际问题进行分析建模和获得最优决策。
需要注意的是，在线性规划问题中，IIS 可能并不是唯一的。若存在多个 IIS，则需要对优化问题进行多次调整，才能使其变得可行。例如：
\[\begin{split}\text{c}_1: ~~ x_1 \leq 1 \\
\text{c}_2: ~~ x_1 \geq 2 \\
\text{c}_3: ~~ x_2 \leq 3 \\
\text{c}_4: ~~ x_2 \geq 4 \\\end{split}\]
在这个例子中，我们很容易知道 \(c_1\) 与 \(c_2\) 为一组 IIS，\(c_3\) 与 \(c_4\) 为一组 IIS。在同时移除 \(c_1\) 或 \(c_2\) 中的任意一条约束以及 \(c_3\) 或 \(c_4\) 中的任意一条约束后，该问题将变得可行。
我们将通过一个更加实际的例子，来展示如何在 MindOpt 中使用约束不可行性分析来获取 IIS。考虑如下的不可行约束系统：
\[\begin{split}\text{Constraints:} & & \\
& -0.5 x_0 + x_1 &>= 0.5 \\
& 2 x_0 - x_1 &>= 3 \\
& 3 x_0 + x_1 &<= 6 \\
& 3 x_3 - x_4 &<= 2 \\
& x_0 + x_4 &<= 10 \\
& x_0 + 2 x_1 + x_3 &<= 14 \\
& x_1 + x_3 &>= 1 \\
\text{Bounds:} & & \\
& 5 <= x_3 & \\
& 0 <= x_4 <= 2 &\end{split}\]
其中，前面三组约束构成一组IIS，而第四个约束和变量上下界则构成另外一组IIS。
Note
MindOpt 目前采用过滤算法来寻找IIS。过滤算法虽然能在短时间找出一组IIS，但无法保证IIS的规模是所有IIS组合中最小的。此外，若用户对约束顺序做调整，则 MindOpt 也可能会产生不同的IIS。
Note
实际操作上，我们建议用户修复IIS中的冲突后，再将修改后的模型输入至求解IIS的API，并修复下一个IIS；依此直至所有的冲突都得以修复。
接下来，我们将分别说明如何在 C/C++/Python 环境中应用 MindOpt 来获取不可行问题的 IIS。
5.5.1. C API: Mdo_computeIIS¶
首先，参考 C 语言的建模和优化 中的方法创建优化问题并设置参数：
96 /*------------------------------------------------------------------*/
97 /* Step 1. Create a model and change the parameters. */
98 /*------------------------------------------------------------------*/
99 printf("Step 1. Create a model and change the parameters.\n\n");
100 /* Create an empty model. */
101 MDO_CHECK_CALL(Mdo_createMdl(&model));
102 /* Turn-off the presolver so that solver won't terminate with an MDO_INF_OR_UBD status. */
103 MDO_CHECK_CALL(Mdo_setIntParam(model, MDO_INT_PARAM_PRESOLVE, 0));
104 /* Use dual-Simplex method. */
105 MDO_CHECK_CALL(Mdo_setIntParam(model, MDO_INT_PARAM_METHOD, 1));
106
107 /*------------------------------------------------------------------*/
108 /* Step 2. Input model. */
109 /*------------------------------------------------------------------*/
110 printf("\nStep 2. Input model.\n\n");
111 /* The following three input methods will all result in the same model. */
112 /* Change to minimization problem. */
113 MDO_CHECK_CALL(Mdo_setIntAttr(model, MDO_INT_ATTR_MIN_SENSE, MDO_YES));
114
115 /* Add variables. */
116 for (i = 0; i < 5; ++i)
117 {
118 MDO_CHECK_CALL(Mdo_addCol(model, lbs[i], ubs[i], objs[i], 0, NULL, NULL, col_names[i], MDO_NO));
119 }
120 /* Add two constraints.
121 * The coefficients of the constraint matrix are inputted in a row-wise order.
122 */
123 MDO_CHECK_CALL(Mdo_addRows(model, 7, lhss, rhss, csr_bgn, csr_indices, csr_values, row_names));
接下来，当优化问题不可行时，使用 Mdo_computeIIS() 获取不可约不可行子系统的行列坐标，并打印对应的约束名与变量名以及相应的状态，还可通过 Mdo_writeProb() 来将不可行系统输出到文件中进行查看：
143 case MDO_INFEASIBLE:
144 printf("Optimizer terminated with an INFEASIBLE status.\n");
145 printf("Start computing IIS.\n");
146 MDO_CHECK_CALL(Mdo_computeIIS(model));
147 printf("Writing IIS into file.\n");
148 MDO_CHECK_CALL(Mdo_writeProb(model, "./test1.ilp"));
149
150 printf("Populating all bounds participate in the computed IIS.\n");
151 for (int i = 0; i < Mdo_getNumRows(model); ++i)
152 {
153 MDO_CHECK_CALL(Mdo_getStrAttrIndex(model, MDO_STR_ATTR_ROW_NAME, i, 1024, sval));
154 MDO_CHECK_CALL(Mdo_getIntAttrIndex(model, MDO_INT_ATTR_ROW_IIS, i, &ival));
155 switch (ival)
156 {
157 case 2:
158 printf("The upper bound of inequality constraint [%s] participates in the IIS.\n", sval);
159 break;
160 case 3:
161 printf("The lower bound of inequality constraint [%s] participates in the IIS.\n", sval);
162 break;
163 case 5:
164 printf("[%s] is an equality constraint, and both its lower bound and upper bound participate in the IIS.\n", sval);
165 break;
166 }
167 }
168 for (int j = 0; j < Mdo_getNumCols(model); ++j)
169 {
170 MDO_CHECK_CALL(Mdo_getStrAttrIndex(model, MDO_STR_ATTR_COL_NAME, j, 1024, sval));
171 MDO_CHECK_CALL(Mdo_getIntAttrIndex(model, MDO_INT_ATTR_COL_IIS, j, &ival));
172 switch (ival)
173 {
174 case 2:
175 printf("The upper bound of variable [%s] participates in the IIS.\n", sval);
176 break;
177 case 3:
178 printf("The lower bound of variable [%s] participates in the IIS.\n", sval);
179 break;
180 case 5:
181 printf("[%s] is a fixed variable, and both its lower bound and upper bound participate in the IIS.\n", sval);
182 break;
183 }
184 }
185 break;
文件链接 MdoLoIIS.c 提供了完整源代码：
1/**
2 * Description
3 * -----------
4 *
5 * Linear optimization.
6 * - Compute IIS of an infeasible problem.
7 *
8 * Formulation
9 * -----------
10 *
11 * Minimize
12 * Obj:
13 * Subject To
14 * c0: -0.500000000 x0 + x1 >= 0.500000000
15 * c1: 2 x0 - x1 >= 3
16 * c2: 3 x0 + x1 <= 6
17 * c3: 3 x3 - x4 <= 2 <- conflicts with variable bounds listed below!
18 * c4: x0 + x4 <= 10
19 * c5: x0 + 2 x1 + x3 <= 14
20 * c6: x1 + x3 >= 1
21 * Bounds
22 * 5 <= x3
23 * 0 <= x4 <= 2
24 * End
25 */
26#include <stdio.h>
27#include <stdlib.h>
28#include "Mindopt.h"
29
30
31/* Macro to check the return code */
32#define MDO_CHECK_CALL(MDO_CALL) \
33 code = MDO_CALL; \
34 if (code != MDO_OKAY) \
35 { \
36 Mdo_explainResult(model, code, str); \
37 Mdo_freeMdl(&model); \
38 fprintf(stderr, "===================================\n"); \
39 fprintf(stderr, "Error : code <%d>\n", code); \
40 fprintf(stderr, "Reason : %s\n", str); \
41 fprintf(stderr, "===================================\n"); \
42 return (int)code; \
43 }
44
45int main(void)
46{
47 /* Variables. */
48 char str[1024] = { "\0" };
49 MdoMdl * model = NULL;
50 MdoResult code = MDO_OKAY;
51 MdoStatus status = MDO_UNKNOWN;
52 double val;
53 char sval[1024];
54 int ival;
55 int num_iis_rows, num_iis_cols;
56 int idx_iis_rows[7], idx_iis_cols[5];
57 int i, j;
58
59 const int csr_bgn[] = {0, 2, 4, 6, 8, 10, 13, 15};
60 const int csr_indices[] =
61 {
62 0, 1,
63 0, 1,
64 0, 1,
65 3, 4,
66 0, 4,
67 0, 1, 3,
68 1, 3
69 };
70 const double csr_values[] =
71 {
72 -0.5, 1,
73 2, -1,
74 3, 1,
75 3, -1,
76 1, 1,
77 1, 2, 1,
78 1, 1
79 };
80
81 const double lhss[] =
82 {
83 0.5, 3.0, -MDO_INFINITY, -MDO_INFINITY, -MDO_INFINITY, -MDO_INFINITY, 1.0
84 };
85 const double rhss[] =
86 {
87 MDO_INFINITY, MDO_INFINITY, 6.0, 2.0, 10.0, 14.0, MDO_INFINITY
88 };
89 const char* row_names[] = { "c0", "c1" , "c2" , "c3" , "c4" , "c5" , "c6" };
90
91 const double lbs[] = { 0.0, 0.0, 0.0, 5.0, 0.0 };
92 const double ubs[] = { MDO_INFINITY, MDO_INFINITY, MDO_INFINITY, MDO_INFINITY, 2.0 };
93 const double objs[] = { 0.0, 0.0, 0.0, 0.0, 0.0 };
94 const char* col_names[] = { "x0", "x1", "x2", "x3", "x4" };
95
96 /*------------------------------------------------------------------*/
97 /* Step 1. Create a model and change the parameters. */
98 /*------------------------------------------------------------------*/
99 printf("Step 1. Create a model and change the parameters.\n\n");
100 /* Create an empty model. */
101 MDO_CHECK_CALL(Mdo_createMdl(&model));
102 /* Turn-off the presolver so that solver won't terminate with an MDO_INF_OR_UBD status. */
103 MDO_CHECK_CALL(Mdo_setIntParam(model, MDO_INT_PARAM_PRESOLVE, 0));
104 /* Use dual-Simplex method. */
105 MDO_CHECK_CALL(Mdo_setIntParam(model, MDO_INT_PARAM_METHOD, 1));
106
107 /*------------------------------------------------------------------*/
108 /* Step 2. Input model. */
109 /*------------------------------------------------------------------*/
110 printf("\nStep 2. Input model.\n\n");
111 /* The following three input methods will all result in the same model. */
112 /* Change to minimization problem. */
113 MDO_CHECK_CALL(Mdo_setIntAttr(model, MDO_INT_ATTR_MIN_SENSE, MDO_YES));
114
115 /* Add variables. */
116 for (i = 0; i < 5; ++i)
117 {
118 MDO_CHECK_CALL(Mdo_addCol(model, lbs[i], ubs[i], objs[i], 0, NULL, NULL, col_names[i], MDO_NO));
119 }
120 /* Add two constraints.
121 * The coefficients of the constraint matrix are inputted in a row-wise order.
122 */
123 MDO_CHECK_CALL(Mdo_addRows(model, 7, lhss, rhss, csr_bgn, csr_indices, csr_values, row_names));
124
125 /*------------------------------------------------------------------*/
126 /* Step 3. Solve the problem and populate the result. */
127 /*------------------------------------------------------------------*/
128 printf("\nStep 3. Solve the problem and populate the result.\n\n");
129 /* Solve the problem. */
130 MDO_CHECK_CALL(Mdo_solveProb(model));
131 Mdo_displayResults(model);
132
133 switch (Mdo_getStatus(model))
134 {
135 case MDO_UNKNOWN:
136 printf("Optimizer terminated with an UNKNOWN status.\n");
137 break;
138 case MDO_OPTIMAL:
139 MDO_CHECK_CALL(Mdo_getRealAttr(model, MDO_REAL_ATTR_PRIMAL_OBJ_VAL, &val));
140 printf("Optimizer terminated with an OPTIMAL status.\n");
141 printf(" - Primal objective : %e.\n", val);
142 break;
143 case MDO_INFEASIBLE:
144 printf("Optimizer terminated with an INFEASIBLE status.\n");
145 printf("Start computing IIS.\n");
146 MDO_CHECK_CALL(Mdo_computeIIS(model));
147 printf("Writing IIS into file.\n");
148 MDO_CHECK_CALL(Mdo_writeProb(model, "./test1.ilp"));
149
150 printf("Populating all bounds participate in the computed IIS.\n");
151 for (int i = 0; i < Mdo_getNumRows(model); ++i)
152 {
153 MDO_CHECK_CALL(Mdo_getStrAttrIndex(model, MDO_STR_ATTR_ROW_NAME, i, 1024, sval));
154 MDO_CHECK_CALL(Mdo_getIntAttrIndex(model, MDO_INT_ATTR_ROW_IIS, i, &ival));
155 switch (ival)
156 {
157 case 2:
158 printf("The upper bound of inequality constraint [%s] participates in the IIS.\n", sval);
159 break;
160 case 3:
161 printf("The lower bound of inequality constraint [%s] participates in the IIS.\n", sval);
162 break;
163 case 5:
164 printf("[%s] is an equality constraint, and both its lower bound and upper bound participate in the IIS.\n", sval);
165 break;
166 }
167 }
168 for (int j = 0; j < Mdo_getNumCols(model); ++j)
169 {
170 MDO_CHECK_CALL(Mdo_getStrAttrIndex(model, MDO_STR_ATTR_COL_NAME, j, 1024, sval));
171 MDO_CHECK_CALL(Mdo_getIntAttrIndex(model, MDO_INT_ATTR_COL_IIS, j, &ival));
172 switch (ival)
173 {
174 case 2:
175 printf("The upper bound of variable [%s] participates in the IIS.\n", sval);
176 break;
177 case 3:
178 printf("The lower bound of variable [%s] participates in the IIS.\n", sval);
179 break;
180 case 5:
181 printf("[%s] is a fixed variable, and both its lower bound and upper bound participate in the IIS.\n", sval);
182 break;
183 }
184 }
185 break;
186 case MDO_UNBOUNDED:
187 printf("Optimizer terminated with an UNBOUNDED status.\n");
188 break;
189 case MDO_INF_OR_UBD:
190 printf("Optimizer terminated with an INFEASIBLE or UNBOUNDED status.\n");
191 break;
192 }
193
194 /*------------------------------------------------------------------*/
195 /* Step 4. Free the model. */
196 /*------------------------------------------------------------------*/
197 printf("\nStep 4. Free the model.\n");
198 /* Free the model. */
199 Mdo_freeMdl(&model);
200
201 return (int)code;
202}
5.5.2. C++ API：computeIIS¶
首先，参考 C++ 的建模和优化 中的方法创建优化问题并设置参数：
51 /* Change to minimization problem. */
52 model.setIntAttr(MDO_INT_ATTR::MIN_SENSE, MDO_YES);
53
54 /* Add variables. */
55 std::vector<MdoVar> x;
56 x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, "x0", MDO_NO));
57 x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, "x1", MDO_NO));
58 x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, "x2", MDO_NO));
59 x.push_back(model.addVar(5.0, MDO_INFINITY, 0.0, "x3", MDO_NO));
60 x.push_back(model.addVar(0.0, 2.0, 0.0, "x4", MDO_NO));
61
62 /* Add constraints. */
63 std::vector<MdoCons> cons;
64 cons.push_back(model.addCons(-0.5 * x[0] + x[1] >= 0.5, "c0"));
65 cons.push_back(model.addCons( 2.0 * x[0] - x[1] >= 3.0, "c1"));
66 cons.push_back(model.addCons( 3.0 * x[0] + x[1] <= 6.0, "c2"));
67 cons.push_back(model.addCons( 3.0 * x[3] - x[4] <= 2.0, "c3"));
68 cons.push_back(model.addCons( x[0] + x[4] <= 10.0, "c4"));
69 cons.push_back(model.addCons( x[0] + 2.0 * x[1] + x[3] <= 14.0, "c5"));
70 cons.push_back(model.addCons( x[1] + x[3] >= 1.0, "c6"));
接下来，当优化问题不可行时，使用 mindopt::MdoModel::computeIIS() 获取不可约不可行子系统的行列坐标，并打印对应的约束名与变量名以及相应的状态，还可通过 mindopt::MdoModel::writeProb() 来将不可行系统输出到文件中进行查看：
87 case MDO_INFEASIBLE:
88 std::cout << "Optimizer terminated with an INFEASIBLE status." << std::endl;
89 std::cout << "Start computing IIS." << std::endl;
90 model.computeIIS();
91 std::cout << "Writing IIS into file." << std::endl;
92 model.writeProb("./test1.ilp");
93 std::cout << "Populating all bounds participate in the computed IIS." << std::endl;
94 for (auto c : cons)
95 {
96 std::string name = c.getStrAttr(MDO_STR_ATTR::ROW_NAME);
97 switch (c.getIntAttr(MDO_INT_ATTR::ROW_IIS))
98 {
99 case 2:
100 std::cout << "The upper bound of inequality constraint [" << name << "] participates in the IIS." << std::endl;
101 break;
102 case 3:
103 std::cout << "The lower bound of inequality constraint [" << name << "] participates in the IIS." << std::endl;
104 break;
105 case 5:
106 std::cout << "[" << name << "] is an equality constraint, and both its lower bound and upper bound participate in the IIS." << std::endl;
107 break;
108 }
109 }
110 for (auto v : x)
111 {
112 std::string name = v.getStrAttr(MDO_STR_ATTR::COL_NAME);
113 switch (v.getIntAttr(MDO_INT_ATTR::COL_IIS))
114 {
115 case 2:
116 std::cout << "The upper bound of variable [" << name << "] participates in the IIS." << std::endl;
117 break;
118 case 3:
119 std::cout << "The lower bound of variable [" << name << "] participates in the IIS." << std::endl;
120 break;
121 case 5:
122 std::cout << "[" << name << "] is a fixed variable, and both its lower bound and upper bound participate in the IIS." << std::endl;
123 break;
124 }
125 }
126 break;
文件链接 MdoLoIIS.cpp 提供了完整源代码：
1/**
2 * Description
3 * -----------
4 *
5 * Linear optimization.
6 * - Compute IIS of an infeasible problem.
7 *
8 * Formulation
9 * -----------
10 *
11 * Minimize
12 * Obj:
13 * Subject To
14 * c0: -0.500000000 x0 + x1 >= 0.500000000
15 * c1: 2 x0 - x1 >= 3
16 * c2: 3 x0 + x1 <= 6
17 * c3: 3 x3 - x4 <= 2 <- conflicts with variable bounds listed below!
18 * c4: x0 + x4 <= 10
19 * c5: x0 + 2 x1 + x3 <= 14
20 * c6: x1 + x3 >= 1
21 * Bounds
22 * 5 <= x3
23 * 0 <= x4 <= 2
24 * End
25 */
26#include <iostream>
27#include <vector>
28#include "MindoptCpp.h"
29
30using namespace mindopt;
31
32int main(void)
33{
34 std::vector<int> idx_rows, idx_cols;
35
36 /*------------------------------------------------------------------*/
37 /* Step 1. Create a model and change the parameters. */
38 /*------------------------------------------------------------------*/
39 /* Create an empty model. */
40 MdoModel model;
41 /* Turn-off the presolver so that solver won't terminate with an MDO_INF_OR_UBD status. */
42 model.setIntParam(MDO_INT_PARAM::PRESOLVE, 0);
43 /* Use dual-Simplex method. */
44 model.setIntParam(MDO_INT_PARAM::METHOD, 1);
45
46 try
47 {
48 /*------------------------------------------------------------------*/
49 /* Step 2. Input model. */
50 /*------------------------------------------------------------------*/
51 /* Change to minimization problem. */
52 model.setIntAttr(MDO_INT_ATTR::MIN_SENSE, MDO_YES);
53
54 /* Add variables. */
55 std::vector<MdoVar> x;
56 x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, "x0", MDO_NO));
57 x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, "x1", MDO_NO));
58 x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, "x2", MDO_NO));
59 x.push_back(model.addVar(5.0, MDO_INFINITY, 0.0, "x3", MDO_NO));
60 x.push_back(model.addVar(0.0, 2.0, 0.0, "x4", MDO_NO));
61
62 /* Add constraints. */
63 std::vector<MdoCons> cons;
64 cons.push_back(model.addCons(-0.5 * x[0] + x[1] >= 0.5, "c0"));
65 cons.push_back(model.addCons( 2.0 * x[0] - x[1] >= 3.0, "c1"));
66 cons.push_back(model.addCons( 3.0 * x[0] + x[1] <= 6.0, "c2"));
67 cons.push_back(model.addCons( 3.0 * x[3] - x[4] <= 2.0, "c3"));
68 cons.push_back(model.addCons( x[0] + x[4] <= 10.0, "c4"));
69 cons.push_back(model.addCons( x[0] + 2.0 * x[1] + x[3] <= 14.0, "c5"));
70 cons.push_back(model.addCons( x[1] + x[3] >= 1.0, "c6"));
71
72 /*------------------------------------------------------------------*/
73 /* Step 3. Solve the problem and populate the result. */
74 /*------------------------------------------------------------------*/
75 /* Solve the problem. */
76 model.solveProb();
77 model.displayResults();
78
79 switch (model.getStatus())
80 {
81 case MDO_UNKNOWN:
82 std::cout << "Optimizer terminated with an UNKNOWN status." << std::endl;
83 break;
84 case MDO_OPTIMAL:
85 std::cout << "Optimizer terminated with an OPTIMAL status." << std::endl;
86 break;
87 case MDO_INFEASIBLE:
88 std::cout << "Optimizer terminated with an INFEASIBLE status." << std::endl;
89 std::cout << "Start computing IIS." << std::endl;
90 model.computeIIS();
91 std::cout << "Writing IIS into file." << std::endl;
92 model.writeProb("./test1.ilp");
93 std::cout << "Populating all bounds participate in the computed IIS." << std::endl;
94 for (auto c : cons)
95 {
96 std::string name = c.getStrAttr(MDO_STR_ATTR::ROW_NAME);
97 switch (c.getIntAttr(MDO_INT_ATTR::ROW_IIS))
98 {
99 case 2:
100 std::cout << "The upper bound of inequality constraint [" << name << "] participates in the IIS." << std::endl;
101 break;
102 case 3:
103 std::cout << "The lower bound of inequality constraint [" << name << "] participates in the IIS." << std::endl;
104 break;
105 case 5:
106 std::cout << "[" << name << "] is an equality constraint, and both its lower bound and upper bound participate in the IIS." << std::endl;
107 break;
108 }
109 }
110 for (auto v : x)
111 {
112 std::string name = v.getStrAttr(MDO_STR_ATTR::COL_NAME);
113 switch (v.getIntAttr(MDO_INT_ATTR::COL_IIS))
114 {
115 case 2:
116 std::cout << "The upper bound of variable [" << name << "] participates in the IIS." << std::endl;
117 break;
118 case 3:
119 std::cout << "The lower bound of variable [" << name << "] participates in the IIS." << std::endl;
120 break;
121 case 5:
122 std::cout << "[" << name << "] is a fixed variable, and both its lower bound and upper bound participate in the IIS." << std::endl;
123 break;
124 }
125 }
126 break;
127 case MDO_UNBOUNDED:
128 std::cout << "Optimizer terminated with an UNBOUNDED status." << std::endl;
129 break;
130 case MDO_INF_OR_UBD:
131 std::cout << "Optimizer terminated with an INFEASIBLE or UNBOUNDED status." << std::endl;
132 break;
133 }
134 }
135 catch (MdoException & e)
136 {
137 std::cerr << "===================================" << std::endl;
138 std::cerr << "Error : code <" << e.getResult() << ">" << std::endl;
139 std::cerr << "Reason : " << model.explainResult(e.getResult()) << std::endl;
140 std::cerr << "===================================" << std::endl;
141
142 return static_cast<int>(e.getResult());
143 }
144
145 return static_cast<int>(MDO_OKAY);
146}
5.5.3. Python API: compute_iis¶
首先，参考 Python 的建模与优化 中的方法创建优化问题并设置参数：
43 # Change to minimization problem.
44 model.set_int_attr(MDO_INT_ATTR.MIN_SENSE, 1)
45
46 # Add variables.
47 # Note that the nonzero elements are inputted in a column-wise order here.
48 x = []
49 x.append(model.add_var(0.0, MDO_INFINITY, 0.0, None, "x0", False))
50 x.append(model.add_var(0.0, MDO_INFINITY, 0.0, None, "x1", False))
51 x.append(model.add_var(0.0, MDO_INFINITY, 0.0, None, "x2", False))
52 x.append(model.add_var(5.0, MDO_INFINITY, 0.0, None, "x3", False))
53 x.append(model.add_var(0.0, 2.0, 0.0, None, "x4", False))
54
55 # Add constraints.
56 # Note that the nonzero elements are inputted in a row-wise order here.
57 conss = []
58 conss.append(model.add_cons(-0.5 * x[0] + x[1] >= 0.5, "c0"))
59 conss.append(model.add_cons( 2.0 * x[0] - x[1] >= 3.0, "c1"))
60 conss.append(model.add_cons( 3.0 * x[0] + x[1] <= 6.0, "c2"))
61 conss.append(model.add_cons( 3.0 * x[3] - x[4] <= 2.0, "c3"))
62 conss.append(model.add_cons( x[0] + x[4] <= 10.0, "c4"))
63 conss.append(model.add_cons( x[0] + 2.0 * x[1] + x[3] <= 14.0, "c5"))
64 conss.append(model.add_cons( x[1] + x[3] >= 1.0, "c6"))
接下来，当优化问题不可行时，使用 mindoptpy.MdoModel.compute_iis() 获取不可约不可行子系统的行列坐标，并打印对应的约束名与变量名以及相应的状态，还可通过 mindoptpy.MdoModel.write_prob() 来将不可行系统输出到文件中进行查看：
71 if status_msg == "INFEASIBLE":
72 print("Optimizer terminated with an MDO_INFEASIBLE status (code {0}).".format(status_code))
73 print("Start computing IIS.")
74 model.compute_iis();
75 print("Writing IIS into file.")
76 model.write_prob("./test1.ilp");
77 print("Populating all bounds participate in the computed IIS.")
78 for c in conss:
79 status = c.get_int_attr(MDO_INT_ATTR.ROW_IIS)
80 name = c.get_str_attr(MDO_STR_ATTR.ROW_NAME)
81 if status == 2:
82 print(f"The upper bound of inequality constraint [{name}] participates in the IIS.")
83 elif status == 3:
84 print(f"The lower bound of inequality constraint [{name}] participates in the IIS.")
85 elif status == 5:
86 print(f"[{name}] is an equality constraint, and both its lower bound and upper bound participate in the IIS.")
87 for v in x:
88 status = v.get_int_attr(MDO_INT_ATTR.COL_IIS)
89 name = v.get_str_attr(MDO_STR_ATTR.COL_NAME)
90 if status == 2:
91 print(f"The upper bound of variable [{name}] participates in the IIS.")
92 elif status == 3:
93 print(f"The lower bound of variable [{name}] participates in the IIS.")
94 elif status == 5:
95 print(f"[{name}] is a fixed variable, and both its lower bound and upper bound participate in the IIS.")
96 else:
97 print("Optimizer terminated with a(n) {0} status (code {1}).".format(status_msg, status_code))
文件链接 mdo_lo_iis.py 提供了完整源代码：
1"""
2/**
3 * Description
4 * -----------
5 *
6 * Linear optimization.
7 * - Compute IIS of an infeasible problem.
8 *
9 * Formulation
10 * -----------
11 *
12 * Minimize
13 * Obj:
14 * Subject To
15 * c0: -0.500000000 x0 + x1 >= 0.500000000
16 * c1: 2 x0 - x1 >= 3
17 * c2: 3 x0 + x1 <= 6
18 * c3: 3 x3 - x4 <= 2 <- conflit with variable bounds below!
19 * c4: x0 + x4 <= 10
20 * c5: x0 + 2 x1 + x3 <= 14
21 * c6: x1 + x3 >= 1
22 * Bounds
23 * 5 <= x3
24 * 0 <= x4 <= 2
25 * End
26 */
27"""
28from mindoptpy import *
29
30
31if __name__ == "__main__":
32
33 MDO_INFINITY = MdoModel.get_infinity()
34
35 # Step 1. Create a model and change the parameters.
36 model = MdoModel()
37 # Turn-off the presolver so that solver won't terminate with an MDO_INF_OR_UBD status.
38 model.set_int_param(MDO_INT_PARAM.PRESOLVE, 0)
39 model.set_int_param(MDO_INT_PARAM.METHOD, 1)
40
41 try:
42 # Step 2. Input model.
43 # Change to minimization problem.
44 model.set_int_attr(MDO_INT_ATTR.MIN_SENSE, 1)
45
46 # Add variables.
47 # Note that the nonzero elements are inputted in a column-wise order here.
48 x = []
49 x.append(model.add_var(0.0, MDO_INFINITY, 0.0, None, "x0", False))
50 x.append(model.add_var(0.0, MDO_INFINITY, 0.0, None, "x1", False))
51 x.append(model.add_var(0.0, MDO_INFINITY, 0.0, None, "x2", False))
52 x.append(model.add_var(5.0, MDO_INFINITY, 0.0, None, "x3", False))
53 x.append(model.add_var(0.0, 2.0, 0.0, None, "x4", False))
54
55 # Add constraints.
56 # Note that the nonzero elements are inputted in a row-wise order here.
57 conss = []
58 conss.append(model.add_cons(-0.5 * x[0] + x[1] >= 0.5, "c0"))
59 conss.append(model.add_cons( 2.0 * x[0] - x[1] >= 3.0, "c1"))
60 conss.append(model.add_cons( 3.0 * x[0] + x[1] <= 6.0, "c2"))
61 conss.append(model.add_cons( 3.0 * x[3] - x[4] <= 2.0, "c3"))
62 conss.append(model.add_cons( x[0] + x[4] <= 10.0, "c4"))
63 conss.append(model.add_cons( x[0] + 2.0 * x[1] + x[3] <= 14.0, "c5"))
64 conss.append(model.add_cons( x[1] + x[3] >= 1.0, "c6"))
65
66 # Step 3. Solve the problem and populate the result.
67 model.solve_prob()
68 model.display_results()
69
70 status_code, status_msg = model.get_status()
71 if status_msg == "INFEASIBLE":
72 print("Optimizer terminated with an MDO_INFEASIBLE status (code {0}).".format(status_code))
73 print("Start computing IIS.")
74 model.compute_iis();
75 print("Writing IIS into file.")
76 model.write_prob("./test1.ilp");
77 print("Populating all bounds participate in the computed IIS.")
78 for c in conss:
79 status = c.get_int_attr(MDO_INT_ATTR.ROW_IIS)
80 name = c.get_str_attr(MDO_STR_ATTR.ROW_NAME)
81 if status == 2:
82 print(f"The upper bound of inequality constraint [{name}] participates in the IIS.")
83 elif status == 3:
84 print(f"The lower bound of inequality constraint [{name}] participates in the IIS.")
85 elif status == 5:
86 print(f"[{name}] is an equality constraint, and both its lower bound and upper bound participate in the IIS.")
87 for v in x:
88 status = v.get_int_attr(MDO_INT_ATTR.COL_IIS)
89 name = v.get_str_attr(MDO_STR_ATTR.COL_NAME)
90 if status == 2:
91 print(f"The upper bound of variable [{name}] participates in the IIS.")
92 elif status == 3:
93 print(f"The lower bound of variable [{name}] participates in the IIS.")
94 elif status == 5:
95 print(f"[{name}] is a fixed variable, and both its lower bound and upper bound participate in the IIS.")
96 else:
97 print("Optimizer terminated with a(n) {0} status (code {1}).".format(status_msg, status_code))
98
99 except MdoError as e:
100 print("Received Mindopt exception.")
101 print(" - Code : {}".format(e.code))
102 print(" - Reason : {}".format(e.message))
103 except Exception as e:
104 print("Received exception.")
105 print(" - Explanation : {}".format(e))
106 finally:
107 # Step 4. Free the model.
108 model.free_mdl()