5.2.8. MILP的特殊约束¶
除了常见的线性约束外， MindOpt 还支持SOS约束（Special-Ordered Set Constraint）和指示符约束（Indicator Constraint）。
5.2.8.1. SOS约束¶
SOS约束是对一组变量的取值进行限制的特殊约束，这些变量可以是整数变量或连续变量。具体地，SOS约束包括SOS1约束和SOS2约束：SOS1约束要求一组变量中至多有1个变量的取值不为零，SOS2约束要求一组变量中至多有2个变量的取值不为零、且非零取值的变量必须是相邻变量。
用户在引入 MindOpt 的SOS约束时，可以通过指定SOS约束类型区分SOS1约束和SOS2约束， MDO_SOS_TYPE1 表示SOS1， MDO_SOS_TYPE2 表示SOS2。不同编程语言的方法如下：
编程语言 |
方法 |
C |
|
CPP |
|
JAVA |
|
Python |
以C语言为例，引入SOS1约束，要求 \(x_0\) 与 \(x_1\) 至多1个变量不为零，引入SOS2约束，要求 \(x_1\)、 \(x_2\) 、 \(x_3\) 至多1个变量不为零：
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 SOS constraints.
78 * sos1: x0, x1
79 * sos2: x1, x2, x3
80 */
81 int sos_cons_num = 2; // The number of SOS constraints to be added.
82 int sos_var_num = 5; // The total number of variables associated with new constraints.
83 int sos_types[] = {MDO_SOS_TYPE1, MDO_SOS_TYPE2}; // The SOS type for each new SOS constraint.
84 int sos_begin[] = {0, 2}; // The list beginning indices for each SOS constraint.
85 int sos_var_idx[] = {0, 1, 1, 2, 3}; // The variable indices associated with new SOS constraints.
86 double sos_var_weight[] = {1, 2, 3, 4, 5}; // Weights for each participating variable.
87 CHECK_RESULT(MDOaddsos(m, sos_cons_num, sos_var_num, sos_types, sos_begin, sos_var_idx, sos_var_weight));
完整源代码请参考 MdoMiloSOS.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 SOS constraints.
78 * sos1: x0, x1
79 * sos2: x1, x2, x3
80 */
81 int sos_cons_num = 2; // The number of SOS constraints to be added.
82 int sos_var_num = 5; // The total number of variables associated with new constraints.
83 int sos_types[] = {MDO_SOS_TYPE1, MDO_SOS_TYPE2}; // The SOS type for each new SOS constraint.
84 int sos_begin[] = {0, 2}; // The list beginning indices for each SOS constraint.
85 int sos_var_idx[] = {0, 1, 1, 2, 3}; // The variable indices associated with new SOS constraints.
86 double sos_var_weight[] = {1, 2, 3, 4, 5}; // Weights for each participating variable.
87 CHECK_RESULT(MDOaddsos(m, sos_cons_num, sos_var_num, sos_types, sos_begin, sos_var_idx, sos_var_weight));
88
89 /*------------------------------------------------------------------*/
90 /* Step 3. Solve the problem and populate optimization result. */
91 /*------------------------------------------------------------------*/
92 /* Solve the problem. */
93 CHECK_RESULT(MDOoptimize(m));
94 CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
95 if (status == MDO_OPTIMAL)
96 {
97 CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
98 printf("The optimal objective value is %f\n", obj);
99 for (int i = 0; i < 4; ++i)
100 {
101 CHECK_RESULT(MDOgetdblattrelement(m, X, i, &x));
102 printf("x[%d] = %f\n", i, x);
103 }
104 }
105 else
106 {
107 printf("No feasible solution.\n");
108 }
109
110 /*------------------------------------------------------------------*/
111 /* Step 4. Free the model. */
112 /*------------------------------------------------------------------*/
113 RELEASE_MEMORY;
114
115 return 0;
116}
5.2.8.2. 指示符约束（Indicator Constraint）¶
指示符约束是通过引入二进制变量控制线性约束是否生效的一种逻辑约束。例如， \(y\) 是二进制变量，指示符约束 \(y=1 \rightarrow x_1 + x_2 + x_3 \geq 2\) 表示当 \(y = 1\) 则约束 \(x_1 + x_2 + x_3 \geq 2\) 生效，否则该约束不起作用。注意，也可以令二进制变量取零时约束生效，例如， \(z=0 \rightarrow w_1 + w_2 \leq 1\) 。
不同编程语言添加指示符约束的API如下：
编程语言 |
方法 |
C |
|
CPP |
|
JAVA |
|
Python |
以C语言为例，引入指示符约束 \(y_0=1 \rightarrow x_0 + x_1 + x_3 \geq 2\) 以及 \(y_1=1 \rightarrow x_1 + x_2 + x_3 \geq 3\)，并要求 \(y_0 + y_1 \geq 1\)：
82 /* Add variables. */
83 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, 10.0, MDO_CONTINUOUS, "x0"));
84 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 2.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x1"));
85 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x2"));
86 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x3"));
87 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 0.0, 0, MDO_INFINITY, MDO_BINARY, "y0"));
88 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 0.0, 0, MDO_INFINITY, MDO_BINARY, "y1"));
89
90 /* Add constraints. */
91 CHECK_RESULT(MDOaddconstr(m, row0_nvars, row0_idx, row0_val, MDO_GREATER_EQUAL, 1.0, "c0"));
92
93 /* Add indicator constraints. */
94 CHECK_RESULT(MDOaddgenconstrIndicator(m, "ic1", indVar1, indVal1, ind1_nvars, ind1_idx, ind1_val, MDO_GREATER_EQUAL, 2.0));
95 CHECK_RESULT(MDOaddgenconstrIndicator(m, "ic2", indVar2, indVal2, ind2_nvars, ind2_idx, ind2_val, MDO_GREATER_EQUAL, 3.0));
完整源代码请参考 MdoMiloIndicator.c
1#include <stdio.h>
2#include "Mindopt.h"
3#include <stdlib.h>
4/**
5 * Description
6 * -----------
7 *
8 * Mixed Integer Linear optimization (row-wise input).
9 *
10 * Formulation
11 * -----------
12 *
13 * Minimize
14 * obj: 1 x0 + 2 x1 + 1 x2 + 1 x3
15 * Subject To
16 * c0 : y0 + y1 >= 1
17 * ic1 : y0 = 1 -> x0 + x1 + x3 >= 2
18 * ic2 : y1 = 1 -> x1 + x2 + x3 >= 3
19 * Bounds
20 * 0 <= x0 <= 10
21 * 0 <= x1
22 * 0 <= x2
23 * 0 <= x3
24 * 0 <= y0
25 * 0 <= y1
26 * Integers
27 * y0 y1
28 * End
29 */
30
31#include <stdio.h>
32#include <stdlib.h>
33#include "Mindopt.h"
34
35/* Macro to check the return code */
36#define RELEASE_MEMORY \
37 MDOfreemodel(m); \
38 MDOfreeenv(env);
39#define CHECK_RESULT(code) { int res = code; if (res != 0) { fprintf(stderr, "Bad code: %d\n", res); RELEASE_MEMORY; exit(res); } }
40#define MODEL_NAME "MILP_Indicator"
41#define MODEL_SENSE "ModelSense"
42#define STATUS "Status"
43#define OBJ_VAL "ObjVal"
44#define X "X"
45
46int main(void)
47{
48 /* Creat Model. */
49 MDOenv *env;
50 MDOmodel *m;
51 double obj, x;
52 int status, i;
53
54 /* Model data. */
55 int row0_nvars = 2;
56 int row0_idx[] = { 4, 5};
57 double row0_val[] = { 1.0, 1.0}; // y0 + y1
58
59 int indVar1 = 4; // y0
60 int indVal1 = 1; // y0 = 1
61 int ind1_nvars = 3;
62 int ind1_idx[] = {0, 1, 3};
63 double ind1_val[] = {1.0, 1.0, 1.0};
64
65 int indVar2 = 5; // y1
66 int indVal2 = 1; // y1 = 1
67 int ind2_nvars = 3;
68 int ind2_idx[] = {1, 2, 3};
69 double ind2_val[] = {1,0, 1.0, 1.0};
70
71 /*------------------------------------------------------------------*/
72 /* Step 1. Create environment and model. */
73 /*------------------------------------------------------------------*/
74 /* Create an empty model. */
75 CHECK_RESULT(MDOemptyenv(&env));
76 CHECK_RESULT(MDOstartenv(env));
77 CHECK_RESULT(MDOnewmodel(env, &m, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
78
79 /*------------------------------------------------------------------*/
80 /* Step 2. Input model. */
81 /*------------------------------------------------------------------*/
82 /* Change to minimization problem. */
83 CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MINIMIZE));
84
85 /* Add variables. */
86 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, 10.0, MDO_CONTINUOUS, "x0"));
87 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 2.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x1"));
88 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x2"));
89 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x3"));
90 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 0.0, 0, MDO_INFINITY, MDO_BINARY, "y0"));
91 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 0.0, 0, MDO_INFINITY, MDO_BINARY, "y1"));
92
93 /* Add constraints. */
94 CHECK_RESULT(MDOaddconstr(m, row0_nvars, row0_idx, row0_val, MDO_GREATER_EQUAL, 1.0, "c0"));
95
96 /* Add indicator constraints. */
97 CHECK_RESULT(MDOaddgenconstrIndicator(m, "ic1", indVar1, indVal1, ind1_nvars, ind1_idx, ind1_val, MDO_GREATER_EQUAL, 2.0));
98 CHECK_RESULT(MDOaddgenconstrIndicator(m, "ic2", indVar2, indVal2, ind2_nvars, ind2_idx, ind2_val, MDO_GREATER_EQUAL, 3.0));
99
100 /*------------------------------------------------------------------*/
101 /* Step 3. Solve the problem and populate optimization result. */
102 /*------------------------------------------------------------------*/
103 CHECK_RESULT(MDOoptimize(m));
104 CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
105 if (status == MDO_OPTIMAL)
106 {
107 CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
108 printf("The optimal objective value is %f\n", obj);
109
110 for (i = 0; i < 6; ++i)
111 {
112 CHECK_RESULT(MDOgetdblattrelement(m, X, i, &x));
113 printf("x%d = %f\n", i, x);
114 }
115 }
116 else
117 {
118 printf("No feasible solution exists\n");
119 }
120
121 /*------------------------------------------------------------------*/
122 /* Step 4. Free the model. */
123 /*------------------------------------------------------------------*/
124 RELEASE_MEMORY;
125
126 return 0;
127}