6.1. 不可约不一致子系统(IIS)

在对实际应用问题进行建模求解的过程中,经常会遇到问题不可行的情况,而不可行问题必然是由某些约束及变量边界互相之间冲突导致的;如何分析问题的不可行性并识别出导致冲突的关键约束及变量边界成为求解器应用的重要一环。

给定一个不可行问题,一组相互冲突的约束和变量边界的最小集合被称为 不可约不一致子系统 (Irreducible Inconsistent Subsystem, IIS)。IIS具有两个特征:(1)不可约,即任意移除某条约束或变量边界后子系统变得可行;(2)不一致,即子系统本身是不可行的。

用户可以使用 MindOpt 的IIS计算功能找到不可行问题中一组相互冲突的约束或变量边界,并修正或移除原问题中的这些约束或变量边界,进而使问题变得可行。需要注意的是,当一个不可行问题包含多组 IIS时,用户需要消除所有IIS,才能使其变得可行。例如:

c1:  x11c2:  x12c3:  x23c4:  x24

在这个例子中,c1c2 为一组 IIS,c3c4 为另一组 IIS。在同时移除 c1c2 中的任意一条约束以及 c3c4 中的任意一条约束后,才能让该问题将变得可行。

以下我们将通过一个更加实际的例子,来展示如何利用 MindOpt 获取不可行问题的IIS。考虑如下的不可行问题:

Constraints:0.5x0+x1>=0.52x0x1>=33x0+x1<=63x3x4<=2x0+x4<=10x0+2x1+x3<=14x1+x3>=1Bounds:5<=x30<=x4<=2

其中,前面三组约束构成一组IIS,而第四个约束和变量边界则构成另外一组IIS。

Note

MindOpt 目前采用过滤算法来寻找IIS。过滤算法虽然能在短时间找出一组IIS,但无法保证IIS的规模是所有IIS组合中最小的。此外,若用户对约束顺序做调整,则 MindOpt 也可能会产生不同的IIS。

Note

实际使用时,如果在修复一个IIS后问题仍然不可行,用户可以对修改后的模型重新求解IIS,并修复下一个IIS,如此重复直至修复所有冲突,得到可行的问题。

由于IIS求解可能非常耗时,当求解过程被中断时, MindOpt 将返回当前找到的不可行子系统,该子系统可能不满足不可约性。

IIS求解完成后, MindOpt 提供将IIS写到 .ilp 文件的方法,便于用户查看。该文件格式同 .lp 文件,目标函数为空,内容是构成IIS的约束与变量边界。

MindOpt 也支持用户通过约束的 IISConstr (或 IISRow) 属性以及变量的 IISVar (或 IISCol) 属性判断指定约束或变量边界是否属于当前求得的IIS。

接下来,我们将分别说明如何在 C/C++/Python 环境中应用 MindOpt 来获取不可行问题的 IIS。

6.1.1. C 的IIS计算

首先,参考 C 的LP建模和优化 中的方法创建优化问题并设置参数:

 89    /* Create and start environment. */
 90    MDOemptyenv(&env);
 91    MDOstartenv(env);
 92
 93    /* Create optimization model with variables. */
 94    CHECK_RESULT(MDOnewmodel(env, &m, MODEL_NAME, NCOLS, obj, lb, ub, NULL, colname));
 95
 96    /* Input constraints. */
 97    CHECK_RESULT(MDOaddrangeconstrs(m, NROWS, cbeg[NROWS], cbeg, cind, cval, lhs, rhs, rowname));
 98
 99    /* Specify objective sense. */
100    CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MINIMIZE));
101    
102    /* Optimize the input problem. */
103    CHECK_RESULT(MDOoptimize(m));

接下来,当优化问题不可行时,使用 computeIIS() 来计算IIS,再使用 MDOwrite() 可以将求得的IIS写到文件,并通过约束的 IISConstr (或 IISRow) 属性以及变量的 IISVar (或 IISCol) 属性来打印 IIS的行列坐标:

