5.6.2. MIQCP Modeling and Optimization in CΒΆ

In this chapter, we will use MindOpt C API to model and solve the problem in Example of Mixed Integer Quadratically Constrained Programming.

Include the header file:

27#include <stdio.h>

Create an optimization model model:

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

Next, we set the optimization sense to minimization via MDOsetIntAttr() and four variables are added by calling MDOaddvar(). Their lower bounds, upper bounds, names, types and linear objective coefficients are defined as follows (for more details on how to use MDOsetIntAttr() and MDOaddvar(), please refer to Attributes):

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"));

Note

The non-zero elements of the matrix \(A\) will be inputted later. After adding the four aforementioned variables, certain parameters of the constraint matrix, specifically size, indices, and value, are set to 0, NULL, and NULL, respectively. This means that, as of now, model has no constraints.

Next, we will introduce the quadratic terms in the objective. Three arrays are utilized for this purpose. Specifically, qo_col1, qo_col2, and qo_values record the row indices, column indices, and values of all the non-zero quadratic terms.

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;

We call MDOaddqpterms() to set the quadratic terms of the objective.

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"));

Now we start to add quadratic constraints to the model. The linear part is constructed in the same way as in the objective.

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 */

The quadratic part is constructed in the same way as it is in the objective as well.

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;

We call MDOaddqconstr() to input the linear constraints into model:

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

Once the model is constructed, we call MDOoptimize() to solve the problem:

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

We can retrieive the optimal objective value and solutions via getting attributes:

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    {

Finally, we call MDOfreemodel() and MDOfreeenv() to free the model:

30/* Macro to check the return code */
31#define RELEASE_MEMORY  \

127            CHECK_RESULT(MDOgetdblattrelement(model, X, i, &x));

The complete example code is provided in 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}