5.3.2. QP Modeling and Optimization in C¶
In this chapter, we will use MindOpt C API to model and solve the problem in Example of Quadratic Programming.
Include the header file:
27#include "Mindopt.h"
Create an optimization model model:
91 CHECK_RESULT(MDOemptyenv(&env));
92 CHECK_RESULT(MDOstartenv(env));
93 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, and types are defined as follows (for more details on how to use MDOsetIntAttr() and MDOaddvar(), please refer to Attributes):
99 /* Change to minimization problem. */
100 CHECK_RESULT(MDOsetintattr(model, MODEL_SENSE, MDO_MINIMIZE));
101
102 /* Add variables. */
103 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, 10.0, MDO_CONTINUOUS, "x0"));
104 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 2.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x1"));
105 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x2"));
106 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.
Now we set the constraint matrix \(A\) following the same procedure as in LP. The arrays row1_idx and row2_idx represent positions of the non-zero elements in the first and second rows while row1_val and row2_val represent corresponding values of the non-zero elements.
48 /* Model data. */
49 int row1_idx[] = { 0, 1, 2, 3 };
50 double row1_val[] = { 1.0, 1.0, 2.0, 3.0 };
51 int row2_idx[] = { 0, 2, 3 };
52 double row2_val[] = { 1.0, -1.0, 6.0 };
We call MDOaddconstr() to input the linear constraints into model:
108 /* Add constraints.
109 * Note that the nonzero elements are inputted in a row-wise order here.
110 */
111 CHECK_RESULT(MDOaddconstr(model, 4, row1_idx, row1_val, MDO_GREATER_EQUAL, 1.0, "c0"));
112 CHECK_RESULT(MDOaddconstr(model, 3, row2_idx, row2_val, MDO_EQUAL, 1.0, "c1"));
Next, we will introduce the coefficient matrix \(Q\) of the quadratic term in quadratic programming. 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 terms in the lower triangular part of \(Q\), respectively.
Note
To ensure symmetry, users need to input only its lower triangular part.
54 /* Quadratic objective matrix Q.
55 *
56 * Note.
57 * 1. The objective function is defined as c^Tx + 1/2 x^TQx, where Q is stored with coordinate format.
58 * 2. Q will be scaled by 1/2 internally.
59 * 3. To ensure the symmetricity of Q, user needs to input only the lower triangular part.
60 *
61 * Q = [ 1.0 0.5 0 0 ]
62 * [ 0.5 1.0 0 0 ]
63 * [ 0.0 0.0 1.0 0 ]
64 * [ 0 0 0 1.0 ]
65 */
66 int qo_col1[] =
67 {
68 0,
69 1, 1,
70 2,
71 3
72 };
73 int qo_col2[] =
74 {
75 0,
76 0, 1,
77 2,
78 3
79 };
80 double qo_values[] =
81 {
82 1.0,
83 0.5, 1.0,
84 1.0,
85 1.0
86 };
We call MDOaddqpterms() to set the quadratic terms of the objective. Here the argument “5” represents the length of the three arrays qo_col1, qo_col2, and qo_values:
114 /* Add quadratic objective term. */
115 CHECK_RESULT(MDOaddqpterms(model, 5, qo_col1, qo_col2, qo_values));
Once the model is constructed, we call MDOoptimize() to solve the problem:
117 /*------------------------------------------------------------------*/
118 /* Step 3. Solve the problem and populate optimization result. */
119 /*------------------------------------------------------------------*/
120 /* Solve the problem. */
121 CHECK_RESULT(MDOoptimize(model));
We can retrieive the optimal objective value and solutions via getting attributes:
124 CHECK_RESULT(MDOgetintattr(model, STATUS, &status));
125 if (status == MDO_OPTIMAL)
126 {
127 CHECK_RESULT(MDOgetdblattr(model, OBJ_VAL, &obj));
128 printf("The optimal objective value is: %f\n", obj);
129 for (int i = 0; i < 4; ++i)
130 {
131 CHECK_RESULT(MDOgetdblattrelement(model, X, i, &x));
132 printf("x[%d] = %f\n", i, x);
133 }
134 }
135 else
136 {
137 printf("No feasible solution.\n");
138 }
Finally, we call MDOfreemodel() and MDOfreeenv() to free the model:
30#define RELEASE_MEMORY \
31 MDOfreemodel(model); \
32 MDOfreeenv(env);
143 RELEASE_MEMORY;
The complete example code is provided in MdoQoEx1.c:
1/**
2 * Description
3 * -----------
4 *
5 * Quadratic optimization (row-wise input).
6 *
7 * Formulation
8
9 * -----------
10 *
11 * Minimize
12 * obj: 1 x0 + 1 x1 + 1 x2 + 1 x3
13 * + 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1]
14 * Subject To
15 * c0 : 1 x0 + 1 x1 + 2 x2 + 3 x3 >= 1
16 * c1 : 1 x0 - 1 x2 + 6 x3 = 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 "QP_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 /* Model data. */
49 int row1_idx[] = { 0, 1, 2, 3 };
50 double row1_val[] = { 1.0, 1.0, 2.0, 3.0 };
51 int row2_idx[] = { 0, 2, 3 };
52 double row2_val[] = { 1.0, -1.0, 6.0 };
53
54 /* Quadratic objective matrix Q.
55 *
56 * Note.
57 * 1. The objective function is defined as c^Tx + 1/2 x^TQx, where Q is stored with coordinate format.
58 * 2. Q will be scaled by 1/2 internally.
59 * 3. To ensure the symmetricity of Q, user needs to input only the lower triangular part.
60 *
61 * Q = [ 1.0 0.5 0 0 ]
62 * [ 0.5 1.0 0 0 ]
63 * [ 0.0 0.0 1.0 0 ]
64 * [ 0 0 0 1.0 ]
65 */
66 int qo_col1[] =
67 {
68 0,
69 1, 1,
70 2,
71 3
72 };
73 int qo_col2[] =
74 {
75 0,
76 0, 1,
77 2,
78 3
79 };
80 double qo_values[] =
81 {
82 1.0,
83 0.5, 1.0,
84 1.0,
85 1.0
86 };
87
88 /*------------------------------------------------------------------*/
89 /* Step 1. Create environment and model. */
90 /*------------------------------------------------------------------*/
91 CHECK_RESULT(MDOemptyenv(&env));
92 CHECK_RESULT(MDOstartenv(env));
93 CHECK_RESULT(MDOnewmodel(env, &model, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
94
95
96 /*------------------------------------------------------------------*/
97 /* Step 2. Input model. */
98 /*------------------------------------------------------------------*/
99 /* Change to minimization problem. */
100 CHECK_RESULT(MDOsetintattr(model, MODEL_SENSE, MDO_MINIMIZE));
101
102 /* Add variables. */
103 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, 10.0, MDO_CONTINUOUS, "x0"));
104 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 2.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x1"));
105 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x2"));
106 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x3"));
107
108 /* Add constraints.
109 * Note that the nonzero elements are inputted in a row-wise order here.
110 */
111 CHECK_RESULT(MDOaddconstr(model, 4, row1_idx, row1_val, MDO_GREATER_EQUAL, 1.0, "c0"));
112 CHECK_RESULT(MDOaddconstr(model, 3, row2_idx, row2_val, MDO_EQUAL, 1.0, "c1"));
113
114 /* Add quadratic objective term. */
115 CHECK_RESULT(MDOaddqpterms(model, 5, qo_col1, qo_col2, qo_values));
116
117 /*------------------------------------------------------------------*/
118 /* Step 3. Solve the problem and populate optimization result. */
119 /*------------------------------------------------------------------*/
120 /* Solve the problem. */
121 CHECK_RESULT(MDOoptimize(model));
122
123
124 CHECK_RESULT(MDOgetintattr(model, STATUS, &status));
125 if (status == MDO_OPTIMAL)
126 {
127 CHECK_RESULT(MDOgetdblattr(model, OBJ_VAL, &obj));
128 printf("The optimal objective value is: %f\n", obj);
129 for (int i = 0; i < 4; ++i)
130 {
131 CHECK_RESULT(MDOgetdblattrelement(model, X, i, &x));
132 printf("x[%d] = %f\n", i, x);
133 }
134 }
135 else
136 {
137 printf("No feasible solution.\n");
138 }
139
140 /*------------------------------------------------------------------*/
141 /* Step 4. Free the model. */
142 /*------------------------------------------------------------------*/
143 RELEASE_MEMORY;
144
145 return 0;
146}