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约束,要求 x0x1 至多1个变量不为零,引入SOS2约束,要求 x1x2x3 至多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=1x1+x2+x32 表示当 y=1 则约束 x1+x2+x32 生效,否则该约束不起作用。注意,也可以令二进制变量取零时约束生效,例如, z=0w1+w21

不同编程语言添加指示符约束的API如下:

以C语言为例,引入指示符约束 y0=1x0+x1+x32 以及 y1=1x1+x2+x33,并要求 y0+y11

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}