5.6.2. C 的MIQCP建模和优化

在本节中,我们将使用 MindOpt C API,以按行输入的形式来建模以及求解 MIQCP题示例 中的问题。

首先,引入头文件:

27#include <stdio.h>

并创建优化模型:

78     /*------------------------------------------------------------------*/
79    /* Step 1. Create environment and model.                            */
80    /*------------------------------------------------------------------*/

接下来,我们通过 MDOsetIntAttr() 将目标函数设置为 最小化,并调用 MDOaddvar() 来添加四个优化变量,定义其下界、上界、名称和类型,以及其在目标函数中线性项的系数(关于 MDOsetIntAttr()MDOaddvar() 的详细使用方式,请参考 属性):

86    /*------------------------------------------------------------------*/
87    /* Step 2. Input model.                                             */
88    /*------------------------------------------------------------------*/
89    /* Change to minimization problem. */
90    CHECK_RESULT(MDOsetintattr(model, MODEL_SENSE, MDO_MINIMIZE));
91
92    /* Add variables. */
93    CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0,         10.0, MDO_INTEGER, "x0"));

备注

在函数 MDOaddvar() 中一个参数位是 vtype,设置为 MDO_INTEGER 代表这个变量是整形变量。 矩阵的非零元随后将按 输入;因此,MDOaddvar() 中,与约束矩阵相关联的参数 sizeindicesvalue 分别用 0NULLNULL 代替(换句话说,此时问题无约束)。

接下来我们将添加二次规划中的目标函数的二次项系数。我们使用以下三列数组来定义:其中 qo_col1qo_col2 分别记录二次项中所有非零项的两个变量索引,而 qo_values 是与之相对应的非零系数值。

49    int i, solcount, status;
50
51    /* Prepare model data. */
52    /* Quadratic part in objective: 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
53    int    qo_nnz      = 5;

我们调用 MDOaddqpterms() 设置目标的二次项:

95    CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x2"));
96    CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x3"));

以下我们将开始添加模型中的两个二次约束。其中的线性项与添加线性约束的方式类似,我们使用以下数组来定义线性项;其中, row1_idxrow2_idx 分别表示第一和第二个约束中非零元素的位置(索引),而 row1_valrow2_val 则是与之相对应的非零数值。

55    int    qo_col2[]   = { 0,   1,   2,   3,   1 };
56    double qo_values[] = { 0.5, 0.5, 0.5, 0.5, 0.5 };
57
58    /* Linear part in the first constraint: 1 x0 + 1 x1 + 2 x2 + 3 x3 */
65    int    qc1_col2[]   = { 0,    1,    2,    3,    1 };
66    double qc1_values[] = { -0.5, -0.5, -0.5, -0.5, -0.5 };
67
68    /* Linear part in the second constraint: 1 x0 - 1 x2 + 6 x3 */

二次约束中的二次项与目标函数中的二次项类似:第一个二次约束中我们用 qc1_col1qc1_col2 分别记录二次项中所有非零项的两个变量索引,而 qc1_values 是与之相对应的非零系数值。第二个二次约束类似。

59    int    row1_nnz   = 4;
60    int    row1_idx[] = { 0,   1,   2,   3   };
61    double row1_val[] = { 1.0, 1.0, 2.0, 3.0 };
62    /* Quadratic part in the first constraint: - 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
63    int    qc1_nnz      = 5;
69    int    row2_nnz   = 3;
70    int    row2_idx[] = { 0,    2,   3   };
71    double row2_val[] = { 1.0, -1.0, 6.0 };
72    /* Quadratic part in the second constraint: 1/2 [x1^2] */
73    int    qc2_nnz      = 1;

我们调用 MDOaddqconstr() 来添加二次约束:

98    /* Add quadratic objective term. */
99    CHECK_RESULT(MDOaddqpterms(model, qo_nnz, qo_col1, qo_col2, qo_values));

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

