5.6.3. 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:
25#include "MindoptCpp.h"
Create an optimization model model:
32 /*------------------------------------------------------------------*/
33 /* Step 1. Create environment and model. */
34 /*------------------------------------------------------------------*/
35 MDOEnv env = MDOEnv();
36 MDOModel model = MDOModel(env);
Note
To mark a variable that is integer, set the value of vtype as MDO_INTEGER in MDOaddvar().
Next, we set the optimization sense to minimization via MDOModel::set(). Then, we call MDOModel::addVar() to add four variables, which define upper bounds, lower bounds, names and types.
(for more details on MDOModel::set() and MDOModel::addVar(), please refer to C++ API)
43 /* Change to minimization problem. */
44 model.set(MDO_IntAttr_ModelSense, MDO_MINIMIZE);
45
46 /* Add variables. */
47 std::vector<MDOVar> x;
48 x.push_back(model.addVar(0.0, 10.0, 0.0, MDO_INTEGER, "x0"));
49 x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, MDO_CONTINUOUS, "x1"));
50 x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, MDO_CONTINUOUS, "x2"));
51 x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, MDO_CONTINUOUS, "x3"));
Then, we set the quadratic objective via a quadratic expression MDOQuadExpr and call MDOQuadExpr::addTerms
to set the linear part of the objective function. obj_idx represents the indices of the linear terms, obj_val represents the corresponding non-zero coefficient values in obj_idx, and obj_nnz represents the number of non-zero elements in the linear part.
54 /* Linear part in the objective: 1 x0 + 1 x1 + 1 x2 + 1 x3 */
55 int obj_nnz = 4;
56 MDOVar obj_idx[] = { x[0], x[1], x[2], x[3]};
57 double obj_val[] = { 1.0, 1.0, 1.0, 1.0};
85 /* Create objective. */
86 MDOQuadExpr obj = MDOQuadExpr(0.0);
87 /* Add linear terms */
88 obj.addTerms(obj_val, obj_idx, obj_nnz);
We call MDOQuadExpr::addTerms
to set the quadratic terms of the objective. Here, qo_values represents the coefficients of all the non-zero quadratic terms, while qo_col1 and qo_col2 respectively represent its row and column indices. qo_nnz represents the number of non-zero quadratic terms.
58 /* Quadratic part in the objective: 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
59 int qo_nnz = 5;
60 MDOVar qo_col1[] = { x[0], x[1], x[2], x[3], x[0] };
61 MDOVar qo_col2[] = { x[0], x[1], x[2], x[3], x[1] };
62 double qo_values[] = { 0.5, 0.5, 0.5, 0.5, 0.5 };
89 /* Add quadratic terms */
90 obj.addTerms(qo_values, qo_col1, qo_col2, qo_nnz);
Lastly, we call MDOModel::setObjective to set the objective and the direction to be optimized.
104 /* Set optimization sense. */
105 model.setObjective(obj, MDO_MINIMIZE);
Now we start to add quadratic constraints to the model. The quadratic expression is constructed in the same way as in the objective.
64 /* Linear part in the first constraint: 1 x0 + 1 x1 + 2 x2 + 3 x3 */
65 int c1_nnz = 4;
66 MDOVar c1_idx[] = { x[0], x[1], x[2], x[3] };
67 double c1_val[] = { 1.0, 1.0, 2.0, 3.0 };
68 /* Quadratic part in the first constraint: - 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
69 int qc1_nnz = 5;
70 MDOVar qc1_col1[] = { x[0], x[1], x[2], x[3], x[0] };
71 MDOVar qc1_col2[] = { x[0], x[1], x[2], x[3], x[1] };
72 double qc1_values[] = { -0.5, -0.5, -0.5, -0.5, -0.5 };
93 MDOQuadExpr c1 = MDOQuadExpr(0.0);
94 c1.addTerms(c1_val, c1_idx, c1_nnz);
95 c1.addTerms(qc1_values, qc1_col1, qc1_col2, qc1_nnz);
74 /* Linear part in the second constraint: 1 x0 - 1 x2 + 6 x3 */
75 int c2_nnz = 3;
76 MDOVar c2_idx[] = { x[0], x[2], x[3] };
77 double c2_val[] = { 1.0, -1.0, 6.0 };
78 /* Quadratic part in the second constraint: 1/2 [x1^2] */
79 int qc2_nnz = 1;
80 MDOVar qc2_col1[] = { x[1] };
81 MDOVar qc2_col2[] = { x[1] };
82 double qc2_values[] = { 0.5 };
99 MDOQuadExpr c2 = MDOQuadExpr(0.0);
100 c2.addTerms(c2_val, c2_idx, c2_nnz);
101 c2.addTerms(qc2_values, qc2_col1, qc2_col2, qc2_nnz);
Then, we call MDOModel::addQConstr to add the quadratic constraints to the model.
96 model.addQConstr(c1, MDO_GREATER_EQUAL, 1.0, "c0");
102 model.addQConstr(c2, MDO_LESS_EQUAL, 1.0, "c1");
Once the model is constructed, we call MDOModel::optimize() to solve the problem:
110 /* Solve the problem. */
111 model.optimize();
The complete example code is shown in MdoMIQCPEx1.cpp :
1/**
2 * Description
3 * -----------
4 *
5 * Formulation
6 * -----------
7 *
8 * Minimize
9 * obj: 1 x0 + 1 x1 + 1 x2 + 1 x3
10 * + 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1]
11 *
12 * Subject To
13 * c0 : 1 x0 + 1 x1 + 2 x2 + 3 x3 - 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] >= 1
14 * c1 : 1 x0 - 1 x2 + 6 x3 + 1/2 [x1^2] <= 1
15 * Bounds
16 * 0 <= x0 <= 10
17 * 0 <= x1
18 * 0 <= x2
19 * 0 <= x3
20 * Integer
21 * x0
22 * End
23 */
24#include <iostream>
25#include "MindoptCpp.h"
26#include <vector>
27
28using namespace std;
29
30int main(void)
31{
32 /*------------------------------------------------------------------*/
33 /* Step 1. Create environment and model. */
34 /*------------------------------------------------------------------*/
35 MDOEnv env = MDOEnv();
36 MDOModel model = MDOModel(env);
37
38 try
39 {
40 /*------------------------------------------------------------------*/
41 /* Step 2. Input model. */
42 /*------------------------------------------------------------------*/
43 /* Change to minimization problem. */
44 model.set(MDO_IntAttr_ModelSense, MDO_MINIMIZE);
45
46 /* Add variables. */
47 std::vector<MDOVar> x;
48 x.push_back(model.addVar(0.0, 10.0, 0.0, MDO_INTEGER, "x0"));
49 x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, MDO_CONTINUOUS, "x1"));
50 x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, MDO_CONTINUOUS, "x2"));
51 x.push_back(model.addVar(0.0, MDO_INFINITY, 0.0, MDO_CONTINUOUS, "x3"));
52
53 /* Prepare model data. */
54 /* Linear part in the objective: 1 x0 + 1 x1 + 1 x2 + 1 x3 */
55 int obj_nnz = 4;
56 MDOVar obj_idx[] = { x[0], x[1], x[2], x[3]};
57 double obj_val[] = { 1.0, 1.0, 1.0, 1.0};
58 /* Quadratic part in the objective: 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
59 int qo_nnz = 5;
60 MDOVar qo_col1[] = { x[0], x[1], x[2], x[3], x[0] };
61 MDOVar qo_col2[] = { x[0], x[1], x[2], x[3], x[1] };
62 double qo_values[] = { 0.5, 0.5, 0.5, 0.5, 0.5 };
63
64 /* Linear part in the first constraint: 1 x0 + 1 x1 + 2 x2 + 3 x3 */
65 int c1_nnz = 4;
66 MDOVar c1_idx[] = { x[0], x[1], x[2], x[3] };
67 double c1_val[] = { 1.0, 1.0, 2.0, 3.0 };
68 /* Quadratic part in the first constraint: - 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
69 int qc1_nnz = 5;
70 MDOVar qc1_col1[] = { x[0], x[1], x[2], x[3], x[0] };
71 MDOVar qc1_col2[] = { x[0], x[1], x[2], x[3], x[1] };
72 double qc1_values[] = { -0.5, -0.5, -0.5, -0.5, -0.5 };
73
74 /* Linear part in the second constraint: 1 x0 - 1 x2 + 6 x3 */
75 int c2_nnz = 3;
76 MDOVar c2_idx[] = { x[0], x[2], x[3] };
77 double c2_val[] = { 1.0, -1.0, 6.0 };
78 /* Quadratic part in the second constraint: 1/2 [x1^2] */
79 int qc2_nnz = 1;
80 MDOVar qc2_col1[] = { x[1] };
81 MDOVar qc2_col2[] = { x[1] };
82 double qc2_values[] = { 0.5 };
83
84 /* Construct model. */
85 /* Create objective. */
86 MDOQuadExpr obj = MDOQuadExpr(0.0);
87 /* Add linear terms */
88 obj.addTerms(obj_val, obj_idx, obj_nnz);
89 /* Add quadratic terms */
90 obj.addTerms(qo_values, qo_col1, qo_col2, qo_nnz);
91
92 /* Add 1st quadratic constraint. */
93 MDOQuadExpr c1 = MDOQuadExpr(0.0);
94 c1.addTerms(c1_val, c1_idx, c1_nnz);
95 c1.addTerms(qc1_values, qc1_col1, qc1_col2, qc1_nnz);
96 model.addQConstr(c1, MDO_GREATER_EQUAL, 1.0, "c0");
97
98 /* Add 2nd quadratic constraint. */
99 MDOQuadExpr c2 = MDOQuadExpr(0.0);
100 c2.addTerms(c2_val, c2_idx, c2_nnz);
101 c2.addTerms(qc2_values, qc2_col1, qc2_col2, qc2_nnz);
102 model.addQConstr(c2, MDO_LESS_EQUAL, 1.0, "c1");
103
104 /* Set optimization sense. */
105 model.setObjective(obj, MDO_MINIMIZE);
106
107 /*------------------------------------------------------------------*/
108 /* Step 3. Solve the problem and populate optimization result. */
109 /*------------------------------------------------------------------*/
110 /* Solve the problem. */
111 model.optimize();
112
113 if(model.get(MDO_IntAttr_Status) == MDO_OPTIMAL)
114 {
115 cout << "Optimal objective value is: " << model.get(MDO_DoubleAttr_ObjVal) << endl;
116 cout << "Decision variables:" << endl;
117 int i = 0;
118 for (auto v : x)
119 {
120 cout << "x[" << i++ << "] = " << v.get(MDO_DoubleAttr_X) << endl;
121 }
122 }
123 else
124 {
125 cout<< "No feasible solution." << endl;
126 }
127
128 }
129 catch (MDOException& e)
130 {
131 std::cout << "Error code = " << e.getErrorCode() << std::endl;
132 std::cout << e.getMessage() << std::endl;
133 }
134 catch (...)
135 {
136 std::cout << "Error during optimization." << std::endl;
137 }
138
139 return static_cast<int>(MDO_OKAY);
140}