107    /* Populate optimziation result. */
108    CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
109    if (status == MDO_INFEASIBLE || status == MDO_INF_OR_UBD) 
110    {
111        printf("Optimizer terminated with an primal infeasible status.\n");
112        printf("Start to compute an Irreducible Inconsistent Subsystem (IIS).\n");
113        /* Compute an IIS and write the result into file (in ILP format). */
114        CHECK_RESULT(MDOcomputeIIS(m));
115        printf("Writing IIS into file (ILP format).\n");
116        CHECK_RESULT(MDOwrite(m, "./test1.ilp"));
117        /* Populate the computed IIS. */
118        printf("Populating all variable/constraint bounds participate in the computed IIS.\n");
119        CHECK_RESULT(MDOgetintattrarray(m, IISROW, 0, NROWS, &(*ival)));
120        for (i = 0; i < NROWS; ++i)
121        {
122            switch (ival[i])
123            {
124            case 2:
125                printf("The upper bound of inequality constraint [%s] participates in the IIS.\n", rowname[i]);
126                break;
127            case 3:
128                printf("The lower bound of inequality constraint [%s] participates in the IIS.\n", rowname[i]);
129                break;
130            case 5:
131                printf("[%s] is an equality constraint, and both its lower bound and upper bound participate in the IIS.\n", rowname[i]);
132                break;
133            }
134        }
135        CHECK_RESULT(MDOgetintattrarray(m, IISCOL, 0, NCOLS, &(*ival)));
136        for (j = 0; j < NCOLS; ++j)
137        {
138            switch (ival[j])
139            {
140            case 2:
141                printf("The upper bound of variable [%s] participates in the IIS.\n", colname[j]);
142                break;
143            case 3:
144                printf("The lower bound of variable [%s] participates in the IIS.\n", colname[j]);
145                break;
146            case 5:
147                printf("[%s] is a fixed variable, and both its lower bound and upper bound participate in the IIS.\n", colname[j]);
148                break;
149            }
150        }
151    }

