5.2.2. C 的MILP建模和优化

在本节中,我们将使用 MindOpt C API,以按行输入的形式来建模以及求解 混合整数线性规划问题示例 中的问题。

首先,引入头文件:

25#include <stdio.h>

创建优化模型:

58    /* Create an empty model. */
59    CHECK_RESULT(MDOemptyenv(&env));
60    CHECK_RESULT(MDOstartenv(env));

接下来,我们通过 MDOsetintattr() 将目标函数设置为 最小化,并调用 MDOaddvar() 来添加四个优化变量。(更多API和使用方式,请参考 C API):

65    /*------------------------------------------------------------------*/
66    /* Change to minimization problem. */
67    CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MINIMIZE));
68
69    /* Add variables. */
70    CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0,         10.0, MDO_INTEGER,    "x0"));
71    CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 2.0, 0, MDO_INFINITY, MDO_INTEGER,    "x1"));
72    CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_INTEGER,    "x2"));

接下来添加线性约束,需要定义其中的非零元及其左右边界。我们使用以下四列数组来定义线性约束,其中, row1_idxrow2_idx 分别表示第一和第二个约束中非零元素的位置(索引),而 row1_valrow2_val 则是与之相对应的非零数值。

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   };

调用 MDOaddconstr() 来输入约束:

74    /* Add constraints. */
75    CHECK_RESULT(MDOaddconstr(m, 4, row1_idx, row1_val, MDO_GREATER_EQUAL, 1.0, "c0"));

问题输入完成后,再调用 MDOoptimize() 求解优化问题。

81    /*------------------------------------------------------------------*/

然后,我们可以通过获取属性值的方式来获取求解后的最优值 (optimal value) 和最优解 (optimal solution).

82    CHECK_RESULT(MDOoptimize(m));
83
84    /*------------------------------------------------------------------*/
85    /* Step 4. Retrive model status and objective.                      */
86    /* For MIP(MILP,MIQP, MIQCP) problems, if the solving process       */
87    /* terminates early due to reasons such as timeout or interruption, */
88    /* the model status will indicate termination by timeout (or        */
89    /* interruption, etc.). However, suboptimal solutions may still     */
90    /* exist, making it necessary to check the SolCount property.       */
91    /*------------------------------------------------------------------*/
92    CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
93    CHECK_RESULT(MDOgetintattr(m, SOL_COUNT, &solcount));
94    if (status == MDO_OPTIMAL || status == MDO_SUB_OPTIMAL || solcount != 0)
95    {
96        CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
97        printf("The optimal objective value is %f\n", obj);

最后,调用 MDOfreemodel()MDOfreeenv() 来释放模型:

30#define RELEASE_MEMORY  \
31    MDOfreemodel(m);    \
32    MDOfreeenv(env);
102            printf("x%d = %f\n", i, x);

示例 MdoMiloEx1.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); RELEASE_MEMORY; exit(res); } }
 34#define MODEL_NAME  "MILP_01"
 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    /* Creat Model. */
 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 environment and model.                            */
 57    /*------------------------------------------------------------------*/
 58    /* Create an empty model. */
 59    CHECK_RESULT(MDOemptyenv(&env));
 60    CHECK_RESULT(MDOstartenv(env));
 61    CHECK_RESULT(MDOnewmodel(env, &m, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
 62
 63    /*------------------------------------------------------------------*/
 64    /* Step 2. Input model.                                             */
 65    /*------------------------------------------------------------------*/
 66    /* Change to minimization problem. */
 67    CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MINIMIZE));
 68
 69    /* Add variables. */
 70    CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0,         10.0, MDO_INTEGER,    "x0"));
 71    CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 2.0, 0, MDO_INFINITY, MDO_INTEGER,    "x1"));
 72    CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_INTEGER,    "x2"));
 73    CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x3"));
 74
 75    /* Add constraints. */
 76    CHECK_RESULT(MDOaddconstr(m, 4, row1_idx, row1_val, MDO_GREATER_EQUAL, 1.0, "c0"));
 77    CHECK_RESULT(MDOaddconstr(m, 3, row2_idx, row2_val, MDO_EQUAL,         1.0, "c1"));
 78
 79    /*------------------------------------------------------------------*/
 80    /* Step 3. Solve the problem.                                       */
 81    /*------------------------------------------------------------------*/
 82    CHECK_RESULT(MDOoptimize(m));
 83
 84    /*------------------------------------------------------------------*/
 85    /* Step 4. Retrive model status and objective.                      */
 86    /* For MIP(MILP,MIQP, MIQCP) problems, if the solving process       */
 87    /* terminates early due to reasons such as timeout or interruption, */
 88    /* the model status will indicate termination by timeout (or        */
 89    /* interruption, etc.). However, suboptimal solutions may still     */
 90    /* exist, making it necessary to check the SolCount property.       */
 91    /*------------------------------------------------------------------*/
 92    CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
 93    CHECK_RESULT(MDOgetintattr(m, SOL_COUNT, &solcount));
 94    if (status == MDO_OPTIMAL || status == MDO_SUB_OPTIMAL || solcount != 0)
 95    {
 96        CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
 97        printf("The optimal objective value is %f\n", obj);
 98
 99        for (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 exists\n");
108    }
109
110    /*------------------------------------------------------------------*/
111    /* Step 4. Free the model.                                          */
112    /*------------------------------------------------------------------*/
113    RELEASE_MEMORY;
114
115    return 0;
116}