105    /*------------------------------------------------------------------*/
106    /* Step 3. Solve the problem.                                       */

然后,我们可以通过获取属性值的方式来获取对应的优化目标值objective和变量的取值:

108    /* Solve the problem. */
109    CHECK_RESULT(MDOoptimize(model));
110
111    /*------------------------------------------------------------------*/
112    /* Step 4. Retrive model status and objective.                      */
113    /* For MIP(MILP,MIQP, MIQCP) problems, if the solving process       */
114    /* terminates early due to reasons such as timeout or interruption, */
115    /* the model status will indicate termination by timeout (or        */
116    /* interruption, etc.). However, suboptimal solutions may still     */
117    /* exist, making it necessary to check the SolCount property.       */
118    /*------------------------------------------------------------------*/
119    CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
120    CHECK_RESULT(MDOgetintattr(m, SOL_COUNT, &solcount));
121    if (status == MDO_OPTIMAL || status == MDO_SUB_OPTIMAL || solcount != 0)
122    {

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

30/* Macro to check the return code */
31#define RELEASE_MEMORY  \
127            CHECK_RESULT(MDOgetdblattrelement(model, X, i, &x));

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

  1/**
  2 *  Description
  3 *  -----------
  4 *
  5 *  Mixed Integer Quadratically constrained quadratic optimization (row-wise input).
  6 *
  7 *  Formulation
  8 *  -----------
  9 *
 10 *  Minimize
 11 *    obj: 1 x0 + 1 x1 + 1 x2 + 1 x3
 12 *         + 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1]
 13 *
 14 *  Subject To
 15 *   c0 : 1 x0 + 1 x1 + 2 x2 + 3 x3 - 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] >= 1
 16 *   c1 : 1 x0 - 1 x2 + 6 x3 + 1/2 [x1^2] <= 1
 17 *  Bounds
 18 *    0 <= x0 <= 10
 19 *    0 <= x1
 20 *    0 <= x2
 21 *    0 <= x3
 22 *  Integer
 23 *  x0 
 24 *  End
 25 */
 26
 27#include <stdio.h>
 28#include <stdlib.h>
 29#include "Mindopt.h"
 30
 31/* Macro to check the return code */
 32#define RELEASE_MEMORY  \
 33    MDOfreemodel(model);    \
 34    MDOfreeenv(env);
 35#define CHECK_RESULT(code) { int res = code; if (res != 0) { fprintf(stderr, "Bad code: %d\n", res);  RELEASE_MEMORY; return (res); } }
 36#define MODEL_NAME  "QCP_01"
 37#define MODEL_SENSE "ModelSense"
 38#define SOL_COUNT   "SolCount"
 39#define STATUS      "Status"
 40#define OBJ_VAL     "ObjVal"
 41#define X           "X"
 42
 43int main(void)
 44{
 45    /* Variables. */
 46    MDOenv *env;
 47    MDOmodel *model;
 48    double obj, x;
 49    int i, solcount, status;
 50
 51    /* Prepare model data. */
 52    /* Quadratic part in objective: 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
 53    int    qo_nnz      = 5;
 54    int    qo_col1[]   = { 0,   1,   2,   3,   0 };
 55    int    qo_col2[]   = { 0,   1,   2,   3,   1 };
 56    double qo_values[] = { 0.5, 0.5, 0.5, 0.5, 0.5 };
 57
 58    /* Linear part in the first constraint: 1 x0 + 1 x1 + 2 x2 + 3 x3 */
 59    int    row1_nnz   = 4;
 60    int    row1_idx[] = { 0,   1,   2,   3   };
 61    double row1_val[] = { 1.0, 1.0, 2.0, 3.0 };
 62    /* Quadratic part in the first constraint: - 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
 63    int    qc1_nnz      = 5;
 64    int    qc1_col1[]   = { 0,    1,    2,    3,    0 };
 65    int    qc1_col2[]   = { 0,    1,    2,    3,    1 };
 66    double qc1_values[] = { -0.5, -0.5, -0.5, -0.5, -0.5 };
 67
 68    /* Linear part in the second constraint: 1 x0 - 1 x2 + 6 x3 */
 69    int    row2_nnz   = 3;
 70    int    row2_idx[] = { 0,    2,   3   };
 71    double row2_val[] = { 1.0, -1.0, 6.0 };
 72    /* Quadratic part in the second constraint: 1/2 [x1^2] */
 73    int    qc2_nnz      = 1;
 74    int    qc2_col1[]   = { 1 };
 75    int    qc2_col2[]   = { 1 };
 76    double qc2_values[] = { 0.5 };
 77
 78     /*------------------------------------------------------------------*/
 79    /* Step 1. Create environment and model.                            */
 80    /*------------------------------------------------------------------*/
 81    CHECK_RESULT(MDOemptyenv(&env));
 82    CHECK_RESULT(MDOstartenv(env));
 83    CHECK_RESULT(MDOnewmodel(env, &model, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
 84
 85
 86    /*------------------------------------------------------------------*/
 87    /* Step 2. Input model.                                             */
 88    /*------------------------------------------------------------------*/
 89    /* Change to minimization problem. */
 90    CHECK_RESULT(MDOsetintattr(model, MODEL_SENSE, MDO_MINIMIZE));
 91
 92    /* Add variables. */
 93    CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0,         10.0, MDO_INTEGER, "x0"));
 94    CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x1"));
 95    CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x2"));
 96    CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x3"));
 97
 98    /* Add quadratic objective term. */
 99    CHECK_RESULT(MDOaddqpterms(model, qo_nnz, qo_col1, qo_col2, qo_values));
100
101    /* Add quadratic constraints. */
102    CHECK_RESULT(MDOaddqconstr(model, row1_nnz, row1_idx, row1_val, qc1_nnz, qc1_col1, qc1_col2, qc1_values, MDO_GREATER_EQUAL, 1.0, "c0"));
103    CHECK_RESULT(MDOaddqconstr(model, row2_nnz, row2_idx, row2_val, qc2_nnz, qc2_col1, qc2_col2, qc2_values, MDO_LESS_EQUAL,    1.0, "c1"));
104    
105    /*------------------------------------------------------------------*/
106    /* Step 3. Solve the problem.                                       */
107    /*------------------------------------------------------------------*/
108    /* Solve the problem. */
109    CHECK_RESULT(MDOoptimize(model));
110
111    /*------------------------------------------------------------------*/
112    /* Step 4. Retrive model status and objective.                      */
113    /* For MIP(MILP,MIQP, MIQCP) problems, if the solving process       */
114    /* terminates early due to reasons such as timeout or interruption, */
115    /* the model status will indicate termination by timeout (or        */
116    /* interruption, etc.). However, suboptimal solutions may still     */
117    /* exist, making it necessary to check the SolCount property.       */
118    /*------------------------------------------------------------------*/
119    CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
120    CHECK_RESULT(MDOgetintattr(m, SOL_COUNT, &solcount));
121    if (status == MDO_OPTIMAL || status == MDO_SUB_OPTIMAL || solcount != 0)
122    {
123        CHECK_RESULT(MDOgetdblattr(model, OBJ_VAL, &obj));
124        printf("The optimal objective value is: %f\n", obj);
125        for (int i = 0; i < 4; ++i) 
126        {
127            CHECK_RESULT(MDOgetdblattrelement(model, X, i, &x));
128            printf("x[%d] = %f\n", i, x);
129        }
130    } 
131    else 
132    {
133        printf("No feasible solution.\n");
134    }
135 
136    /*------------------------------------------------------------------*/
137    /* Step 4. Free the model.                                          */
138    /*------------------------------------------------------------------*/
139    RELEASE_MEMORY;
140       
141    return 0;
142}