示例 MdoLoIIS.c 提供了完整源代码:

  1/**
  2 *  Description
  3 *  -----------
  4 *
  5 *  Linear optimization.
  6 *   - Compute IIS of an infeasible problem.
  7 *
  8 *  Formulation
  9 *  -----------
 10 *
 11 *  Minimize
 12 *  Obj:
 13 *  Subject To
 14 *  c0:  -0.500000000 x0 + x1 >= 0.500000000
 15 *  c1:  2 x0 - x1 >= 3
 16 *  c2:  3 x0 + x1 <= 6
 17 *  c3:  3 x3 - x4 <= 2 <- conflicts with variable bounds listed below!
 18 *  c4:  x0 + x4 <= 10
 19 *  c5:  x0 + 2 x1 + x3 <= 14
 20 *  c6:  x1 + x3 >= 1
 21 *  Bounds
 22 *   5 <= x3
 23 *   0 <= x4 <= 2
 24 *  End
 25 */
 26#include <stdio.h>
 27#include "Mindopt.h"
 28#include <stdlib.h>
 29
 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); RELEASE_MEMORY; return (res); } }
 34#define NROWS        7
 35#define NCOLS        5
 36#define MODEL_NAME  "lp_iis"
 37#define MODEL_SENSE "ModelSense"
 38#define STATUS      "Status"
 39#define ROWNAME     "RowName"
 40#define COLNAME     "ColName"
 41#define IISROW      "IISRow"
 42#define IISCOL      "IISCol"
 43#define MAXDIM      (NROWS>NCOLS ? NROWS:NCOLS)
 44
 45int main(void) 
 46{
 47    /* Variables. */
 48    MDOenv *env;
 49    MDOmodel *m;
 50    int i, j, status;
 51    int ival[MAXDIM];
 52
 53    /* Model data. */
 54    int cbeg[] = {0, 2, 4, 6, 8, 10, 13, 15};
 55    int cind[] = 
 56    {
 57        0,   1, 
 58        0,   1,
 59        0,   1,
 60        3,   4,
 61        0,   4,
 62        0,   1,   3,
 63        1,   3  
 64    };
 65    double cval[] =
 66    {
 67       -0.5, 1,
 68        2,  -1,
 69        3,   1,
 70        3,  -1,
 71        1,   1,
 72        1,   2,   1,
 73        1,   1
 74    };
 75    double lhs[] = 
 76    {          
 77        0.5, 3.0, -MDO_INFINITY, -MDO_INFINITY, -MDO_INFINITY, -MDO_INFINITY, 1.0 
 78    };
 79    double rhs[] = 
 80    {
 81        MDO_INFINITY, MDO_INFINITY, 6.0, 2.0, 10.0, 14.0, MDO_INFINITY
 82    };
 83    const char* rowname[] = { "c0", "c1" , "c2" , "c3" , "c4" , "c5" , "c6" };
 84    double lb[] =  {          0.0,          0.0,          0.0,          5.0, 0.0 };
 85    double ub[] =  { MDO_INFINITY, MDO_INFINITY, MDO_INFINITY, MDO_INFINITY, 2.0 };
 86    double obj[] = {          0.0,          0.0,          0.0,          0.0, 0.0 };
 87    const char* colname[] = { "x0", "x1", "x2", "x3", "x4" };
 88
 89    /* Create and start environment. */
 90    MDOemptyenv(&env);
 91    MDOstartenv(env);
 92
 93    /* Create optimization model with variables. */
 94    CHECK_RESULT(MDOnewmodel(env, &m, MODEL_NAME, NCOLS, obj, lb, ub, NULL, colname));
 95
 96    /* Input constraints. */
 97    CHECK_RESULT(MDOaddrangeconstrs(m, NROWS, cbeg[NROWS], cbeg, cind, cval, lhs, rhs, rowname));
 98
 99    /* Specify objective sense. */
100    CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MINIMIZE));
101    
102    /* Optimize the input problem. */
103    CHECK_RESULT(MDOoptimize(m));
104
105    /* Populate optimziation result. */
106    CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
107    if (status == MDO_INFEASIBLE || status == MDO_INF_OR_UBD) 
108    {
109        printf("Optimizer terminated with an primal infeasible status.\n");
110        printf("Start to compute an Irreducible Inconsistent Subsystem (IIS).\n");
111        /* Compute an IIS and write the result into file (in ILP format). */
112        CHECK_RESULT(MDOcomputeIIS(m));
113        printf("Writing IIS into file (ILP format).\n");
114        CHECK_RESULT(MDOwrite(m, "./test1.ilp"));
115        /* Populate the computed IIS. */
116        printf("Populating all variable/constraint bounds participate in the computed IIS.\n");
117        CHECK_RESULT(MDOgetintattrarray(m, IISROW, 0, NROWS, &(*ival)));
118        for (i = 0; i < NROWS; ++i)
119        {
120            switch (ival[i])
121            {
122            case 2:
123                printf("The upper bound of inequality constraint [%s] participates in the IIS.\n", rowname[i]);
124                break;
125            case 3:
126                printf("The lower bound of inequality constraint [%s] participates in the IIS.\n", rowname[i]);
127                break;
128            case 5:
129                printf("[%s] is an equality constraint, and both its lower bound and upper bound participate in the IIS.\n", rowname[i]);
130                break;
131            }
132        }
133        CHECK_RESULT(MDOgetintattrarray(m, IISCOL, 0, NCOLS, &(*ival)));
134        for (j = 0; j < NCOLS; ++j)
135        {
136            switch (ival[j])
137            {
138            case 2:
139                printf("The upper bound of variable [%s] participates in the IIS.\n", colname[j]);
140                break;
141            case 3:
142                printf("The lower bound of variable [%s] participates in the IIS.\n", colname[j]);
143                break;
144            case 5:
145                printf("[%s] is a fixed variable, and both its lower bound and upper bound participate in the IIS.\n", colname[j]);
146                break;
147            }
148        }
149    }
150
151    /* Free up model memory. */
152    RELEASE_MEMORY;
153
154    return 0;
155}

6.1.2. C++ 的IIS计算

