5.2.2. C 的MILP建模和优化¶
在本节中,我们将使用 MindOpt C API,以按行输入的形式来建模以及求解 混合整数线性规划问题示例 中的问题。
首先,引入头文件:
25#include <stdio.h>
创建优化模型:
58 /* Create an empty model. */
59 CHECK_RESULT(MDOemptyenv(&env));
60 CHECK_RESULT(MDOstartenv(env));
接下来,我们通过 MDOsetintattr()
将目标函数设置为 最小化,并调用 MDOaddvar()
来添加四个优化变量。(更多API和使用方式,请参考 C API):
65 /*------------------------------------------------------------------*/
66 /* Change to minimization problem. */
67 CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MINIMIZE));
68
69 /* Add variables. */
70 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, 10.0, MDO_INTEGER, "x0"));
71 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 2.0, 0, MDO_INFINITY, MDO_INTEGER, "x1"));
72 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_INTEGER, "x2"));
接下来添加线性约束,需要定义其中的非零元及其左右边界。我们使用以下四列数组来定义线性约束,其中, row1_idx
和 row2_idx
分别表示第一和第二个约束中非零元素的位置(索引),而 row1_val
和 row2_val
则是与之相对应的非零数值。
49 /* Model data. */
50 int row1_idx[] = { 0, 1, 2, 3 };
51 double row1_val[] = { 1.0, 1.0, 2.0, 3.0 };
52 int row2_idx[] = { 0, 2, 3 };
调用 MDOaddconstr()
来输入约束:
74 /* Add constraints. */
75 CHECK_RESULT(MDOaddconstr(m, 4, row1_idx, row1_val, MDO_GREATER_EQUAL, 1.0, "c0"));
问题输入完成后,再调用 MDOoptimize()
求解优化问题。
81 /*------------------------------------------------------------------*/
然后,我们可以通过获取属性值的方式来获取求解后的最优值 (optimal value) 和最优解 (optimal solution).
82 CHECK_RESULT(MDOoptimize(m));
83
84 /*------------------------------------------------------------------*/
85 /* Step 4. Retrive model status and objective. */
86 /* For MIP(MILP,MIQP, MIQCP) problems, if the solving process */
87 /* terminates early due to reasons such as timeout or interruption, */
88 /* the model status will indicate termination by timeout (or */
89 /* interruption, etc.). However, suboptimal solutions may still */
90 /* exist, making it necessary to check the SolCount property. */
91 /*------------------------------------------------------------------*/
92 CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
93 CHECK_RESULT(MDOgetintattr(m, SOL_COUNT, &solcount));
94 if (status == MDO_OPTIMAL || status == MDO_SUB_OPTIMAL || solcount != 0)
95 {
96 CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
97 printf("The optimal objective value is %f\n", obj);
最后,调用 MDOfreemodel()
和 MDOfreeenv()
来释放模型:
30#define RELEASE_MEMORY \
31 MDOfreemodel(m); \
32 MDOfreeenv(env);
102 printf("x%d = %f\n", i, x);
示例 MdoMiloEx1.c 提供了完整源代码:
1/**
2 * Description
3 * -----------
4 *
5 * Mixed Integer Linear optimization (row-wise input).
6 *
7 * Formulation
8 * -----------
9 *
10 * Minimize
11 * obj: 1 x0 + 2 x1 + 1 x2 + 1 x3
12 * Subject To
13 * c0 : 1 x0 + 1 x1 + 2 x2 + 3 x3 >= 1
14 * c1 : 1 x0 - 1 x2 + 6 x3 = 1
15 * Bounds
16 * 0 <= x0 <= 10
17 * 0 <= x1
18 * 0 <= x2
19 * 0 <= x3
20 * Integers
21 * x0 x1 x2
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(m); \
32 MDOfreeenv(env);
33#define CHECK_RESULT(code) { int res = code; if (res != 0) { fprintf(stderr, "Bad code: %d\n", res); RELEASE_MEMORY; exit(res); } }
34#define MODEL_NAME "MILP_01"
35#define MODEL_SENSE "ModelSense"
36#define SOL_COUNT "SolCount"
37#define STATUS "Status"
38#define OBJ_VAL "ObjVal"
39#define X "X"
40
41int main(void)
42{
43 /* Creat Model. */
44 MDOenv *env;
45 MDOmodel *m;
46 double obj, x;
47 int i, solcount, status;
48
49 /* Model data. */
50 int row1_idx[] = { 0, 1, 2, 3 };
51 double row1_val[] = { 1.0, 1.0, 2.0, 3.0 };
52 int row2_idx[] = { 0, 2, 3 };
53 double row2_val[] = { 1.0, -1.0, 6.0 };
54
55 /*------------------------------------------------------------------*/
56 /* Step 1. Create environment and model. */
57 /*------------------------------------------------------------------*/
58 /* Create an empty model. */
59 CHECK_RESULT(MDOemptyenv(&env));
60 CHECK_RESULT(MDOstartenv(env));
61 CHECK_RESULT(MDOnewmodel(env, &m, MODEL_NAME, 0, NULL, NULL, NULL, NULL, NULL));
62
63 /*------------------------------------------------------------------*/
64 /* Step 2. Input model. */
65 /*------------------------------------------------------------------*/
66 /* Change to minimization problem. */
67 CHECK_RESULT(MDOsetintattr(m, MODEL_SENSE, MDO_MINIMIZE));
68
69 /* Add variables. */
70 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, 10.0, MDO_INTEGER, "x0"));
71 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 2.0, 0, MDO_INFINITY, MDO_INTEGER, "x1"));
72 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_INTEGER, "x2"));
73 CHECK_RESULT(MDOaddvar(m, 0, NULL, NULL, 1.0, 0, MDO_INFINITY, MDO_CONTINUOUS, "x3"));
74
75 /* Add constraints. */
76 CHECK_RESULT(MDOaddconstr(m, 4, row1_idx, row1_val, MDO_GREATER_EQUAL, 1.0, "c0"));
77 CHECK_RESULT(MDOaddconstr(m, 3, row2_idx, row2_val, MDO_EQUAL, 1.0, "c1"));
78
79 /*------------------------------------------------------------------*/
80 /* Step 3. Solve the problem. */
81 /*------------------------------------------------------------------*/
82 CHECK_RESULT(MDOoptimize(m));
83
84 /*------------------------------------------------------------------*/
85 /* Step 4. Retrive model status and objective. */
86 /* For MIP(MILP,MIQP, MIQCP) problems, if the solving process */
87 /* terminates early due to reasons such as timeout or interruption, */
88 /* the model status will indicate termination by timeout (or */
89 /* interruption, etc.). However, suboptimal solutions may still */
90 /* exist, making it necessary to check the SolCount property. */
91 /*------------------------------------------------------------------*/
92 CHECK_RESULT(MDOgetintattr(m, STATUS, &status));
93 CHECK_RESULT(MDOgetintattr(m, SOL_COUNT, &solcount));
94 if (status == MDO_OPTIMAL || status == MDO_SUB_OPTIMAL || solcount != 0)
95 {
96 CHECK_RESULT(MDOgetdblattr(m, OBJ_VAL, &obj));
97 printf("The optimal objective value is %f\n", obj);
98
99 for (i = 0; i < 4; ++i)
100 {
101 CHECK_RESULT(MDOgetdblattrelement(m, X, i, &x));
102 printf("x%d = %f\n", i, x);
103 }
104 }
105 else
106 {
107 printf("No feasible solution exists\n");
108 }
109
110 /*------------------------------------------------------------------*/
111 /* Step 4. Free the model. */
112 /*------------------------------------------------------------------*/
113 RELEASE_MEMORY;
114
115 return 0;
116}