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.
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_SOS"
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 SOS constraints.
79 * sos1: x0, x1
80 * sos2: x1, x2, x3
81 */
82 int sos_cons_num = 2; // The number of SOS constraints to be added.
83 int sos_var_num = 5; // The total number of variables associated with new constraints.
84 int sos_types[] = {MDO_SOS_TYPE1, MDO_SOS_TYPE2}; // The SOS type for each new SOS constraint.
85 int sos_begin[] = {0, 2}; // The list beginning indices for each SOS constraint.
86 int sos_var_idx[] = {0, 1, 1, 2, 3}; // The variable indices associated with new SOS constraints.
87 double sos_var_weight[] = {1, 2, 3, 4, 5}; // Weights for each participating variable.
88 CHECK_RESULT(MDOaddsos(m, sos_cons_num, sos_var_num, sos_types, sos_begin, sos_var_idx, sos_var_weight));
89
90 /*------------------------------------------------------------------*/
91 /* Step 3. Solve the problem. */
92 /*------------------------------------------------------------------*/
93 /* Solve the problem. */
94 CHECK_RESULT(MDOoptimize(m));
95
96 /*------------------------------------------------------------------*/
97 /* Step 4. Retrive model status and objective. */
98 /* For MIP(MILP,MIQP, MIQCP) problems, if the solving process */
99 /* terminates early due to reasons such as timeout or interruption, */
100 /* the model status will indicate termination by timeout (or */
101 /* interruption, etc.). However, suboptimal solutions may still */
102 /* exist, making it necessary to check the SolCount property. */
103 /*------------------------------------------------------------------*/
104 CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
105 CHECK_RESULT(MDOgetintattr(m, SOL_COUNT, &solcount));
106 if (status == MDO_OPTIMAL || status == MDO_SUB_OPTIMAL || solcount != 0)
107 {
108 CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
109 printf("The optimal objective value is %f\n", obj);
110 for (int i = 0; i < 4; ++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.\n");
119 }
120
121 /*------------------------------------------------------------------*/
122 /* Step 4. Free the model. */
123 /*------------------------------------------------------------------*/
124 RELEASE_MEMORY;
125
126 return 0;
127}
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));
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 SOL_COUNT "SolCount"
43#define STATUS "Status"
44#define OBJ_VAL "ObjVal"
45#define X "X"
46
47int main(void)
48{
49 /* Creat Model. */
50 MDOenv *env;
51 MDOmodel *m;
52 double obj, x;
53 int i, solcount, status;
54
55 /* Model data. */
56 int row0_nvars = 2;
57 int row0_idx[] = { 4, 5};
58 double row0_val[] = { 1.0, 1.0}; // y0 + y1
59
60 int indVar1 = 4; // y0
61 int indVal1 = 1; // y0 = 1
62 int ind1_nvars = 3;
63 int ind1_idx[] = {0, 1, 3};
64 double ind1_val[] = {1.0, 1.0, 1.0};
65
66 int indVar2 = 5; // y1
67 int indVal2 = 1; // y1 = 1
68 int ind2_nvars = 3;
69 int ind2_idx[] = {1, 2, 3};
70 double ind2_val[] = {1,0, 1.0, 1.0};
71
72 /*------------------------------------------------------------------*/
73 /* Step 1. Create environment and model. */
74 /*------------------------------------------------------------------*/
75 /* Create an empty model. */
76 CHECK_RESULT(MDOemptyenv(&env));
77 CHECK_RESULT(MDOstartenv(env));
78 CHECK_RESULT(MDOnewmodel(env, &m, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
79
80 /*------------------------------------------------------------------*/
81 /* Step 2. Input model. */
82 /*------------------------------------------------------------------*/
83 /* Change to minimization problem. */
84 CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MINIMIZE));
85
86 /* Add variables. */
87 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, 10.0, MDO_CONTINUOUS, "x0"));
88 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 2.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x1"));
89 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x2"));
90 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x3"));
91 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 0.0, 0, MDO_INFINITY, MDO_BINARY, "y0"));
92 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 0.0, 0, MDO_INFINITY, MDO_BINARY, "y1"));
93
94 /* Add constraints. */
95 CHECK_RESULT(MDOaddconstr(m, row0_nvars, row0_idx, row0_val, MDO_GREATER_EQUAL, 1.0, "c0"));
96
97 /* Add indicator constraints. */
98 CHECK_RESULT(MDOaddgenconstrIndicator(m, "ic1", indVar1, indVal1, ind1_nvars, ind1_idx, ind1_val, MDO_GREATER_EQUAL, 2.0));
99 CHECK_RESULT(MDOaddgenconstrIndicator(m, "ic2", indVar2, indVal2, ind2_nvars, ind2_idx, ind2_val, MDO_GREATER_EQUAL, 3.0));
100
101 /*------------------------------------------------------------------*/
102 /* Step 3. Solve the problem and populate optimization result. */
103 /*------------------------------------------------------------------*/
104 CHECK_RESULT(MDOoptimize(m));
105
106 /*------------------------------------------------------------------*/
107 /* Step 4. Retrive model status and objective. */
108 /* For MIP(MILP,MIQP, MIQCP) problems, if the solving process */
109 /* terminates early due to reasons such as timeout or interruption, */
110 /* the model status will indicate termination by timeout (or */
111 /* interruption, etc.). However, suboptimal solutions may still */
112 /* exist, making it necessary to check the SolCount property. */
113 /*------------------------------------------------------------------*/
114 CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
115 CHECK_RESULT(MDOgetintattr(m, SOL_COUNT, &solcount));
116 if (status == MDO_OPTIMAL || status == MDO_SUB_OPTIMAL || solcount != 0)
117 {
118 CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
119 printf("The optimal objective value is %f\n", obj);
120
121 for (i = 0; i < 6; ++i)
122 {
123 CHECK_RESULT(MDOgetdblattrelement(m, X, i, &x));
124 printf("x%d = %f\n", i, x);
125 }
126 }
127 else
128 {
129 printf("No feasible solution exists\n");
130 }
131
132 /*------------------------------------------------------------------*/
133 /* Step 4. Free the model. */
134 /*------------------------------------------------------------------*/
135 RELEASE_MEMORY;
136
137 return 0;
138}