首先,参考 C++ 的LP建模和优化 中的方法创建优化问题并设置参数:

36        /* Create an empty model for optimization. */
37        MDOEnv env = MDOEnv();
38        MDOModel model = MDOModel(env);
39
40        /* Add variables. */
41        vector<MDOVar> x;
42        x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, MDO_CONTINUOUS, "x0"));
43        x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, MDO_CONTINUOUS, "x1"));
44        x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, MDO_CONTINUOUS, "x2"));
45        x.push_back(model.addVar(5.0, MDO_INFINITY, 0.0, MDO_CONTINUOUS, "x3"));
46        x.push_back(model.addVar(0.0, 2.0,          0.0, MDO_CONTINUOUS, "x4"));
47
48        /* Add constraints. */
49        vector<MDOConstr> constr;
50        constr.push_back(model.addConstr(-0.5 * x[0]        + x[1]                   >= 0.5,  "c0"));
51        constr.push_back(model.addConstr( 2.0 * x[0]        - x[1]                   >= 3.0,  "c1"));
52        constr.push_back(model.addConstr( 3.0 * x[0]        + x[1]                   <= 6.0,  "c2"));
53        constr.push_back(model.addConstr(                          3.0 * x[3] - x[4] <= 2.0,  "c3"));
54        constr.push_back(model.addConstr(       x[0]                          + x[4] <= 10.0, "c4"));
55        constr.push_back(model.addConstr(       x[0] + 2.0 * x[1]      + x[3]        <= 14.0, "c5"));
56        constr.push_back(model.addConstr(                    x[1]      + x[3]        >= 1.0,  "c6"));
57
58        /* Optimize the input problemodel. */
59        model.optimize();

接下来,当优化问题不可行时,使用 MDOModel::computeIIS() 求解IIS,可以利用 MDOModel::write() 将求得的IIS写到文件,可以通过约束的 IISConstr 属性或变量的 IISVar 属性判断其是否在求得的IIS中:

 61        /* Populate optimziation result. */
 62        int status = model.get(MDO_IntAttr_Status);
 63        if (status == MDO_INFEASIBLE || status == MDO_INF_OR_UBD) 
 64        {
 65            cout << "Optimizer terminated with an primal infeasible status." << endl;
 66            cout << "Start to compute an Irreducible Inconsistent Subsystem (IIS)." << endl;
 67            /* Compute an IIS and write it into file (in ILP format). */
 68            model.computeIIS();
 69            cout << "Writing IIS into file (ILP format)." << endl;
 70            model.write("./test1.ilp");
 71            /* Populate the computed IIS. */
 72            cout << "Populating all row/column bounds participate in the computed IIS." << endl;
 73            for (auto c : constr)
 74            {
 75                string name = c.get(MDO_StringAttr_ConstrName);
 76                switch (c.get(MDO_IntAttr_IISConstr))
 77                {
 78                case 2:
 79                    cout << "The upper bound of inequality constraint [" << name << "] participates in the IIS." << endl;
 80                    break;
 81                case 3:
 82                    cout << "The lower bound of inequality constraint [" << name << "] participates in the IIS." << endl;
 83                    break;
 84                case 5:
 85                    cout << "[" << name << "] is an equality constraint, and both its lower bound and upper bound participate in the IIS." << endl;
 86                    break;
 87                }
 88            }
 89            for (auto v : x)
 90            {
 91                string name = v.get(MDO_StringAttr_VarName);
 92                switch (v.get(MDO_IntAttr_IISVar))
 93                {
 94                case 2:
 95                    cout << "The upper bound of variable [" << name << "] participates in the IIS." << endl;
 96                    break;
 97                case 3:
 98                    cout << "The lower bound of variable [" << name << "] participates in the IIS." << endl;
 99                    break;
100                case 5:
101                    cout << "[" << name << "] is a fixed variable, and both its lower bound and upper bound participate in the IIS." << endl;
102                    break;
103                }
104            }
105        }

