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

MDOaddsos()

CPP

MDOModel::addSOS()

JAVA

MDOModel.addSOS

Python

Model.addSOS()

以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.

完整源代码请参考 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)

指示符约束是通过引入二进制变量控制线性约束是否生效的一种逻辑约束。例如, \(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

MDOaddgenconstrIndicator()

CPP

MDOModel::addGenConstrIndicator

JAVA

MDOModel.addGenConstrIndicator

Python

Model.addGenConstrIndicator()

以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));

完整源代码请参考 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}