5.4.2. QCP Modeling and Optimization in C¶
In this chapter, we will use MindOpt C API to model and solve the problem in Example of Quadratically Constrained Programming.
Include the header file:
27#include "Mindopt.h"
Create an optimization model model:
78 CHECK_RESULT(MDOemptyenv(&env));
79 CHECK_RESULT(MDOstartenv(env));
80 CHECK_RESULT(MDOnewmodel(env, &model, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
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 /* Change to minimization problem. */
87 CHECK_RESULT(MDOsetintattr(model, MODEL_SENSE, MDO_MINIMIZE));
88
89 /* Add variables. */
90 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, 10.0, MDO_CONTINUOUS, "x0"));
91 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x1"));
92 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x2"));
93 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x3"));
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 /* Quadratic part in objective: 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
50 int qo_nnz = 5;
51 int qo_col1[] = { 0, 1, 2, 3, 0 };
52 int qo_col2[] = { 0, 1, 2, 3, 1 };
53 double qo_values[] = { 0.5, 0.5, 0.5, 0.5, 0.5 };
We call MDOaddqpterms() to set the quadratic terms of the objective.
95 /* Add quadratic objective term. */
96 CHECK_RESULT(MDOaddqpterms(model, qo_nnz, qo_col1, qo_col2, qo_values));
Now we start to add quadratic constraints to the model. The linear part is constructed in the same way as in the objective.
55 /* Linear part in the first constraint: 1 x0 + 1 x1 + 2 x2 + 3 x3 */
56 int row1_nnz = 4;
57 int row1_idx[] = { 0, 1, 2, 3 };
58 double row1_val[] = { 1.0, 1.0, 2.0, 3.0 };
65 /* Linear part in the second constraint: 1 x0 - 1 x2 + 6 x3 */
66 int row2_nnz = 3;
67 int row2_idx[] = { 0, 2, 3 };
68 double row2_val[] = { 1.0, -1.0, 6.0 };
The quadratic part is constructed in the same way as it is in the objective as well.
59 /* Quadratic part in the first constraint: - 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
60 int qc1_nnz = 5;
61 int qc1_col1[] = { 0, 1, 2, 3, 0 };
62 int qc1_col2[] = { 0, 1, 2, 3, 1 };
63 double qc1_values[] = { -0.5, -0.5, -0.5, -0.5, -0.5 };
69 /* Quadratic part in the second constraint: 1/2 [x1^2] */
70 int qc2_nnz = 1;
71 int qc2_col1[] = { 1 };
72 int qc2_col2[] = { 1 };
73 double qc2_values[] = { 0.5 };
We call MDOaddqconstr() to input the linear constraints into model:
98 /* Add quadratic constraints. */
99 CHECK_RESULT(MDOaddqconstr(model, row1_nnz, row1_idx, row1_val, qc1_nnz, qc1_col1, qc1_col2, qc1_values, MDO_GREATER_EQUAL, 1.0, "c0"));
100 CHECK_RESULT(MDOaddqconstr(model, row2_nnz, row2_idx, row2_val, qc2_nnz, qc2_col1, qc2_col2, qc2_values, MDO_LESS_EQUAL, 1.0, "c1"));
Once the model is constructed, we call MDOoptimize() to solve the problem:
105 /* Solve the problem. */
106 CHECK_RESULT(MDOoptimize(model));
We can retrieive the optimal objective value and solutions via getting attributes:
108 CHECK_RESULT(MDOgetintattr(model, STATUS, &status));
109 if (status == MDO_OPTIMAL)
110 {
111 CHECK_RESULT(MDOgetdblattr(model, OBJ_VAL, &obj));
112 printf("The optimal objective value is: %f\n", obj);
113 for (int i = 0; i < 4; ++i)
114 {
115 CHECK_RESULT(MDOgetdblattrelement(model, X, i, &x));
116 printf("x[%d] = %f\n", i, x);
117 }
118 }
119 else
120 {
121 printf("No feasible solution.\n");
122 }
Finally, we call MDOfreemodel() and MDOfreeenv() to free the model:
30#define RELEASE_MEMORY \
31 MDOfreemodel(model); \
32 MDOfreeenv(env);
127 RELEASE_MEMORY;
The complete example code is provided in MdoQcoEx1.c:
1/**
2 * Description
3 * -----------
4 *
5 * 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 * 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(model); \
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 MODEL_NAME "QCP_01"
35#define MODEL_SENSE "ModelSense"
36#define STATUS "Status"
37#define OBJ_VAL "ObjVal"
38#define X "X"
39
40int main(void)
41{
42 /* Variables. */
43 MDOenv *env;
44 MDOmodel *model;
45 double obj, x;
46 int status, i;
47
48 /* Prepare model data. */
49 /* Quadratic part in objective: 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
50 int qo_nnz = 5;
51 int qo_col1[] = { 0, 1, 2, 3, 0 };
52 int qo_col2[] = { 0, 1, 2, 3, 1 };
53 double qo_values[] = { 0.5, 0.5, 0.5, 0.5, 0.5 };
54
55 /* Linear part in the first constraint: 1 x0 + 1 x1 + 2 x2 + 3 x3 */
56 int row1_nnz = 4;
57 int row1_idx[] = { 0, 1, 2, 3 };
58 double row1_val[] = { 1.0, 1.0, 2.0, 3.0 };
59 /* Quadratic part in the first constraint: - 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
60 int qc1_nnz = 5;
61 int qc1_col1[] = { 0, 1, 2, 3, 0 };
62 int qc1_col2[] = { 0, 1, 2, 3, 1 };
63 double qc1_values[] = { -0.5, -0.5, -0.5, -0.5, -0.5 };
64
65 /* Linear part in the second constraint: 1 x0 - 1 x2 + 6 x3 */
66 int row2_nnz = 3;
67 int row2_idx[] = { 0, 2, 3 };
68 double row2_val[] = { 1.0, -1.0, 6.0 };
69 /* Quadratic part in the second constraint: 1/2 [x1^2] */
70 int qc2_nnz = 1;
71 int qc2_col1[] = { 1 };
72 int qc2_col2[] = { 1 };
73 double qc2_values[] = { 0.5 };
74
75 /*------------------------------------------------------------------*/
76 /* Step 1. Create environment and model. */
77 /*------------------------------------------------------------------*/
78 CHECK_RESULT(MDOemptyenv(&env));
79 CHECK_RESULT(MDOstartenv(env));
80 CHECK_RESULT(MDOnewmodel(env, &model, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
81
82
83 /*------------------------------------------------------------------*/
84 /* Step 2. Input model. */
85 /*------------------------------------------------------------------*/
86 /* Change to minimization problem. */
87 CHECK_RESULT(MDOsetintattr(model, MODEL_SENSE, MDO_MINIMIZE));
88
89 /* Add variables. */
90 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, 10.0, MDO_CONTINUOUS, "x0"));
91 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x1"));
92 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x2"));
93 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x3"));
94
95 /* Add quadratic objective term. */
96 CHECK_RESULT(MDOaddqpterms(model, qo_nnz, qo_col1, qo_col2, qo_values));
97
98 /* Add quadratic constraints. */
99 CHECK_RESULT(MDOaddqconstr(model, row1_nnz, row1_idx, row1_val, qc1_nnz, qc1_col1, qc1_col2, qc1_values, MDO_GREATER_EQUAL, 1.0, "c0"));
100 CHECK_RESULT(MDOaddqconstr(model, row2_nnz, row2_idx, row2_val, qc2_nnz, qc2_col1, qc2_col2, qc2_values, MDO_LESS_EQUAL, 1.0, "c1"));
101
102 /*------------------------------------------------------------------*/
103 /* Step 3. Solve the problem and populate optimization result. */
104 /*------------------------------------------------------------------*/
105 /* Solve the problem. */
106 CHECK_RESULT(MDOoptimize(model));
107
108 CHECK_RESULT(MDOgetintattr(model, STATUS, &status));
109 if (status == MDO_OPTIMAL)
110 {
111 CHECK_RESULT(MDOgetdblattr(model, OBJ_VAL, &obj));
112 printf("The optimal objective value is: %f\n", obj);
113 for (int i = 0; i < 4; ++i)
114 {
115 CHECK_RESULT(MDOgetdblattrelement(model, X, i, &x));
116 printf("x[%d] = %f\n", i, x);
117 }
118 }
119 else
120 {
121 printf("No feasible solution.\n");
122 }
123
124 /*------------------------------------------------------------------*/
125 /* Step 4. Free the model. */
126 /*------------------------------------------------------------------*/
127 RELEASE_MEMORY;
128
129 return 0;
130}