示例 MdoLoIIS.cpp 提供了完整源代码:

  1/**
  2 *  Description
  3 *  -----------
  4 *
  5 *  Linear optimization.
  6 *   - Compute IIS of an infeasible problem.
  7 *
  8 *  Formulation
  9 *  -----------
 10 *
 11 *  Minimize
 12 *  Obj:
 13 *  Subject To
 14 *  c0:  -0.500000000 x0 + x1 >= 0.500000000
 15 *  c1:  2 x0 - x1 >= 3
 16 *  c2:  3 x0 + x1 <= 6
 17 *  c3:  3 x3 - x4 <= 2 <- conflicts with variable bounds listed below!
 18 *  c4:  x0 + x4 <= 10
 19 *  c5:  x0 + 2 x1 + x3 <= 14
 20 *  c6:  x1 + x3 >= 1
 21 *  Bounds
 22 *   5 <= x3
 23 *   0 <= x4 <= 2
 24 *  End
 25 */
 26#include "MindoptCpp.h"
 27#include <iostream>
 28#include <map>
 29
 30using namespace std;
 31
 32int main(int argc, char *argv[]) 
 33{
 34    try 
 35    {
 36        /* Create an empty model for optimization. */
 37        MDOEnv env = MDOEnv();
 38        MDOModel model = MDOModel(env);
 39
 40        /* Add variables. */
 41        vector<MDOVar> x;
 42        x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, MDO_CONTINUOUS, "x0"));
 43        x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, MDO_CONTINUOUS, "x1"));
 44        x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, MDO_CONTINUOUS, "x2"));
 45        x.push_back(model.addVar(5.0, MDO_INFINITY, 0.0, MDO_CONTINUOUS, "x3"));
 46        x.push_back(model.addVar(0.0, 2.0,          0.0, MDO_CONTINUOUS, "x4"));
 47
 48        /* Add constraints. */
 49        vector<MDOConstr> constr;
 50        constr.push_back(model.addConstr(-0.5 * x[0]        + x[1]                   >= 0.5,  "c0"));
 51        constr.push_back(model.addConstr( 2.0 * x[0]        - x[1]                   >= 3.0,  "c1"));
 52        constr.push_back(model.addConstr( 3.0 * x[0]        + x[1]                   <= 6.0,  "c2"));
 53        constr.push_back(model.addConstr(                          3.0 * x[3] - x[4] <= 2.0,  "c3"));
 54        constr.push_back(model.addConstr(       x[0]                          + x[4] <= 10.0, "c4"));
 55        constr.push_back(model.addConstr(       x[0] + 2.0 * x[1]      + x[3]        <= 14.0, "c5"));
 56        constr.push_back(model.addConstr(                    x[1]      + x[3]        >= 1.0,  "c6"));
 57
 58        /* Optimize the input problemodel. */
 59        model.optimize();
 60
 61        /* Populate optimziation result. */
 62        int status = model.get(MDO_IntAttr_Status);
 63        if (status == MDO_INFEASIBLE || status == MDO_INF_OR_UBD) 
 64        {
 65            cout << "Optimizer terminated with an primal infeasible status." << endl;
 66            cout << "Start to compute an Irreducible Inconsistent Subsystem (IIS)." << endl;
 67            /* Compute an IIS and write it into file (in ILP format). */
 68            model.computeIIS();
 69            cout << "Writing IIS into file (ILP format)." << endl;
 70            model.write("./test1.ilp");
 71            /* Populate the computed IIS. */
 72            cout << "Populating all row/column bounds participate in the computed IIS." << endl;
 73            for (auto c : constr)
 74            {
 75                string name = c.get(MDO_StringAttr_ConstrName);
 76                switch (c.get(MDO_IntAttr_IISConstr))
 77                {
 78                case 2:
 79                    cout << "The upper bound of inequality constraint [" << name << "] participates in the IIS." << endl;
 80                    break;
 81                case 3:
 82                    cout << "The lower bound of inequality constraint [" << name << "] participates in the IIS." << endl;
 83                    break;
 84                case 5:
 85                    cout << "[" << name << "] is an equality constraint, and both its lower bound and upper bound participate in the IIS." << endl;
 86                    break;
 87                }
 88            }
 89            for (auto v : x)
 90            {
 91                string name = v.get(MDO_StringAttr_VarName);
 92                switch (v.get(MDO_IntAttr_IISVar))
 93                {
 94                case 2:
 95                    cout << "The upper bound of variable [" << name << "] participates in the IIS." << endl;
 96                    break;
 97                case 3:
 98                    cout << "The lower bound of variable [" << name << "] participates in the IIS." << endl;
 99                    break;
100                case 5:
101                    cout << "[" << name << "] is a fixed variable, and both its lower bound and upper bound participate in the IIS." << endl;
102                    break;
103                }
104            }
105        }
106    } 
107    catch (MDOException &e) 
108    {
109        cerr << "Error code = " << e.getErrorCode() << endl;
110        cerr << e.getMessage() << endl;
111    } 
112    catch (...) 
113    {
114        cerr << "Error during optimization." << endl;
115    }
116
117    return 0;
118}

