5.2.8. General Constraints in MILP¶
Apart from the linear constraints, MindOpt also supports Special-Ordered Set Constraint (SOS) and Indicator Constraint.
5.2.8.1. Special-Ordered Set Constraint (SOS)¶
SOS constraints are special constraints that impose restrictions on the values of a group of variables, which can be either integer or continuous variables. Specifically, SOS constraints consist of two types: SOS1 and SOS2. SOS1 constraint allows at most one variable in a group to have a non-zero value. SOS2 constraint allows at most two variables in a group to have non-zero values, and the non-zero variables must be adjacent to each other within the group.
When introducing SOS constraints in MindOpt, users can distinguish between SOS1 and SOS2 constraints by specifying the SOS constraint type. MDO_SOS_TYPE1 represents SOS1, while MDO_SOS_TYPE2 represents SOS2. Calling methods in different programming languages are listed as follows:
Language |
API |
C |
|
JAVA |
|
Python |
|
Taking C language for example, to introduce an SOS1 constraint that allows at most 1 variable among \(x_0\) and \(x_1\) to be non-zero, and an SOS2 constraint that allows at most 2 variables among \(x_1\), \(x_2\) and \(x_3\) to be non-zero:
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));
Complete example codes are provided in 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¶
An indicator constraint is a logical constraint that controls whether a linear constraint is active or not by introducing a binary variable. For example, \(y\) is an indicator binary variable, and then the indicator constraint \(y=1 \rightarrow x_1 + x_2 + x_3 \geq 2\) states that if \(y = 1\) then the linear constraint \(x_1 + x_2 + x_3 \geq 2\) has to be satisfied, otherwise, the constraint can be violated. Note that, we can also require the constraint to be satisfied when the the binary indicator variable is equal to zero, like \(z=0 \rightarrow w_1 + w_2 \leq 1\).
APIs for different languages are listed as follows:
Language |
API |
C |
|
CPP |
|
JAVA |
|
Python |
Taking C language for example, to introduce two indicator constraints, \(y_0=1 \rightarrow x_0 + x_1 + x_3 \geq 2\) and \(y_1=1 \rightarrow x_1 + x_2 + x_3 \geq 3\), and require that \(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));
Complete example codes are provided in 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}