5.10. C 语言的QP建模和优化

在本节中,我们将使用 MindOpt C 语言的 API 来建模以及求解 二次规划问题示例 中的问题。

5.10.1. 按行输入:MdoQoEx1

首先,引入头文件:

24#include "Mindopt.h"

并创建优化模型:

87    /*------------------------------------------------------------------*/
88    /* Step 1. Create a model and change the parameters.                */
89    /*------------------------------------------------------------------*/
90    /* Create an empty model. */
91    MDO_CHECK_CALL(Mdo_createMdl(&model));

接下来,我们通过 Mdo_setIntAttr() 将目标函数设置为 最小化 ,并调用 Mdo_addCol() 来添加四个优化变量,定义其下界、上界、名称和类型(关于 Mdo_setIntAttr()Mdo_addCol() 的详细使用方式,请参考 C 接口函数):

 93    /*------------------------------------------------------------------*/
 94    /* Step 2. Input model.                                             */
 95    /*------------------------------------------------------------------*/
 96    /* Change to minimization problem. */
 97    MDO_CHECK_CALL(Mdo_setIntAttr(model, MDO_INT_ATTR_MIN_SENSE, MDO_YES));
 98
 99    /* Add variables. */
100    MDO_CHECK_CALL(Mdo_addCol(model, 0.0, 10.0,         1.0, 0, NULL, NULL, "x0", MDO_NO));
101    MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x1", MDO_NO));
102    MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x2", MDO_NO));
103    MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x3", MDO_NO));

Note

矩阵的非零元将在后面按 输入;因此,Mdo_addCol() 中,按 输入非零元的相关参数 sizeindicesvalue 分别用 0NULLNULL 代替(换句话说,此时问题无约束)。

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

48    const int    row1_idx[] = { 0,   1,   2,   3   };
49    const double row1_val[] = { 1.0, 1.0, 2.0, 3.0 };
50    const int    row2_idx[] = { 0,    2,   3   };
51    const double row2_val[] = { 1.0, -1.0, 6.0 };

我们调用 Mdo_addRow() 来输入约束:

105    /* Add constraints.
106     * Note that the nonzero elements are inputted in a row-wise order here.
107     */
108    MDO_CHECK_CALL(Mdo_addRow(model, 1.0, MDO_INFINITY, 4, row1_idx, row1_val, "c0"));
109    MDO_CHECK_CALL(Mdo_addRow(model, 1.0, 1.0,          3, row2_idx, row2_val, "c1"));

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

Note

为了确保 \(Q\) 的对称性,用户只需要输入其下三角形部分,并且在求解器内部会乘以 1/2.

53    /* Quadratic objective matrix Q.
54     * 
55     *  Note.
56     *  1. The objective function is defined as c^Tx + 1/2 x^TQx, where Q is stored with coordinate format.
57     *  2. Q will be scaled by 1/2 internally.
58     *  3. To ensure the symmetricity of Q, user needs to input only the lower triangular part.
59     * 
60     * Q = [ 1.0  0.5  0    0   ]
61     *     [ 0.5  1.0  0    0   ]
62     *     [ 0.0  0.0  1.0  0   ]
63     *     [ 0    0    0    1.0 ]
64     */
65    const int qo_col1[] = 
66    {
67        0, 
68        1,   1,
69                  2,
70                       3  
71    };
72    const int qo_col2[] =
73    {
74        0,
75        0,   1,
76                  2,
77                       3
78    };
79    const double qo_values[] =
80    {
81        1.0,
82        0.5, 1.0,
83                  1.0, 
84                       1.0
85    };

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

112    /* Add quadratic objective term. */
113    MDO_CHECK_CALL(Mdo_setQuadraticElements(model, 5, qo_col1, qo_col2, qo_values));

问题输入完成后,再调用 Mdo_solveProb() 求解优化问题,并通过 Mdo_displayResults() 查看优化结果:

114    /*------------------------------------------------------------------*/
115    /* Step 3. Solve the problem and populate the result.               */
116    /*------------------------------------------------------------------*/
117    /* Solve the problem. */
118    MDO_CHECK_CALL(Mdo_solveProb(model));
119    Mdo_displayResults(model);

最后,调用 Mdo_freeMdl() 来释放内存:

121    /*------------------------------------------------------------------*/
122    /* Step 4. Free the model.                                          */
123    /*------------------------------------------------------------------*/
124    /* Free the model. */
125    Mdo_freeMdl(&model);