6.1.3. Python 的IIS计算

首先,参考 Python 的LP建模与优化 中的方法创建优化问题并设置参数:

36    try:
37        # Add Variables.
38        x = []
39        x.append(model.addVar(0.0, float('inf'), 'C', "x0"))
40        x.append(model.addVar(0.0, float('inf'), 'C', "x1"))
41        x.append(model.addVar(0.0, float('inf'), 'C', "x2"))
42        x.append(model.addVar(5.0, float('inf'), 'C', "x3"))
43        x.append(model.addVar(0.0, 2.0,          'C', "x4"))
44
45        # Add Constraints.
46        constr = []
47        constr.append(model.addConstr(-0.5 * x[0]       + x[1]                    >= 0.5,  "c0"))
48        constr.append(model.addConstr( 2.0 * x[0]       - x[1]                    >= 3.0,  "c1"))
49        constr.append(model.addConstr( 3.0 * x[0]       + x[1]                    <= 6.0,  "c2"))
50        constr.append(model.addConstr(                          3.0 * x[3] - x[4] <= 2.0,  "c3"))
51        constr.append(model.addConstr(       x[0]                          + x[4] <= 10.0, "c4"))
52        constr.append(model.addConstr(       x[0] + 2.0 * x[1]      + x[3]        <= 14.0, "c5"))
53        constr.append(model.addConstr(       x[1] +                   x[3]        >= 1.0,  "c6"))
54
55        # Optimize the input problem.
56        model.optimize()

接下来,当优化问题不可行时,使用 Model.computeIIS() 求解一个IIS,并打印组成该IIS的约束名与变量名,使用 Model.write() 可以将求得的IIS写到文件:

57        # Run IIS.
58        if model.status == MDO.INFEASIBLE or model.status == MDO.INF_OR_UBD:
59            print("Optimizer terminated with an primal infeasible status.")
60            print("Start to compute an Irreducible Inconsistent Subsystem (IIS).")
61            # Compute an IIS and write it to file (in ILP format).
62            model.computeIIS()
63            print("Writing IIS into file (ILP format).")
64            model.write("./test1.ilp")
65            print("Populating all bounds participate in the computed IIS.")
66            for c in constr:
67                status = c.IISConstr
68                name = c.ConstrName
69                if status == 2:
70                    print(f"The upper bound of inequality constraint [{name}] participates in the IIS.")
71                elif status == 3:
72                    print(f"The lower bound of inequality constraint [{name}] participates in the IIS.")
73                elif status == 5:
74                    print(f"[{name}] is an equality constraint, and both its lower bound and upper bound participate in the IIS.")
75            for v in x:
76                status = v.IISVar
77                name = v.VarName
78                if status == 2:
79                    print(f"The upper bound of variable [{name}] participates in the IIS.")
80                elif status == 3:
81                    print(f"The lower bound of variable [{name}] participates in the IIS.")
82                elif status == 5:
83                    print(f"[{name}] is a fixed variable, and both its lower bound and upper bound participate in the IIS.")

