5.5.2. MIQP 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 Quadratic Programming.
First of all, include the header files:
29#include "Mindopt.h"
Create an optimization model m:
93 CHECK_RESULT(MDOemptyenv(&env));
94 CHECK_RESULT(MDOstartenv(env));
95 CHECK_RESULT(MDOnewmodel(env, &model, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
Next, we set the optimization sense to minimization via MDOsetintattr() and add four decision variables using MDOaddvar() (please refer to C API for more detailed usages of C API):
105 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, 10.0, MDO_INTEGER, "x0"));
106 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 2.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x1"));
107 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x2"));
108 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x3"));
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.
68 int qo_col1[] =
69 {
70 0,
71 1, 1,
72 2,
73 3
74 };
75 int qo_col2[] =
76 {
77 0,
78 0, 1,
79 2,
80 3
81 };
82 double qo_values[] =
83 {
84 1.0,
85 0.5, 1.0,
86 1.0,
87 1.0
88 };
We call MDOaddconstr() to input the linear constraints into the model m:
68 int qo_col1[] =
69 {
70 0,
71 1, 1,
72 2,
73 3
74 };
75 int qo_col2[] =
76 {
77 0,
78 0, 1,
79 2,
80 3
81 };
82 double qo_values[] =
83 {
84 1.0,
85 0.5, 1.0,
86 1.0,
87 1.0
88 };
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.
110 /* Add constraints.
111 * Note that the nonzero elements are inputted in a row-wise order here.
Once the model is constructed, we call MDOoptimize() to solve the problem:
116 /* Add quadratic objective term. */
117 CHECK_RESULT(MDOaddqpterms(model, 5, qo_col1, qo_col2, qo_values));
Then, we can retrieive the optimal objective value and solutions as follows:
128 {
129 CHECK_RESULT(MDOgetdblattr(model, OBJ_VAL, &obj));
130 printf("The optimal objective value is: %f\n", obj);
131 for (int i = 0; i < 4; ++i)
132 {
133 CHECK_RESULT(MDOgetdblattrelement(model, X, i, &x));
134 printf("x[%d] = %f\n", i, x);
135 }
136 }
137 else
Lastly, we call MDOfreemodel() and MDOfreeenv() to free the model:
30/* Macro to check the return code */
31#define RELEASE_MEMORY \
146
Complete example codes are provided in MdoMIQPEx1.c.
1/**
2 * Description
3 * -----------
4 *
5 * Mixed Integer 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 * Integers
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 "MIQCP_01"
37#define MODEL_SENSE "ModelSense"
38#define STATUS "Status"
39#define OBJ_VAL "ObjVal"
40#define X "X"
41
42int main(void)
43{
44 /* Variables. */
45 MDOenv *env;
46 MDOmodel *model;
47 double obj, x;
48 int status, i;
49
50 /* Model data. */
51 int row1_idx[] = { 0, 1, 2, 3 };
52 double row1_val[] = { 1.0, 1.0, 2.0, 3.0 };
53 int row2_idx[] = { 0, 2, 3 };
54 double row2_val[] = { 1.0, -1.0, 6.0 };
55
56 /* Quadratic objective matrix Q.
57 *
58 * Note.
59 * 1. The objective function is defined as c^Tx + 1/2 x^TQx, where Q is stored with coordinate format.
60 * 2. Q will be scaled by 1/2 internally.
61 * 3. To ensure the symmetricity of Q, user needs to input only the lower triangular part.
62 *
63 * Q = [ 1.0 0.5 0 0 ]
64 * [ 0.5 1.0 0 0 ]
65 * [ 0.0 0.0 1.0 0 ]
66 * [ 0 0 0 1.0 ]
67 */
68 int qo_col1[] =
69 {
70 0,
71 1, 1,
72 2,
73 3
74 };
75 int qo_col2[] =
76 {
77 0,
78 0, 1,
79 2,
80 3
81 };
82 double qo_values[] =
83 {
84 1.0,
85 0.5, 1.0,
86 1.0,
87 1.0
88 };
89
90 /*------------------------------------------------------------------*/
91 /* Step 1. Create environment and model. */
92 /*------------------------------------------------------------------*/
93 CHECK_RESULT(MDOemptyenv(&env));
94 CHECK_RESULT(MDOstartenv(env));
95 CHECK_RESULT(MDOnewmodel(env, &model, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
96
97
98 /*------------------------------------------------------------------*/
99 /* Step 2. Input model. */
100 /*------------------------------------------------------------------*/
101 /* Change to minimization problem. */
102 CHECK_RESULT(MDOsetintattr(model, MODEL_SENSE, MDO_MINIMIZE));
103
104 /* Add variables. */
105 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, 10.0, MDO_INTEGER, "x0"));
106 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 2.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x1"));
107 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x2"));
108 CHECK_RESULT(MDOaddvar(model, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x3"));
109
110 /* Add constraints.
111 * Note that the nonzero elements are inputted in a row-wise order here.
112 */
113 CHECK_RESULT(MDOaddconstr(model, 4, row1_idx, row1_val, MDO_GREATER_EQUAL, 1.0, "c0"));
114 CHECK_RESULT(MDOaddconstr(model, 3, row2_idx, row2_val, MDO_EQUAL, 1.0, "c1"));
115
116 /* Add quadratic objective term. */
117 CHECK_RESULT(MDOaddqpterms(model, 5, qo_col1, qo_col2, qo_values));
118
119 /*------------------------------------------------------------------*/
120 /* Step 3. Solve the problem and populate optimization result. */
121 /*------------------------------------------------------------------*/
122 /* Solve the problem. */
123 CHECK_RESULT(MDOoptimize(model));
124
125
126 CHECK_RESULT(MDOgetintattr(model, STATUS, &status));
127 if (status == MDO_OPTIMAL)
128 {
129 CHECK_RESULT(MDOgetdblattr(model, OBJ_VAL, &obj));
130 printf("The optimal objective value is: %f\n", obj);
131 for (int i = 0; i < 4; ++i)
132 {
133 CHECK_RESULT(MDOgetdblattrelement(model, X, i, &x));
134 printf("x[%d] = %f\n", i, x);
135 }
136 }
137 else
138 {
139 printf("No feasible solution.\n");
140 }
141
142 /*------------------------------------------------------------------*/
143 /* Step 4. Free the model. */
144 /*------------------------------------------------------------------*/
145 RELEASE_MEMORY;
146
147 return 0;
148}