MdoQoEx1.c 提供了完整源代码:

  1/**
  2 *  Description
  3 *  -----------
  4 *
  5 *  Linear 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 *  Subject To
 14 *   c0 : 1 x0 + 1 x1 + 2 x2 + 3 x3 >= 1
 15 *   c1 : 1 x0 - 1 x2 + 6 x3 = 1
 16 *  Bounds
 17 *    0 <= x0 <= 10
 18 *    0 <= x1
 19 *    0 <= x2
 20 *    0 <= x3
 21 *  End
 22 */
 23#include <stdio.h>
 24#include "Mindopt.h"
 25
 26/* Macro to check the return code */
 27#define MDO_CHECK_CALL(MDO_CALL)                                    \
 28    code = MDO_CALL;                                                \
 29    if (code != MDO_OKAY)                                           \
 30    {                                                               \
 31        Mdo_explainResult(model, code, str);                        \
 32        Mdo_freeMdl(&model);                                        \
 33        fprintf(stderr, "===================================\n");   \
 34        fprintf(stderr, "Error   : code <%d>\n", code);             \
 35        fprintf(stderr, "Reason  : %s\n", str);                     \
 36        fprintf(stderr, "===================================\n");   \
 37        return (int)code;                                           \
 38    }
 39
 40int main(void)
 41{
 42    /* Variables. */
 43    char str[1024] = { "\0" };
 44    MdoMdl * model = NULL;
 45    MdoResult code = MDO_OKAY;
 46    MdoStatus status = MDO_UNKNOWN;
 47
 48    const int    row1_idx[] = { 0,   1,   2,   3   };
 49    const double row1_val[] = { 1.0, 1.0, 2.0, 3.0 };
 50    const int    row2_idx[] = { 0,    2,   3   };
 51    const double row2_val[] = { 1.0, -1.0, 6.0 };
 52
 53    /* Quadratic objective matrix Q.
 54     * 
 55     *  Note.
 56     *  1. The objective function is defined as c^Tx + 1/2 x^TQx, where Q is stored with coordinate format.
 57     *  2. Q will be scaled by 1/2 internally.
 58     *  3. To ensure the symmetricity of Q, user needs to input only the lower triangular part.
 59     * 
 60     * Q = [ 1.0  0.5  0    0   ]
 61     *     [ 0.5  1.0  0    0   ]
 62     *     [ 0.0  0.0  1.0  0   ]
 63     *     [ 0    0    0    1.0 ]
 64     */
 65    const int qo_col1[] = 
 66    {
 67        0, 
 68        1,   1,
 69                  2,
 70                       3  
 71    };
 72    const int qo_col2[] =
 73    {
 74        0,
 75        0,   1,
 76                  2,
 77                       3
 78    };
 79    const double qo_values[] =
 80    {
 81        1.0,
 82        0.5, 1.0,
 83                  1.0, 
 84                       1.0
 85    };
 86
 87    /*------------------------------------------------------------------*/
 88    /* Step 1. Create a model and change the parameters.                */
 89    /*------------------------------------------------------------------*/
 90    /* Create an empty model. */
 91    MDO_CHECK_CALL(Mdo_createMdl(&model));
 92
 93    /*------------------------------------------------------------------*/
 94    /* Step 2. Input model.                                             */
 95    /*------------------------------------------------------------------*/
 96    /* Change to minimization problem. */
 97    MDO_CHECK_CALL(Mdo_setIntAttr(model, MDO_INT_ATTR_MIN_SENSE, MDO_YES));
 98
 99    /* Add variables. */
100    MDO_CHECK_CALL(Mdo_addCol(model, 0.0, 10.0,         1.0, 0, NULL, NULL, "x0", MDO_NO));
101    MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x1", MDO_NO));
102    MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x2", MDO_NO));
103    MDO_CHECK_CALL(Mdo_addCol(model, 0.0, MDO_INFINITY, 1.0, 0, NULL, NULL, "x3", MDO_NO));
104
105    /* Add constraints.
106     * Note that the nonzero elements are inputted in a row-wise order here.
107     */
108    MDO_CHECK_CALL(Mdo_addRow(model, 1.0, MDO_INFINITY, 4, row1_idx, row1_val, "c0"));
109    MDO_CHECK_CALL(Mdo_addRow(model, 1.0, 1.0,          3, row2_idx, row2_val, "c1"));
110
111    /* Add quadratic objective term. */
112    MDO_CHECK_CALL(Mdo_setQuadraticElements(model, 5, qo_col1, qo_col2, qo_values));
113
114    /*------------------------------------------------------------------*/
115    /* Step 3. Solve the problem and populate the result.               */
116    /*------------------------------------------------------------------*/
117    /* Solve the problem. */
118    MDO_CHECK_CALL(Mdo_solveProb(model));
119    Mdo_displayResults(model);
120 
121    /*------------------------------------------------------------------*/
122    /* Step 4. Free the model.                                          */
123    /*------------------------------------------------------------------*/
124    /* Free the model. */
125    Mdo_freeMdl(&model);
126       
127    return (int)code;
128}