示例 mdo_lo_iis.py 提供了完整源代码:

 1"""
 2/**
 3 *  Description
 4 *  -----------
 5 *
 6 *  Linear optimization.
 7 *   - Compute an IIS on an infeasible problem.
 8 * 
 9 *  Formulation
10 *  -----------
11 *
12 *  Minimize
13 *  Obj:
14 *  Subject To
15 *  c0:  -0.500000000 x0 + x1 >= 0.500000000
16 *  c1:  2 x0 - x1 >= 3
17 *  c2:  3 x0 + x1 <= 6
18 *  c3:  3 x3 - x4 <= 2 <- conflit with variable bounds below!
19 *  c4:  x0 + x4 <= 10
20 *  c5:  x0 + 2 x1 + x3 <= 14
21 *  c6:  x1 + x3 >= 1
22 *  Bounds
23 *   5 <= x3
24 *   0 <= x4 <= 2
25 *  End
26 */
27"""
28from mindoptpy import *
29
30if __name__ == "__main__":
31
32    # Create an empty model for optimization.
33    model = Model("IIS_LP")
34
35    try:
36        # Add Variables.
37        x = []
38        x.append(model.addVar(0.0, float('inf'), 'C', "x0"))
39        x.append(model.addVar(0.0, float('inf'), 'C', "x1"))
40        x.append(model.addVar(0.0, float('inf'), 'C', "x2"))
41        x.append(model.addVar(5.0, float('inf'), 'C', "x3"))
42        x.append(model.addVar(0.0, 2.0,          'C', "x4"))
43
44        # Add Constraints.
45        constr = []
46        constr.append(model.addConstr(-0.5 * x[0]       + x[1]                    >= 0.5,  "c0"))
47        constr.append(model.addConstr( 2.0 * x[0]       - x[1]                    >= 3.0,  "c1"))
48        constr.append(model.addConstr( 3.0 * x[0]       + x[1]                    <= 6.0,  "c2"))
49        constr.append(model.addConstr(                          3.0 * x[3] - x[4] <= 2.0,  "c3"))
50        constr.append(model.addConstr(       x[0]                          + x[4] <= 10.0, "c4"))
51        constr.append(model.addConstr(       x[0] + 2.0 * x[1]      + x[3]        <= 14.0, "c5"))
52        constr.append(model.addConstr(       x[1] +                   x[3]        >= 1.0,  "c6"))
53
54        # Optimize the input problem.
55        model.optimize()
56
57        # Run IIS.
58        if model.status == MDO.INFEASIBLE or model.status == MDO.INF_OR_UBD:
59            print("Optimizer terminated with an primal infeasible status.")
60            print("Start to compute an Irreducible Inconsistent Subsystem (IIS).")
61            # Compute an IIS and write it to file (in ILP format).
62            model.computeIIS()
63            print("Writing IIS into file (ILP format).")
64            model.write("./test1.ilp")
65            print("Populating all bounds participate in the computed IIS.")
66            for c in constr:
67                status = c.IISConstr
68                name = c.ConstrName
69                if status == 2:
70                    print(f"The upper bound of inequality constraint [{name}] participates in the IIS.")
71                elif status == 3:
72                    print(f"The lower bound of inequality constraint [{name}] participates in the IIS.")
73                elif status == 5:
74                    print(f"[{name}] is an equality constraint, and both its lower bound and upper bound participate in the IIS.")
75            for v in x:
76                status = v.IISVar
77                name = v.VarName
78                if status == 2:
79                    print(f"The upper bound of variable [{name}] participates in the IIS.")
80                elif status == 3:
81                    print(f"The lower bound of variable [{name}] participates in the IIS.")
82                elif status == 5:
83                    print(f"[{name}] is a fixed variable, and both its lower bound and upper bound participate in the IIS.")
84    except MindoptError as e:
85        print("Received Mindopt exception.")
86        print(" - Code          : {}".format(e.code))
87        print(" - Reason        : {}".format(e.message))
88    except Exception as e:
89        print("Received other exception.")
90        print(" - Reason        : {}".format(e))
91    finally:
92        # Free up model.
93        model.dispose()