5.4.5. Java 的QCP建模和优化

在本节中,我们将使用 MindOpt JAVA API,以按行输入的形式来建模以及求解 二次约束规划问题示例 中的问题。

首先,引入头文件:

25import com.alibaba.damo.mindopt.*;

并创建优化模型:

30        // Create model
31        MDOEnv env = new MDOEnv(); 
32        MDOModel model = new MDOModel(env); 
33        model.set(MDO.StringAttr.ModelName, "QCP_01");

接下来,我们通过 MDOModel.set 将目标函数设置为 最小化,并调用 MDOModel.addVar 来添加四个优化变量,定义其下界、上界、名称和类型(有关 MDOModel.setMDOModel.addVar 的详细使用方式,请参考 JAVA API):

36            // Add variables.
37            MDOVar[] x = new MDOVar[4];
38            x[0] = model.addVar(0.0,         10.0, 0.0, 'C', "x0");
39            x[1] = model.addVar(0.0, MDO.INFINITY, 0.0, 'C', "x1");
40            x[2] = model.addVar(0.0, MDO.INFINITY, 0.0, 'C', "x2");
41            x[3] = model.addVar(0.0, MDO.INFINITY, 0.0, 'C', "x3");

接着我们开始设置二次目标函数。我们创建一个二次表达式 MDOQuadExpr , 再调用 MDOQuadExpr.addTerms 来设置目标函数线性部分。这里 obj_idx 表示线性部分的索引,obj_val 表示与 obj_idx 中的索引相对应的非零系数值。

44            /* Linear part in the objective: 1 x0 + 1 x1 + 1 x2 + 1 x3 */
45            int      obj_nnz = 4;
46            MDOVar[] obj_idx = new MDOVar[] { x[0], x[1], x[2], x[3] };
47            double[] obj_val = new double[] { 1.0,  1.0,  1.0,  1.0 };
75            // Create a QuadExpr for quadratic objective
76            MDOQuadExpr obj = new MDOQuadExpr();
77            // Add objective linear term: 1 x0 + 1 x1 + 1 x2 + 1 x3 
78            obj.addTerms(obj_val, obj_idx);

然后,调用 MDOQuadExpr.addTerms 来设置目标的二次项系数 \(Q\)。 其中,qo_values 表示要添加的二次项的系数,qo_col1qo_col2 表示与qo_values相对应的二次项的第一个变量和第二个变量。

48            /* Quadratic part in the objective: 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
49            int      qo_nnz    = 5;
50            MDOVar[] qo_col1   = new MDOVar[] { x[0], x[1], x[2], x[3], x[0] };
51            MDOVar[] qo_col2   = new MDOVar[] { x[0], x[1], x[2], x[3], x[1] };
52            double[] qo_values = new double[] { 0.5,  0.5,  0.5,  0.5,  0.5 };
79            // Add quadratic part in objective: 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] 
80            obj.addTerms(qo_values, qo_col1, qo_col2);

最后,我们调用 MDOModel.setObjective 设定优化目标与方向。

82            model.setObjective(obj, MDO.MINIMIZE);

现在我们开始添加二次约束。构建二次约束中的二次表达式的方式与二次目标函数类似。

54            /* Linear part in the first constraint: 1 x0 + 1 x1 + 2 x2 + 3 x3 */
55            int      c1_nnz = 4; 
56            MDOVar[] c1_idx = new MDOVar[] { x[0], x[1], x[2], x[3] };
57            double[] c1_val = new double[] { 1.0,  1.0,  2.0,  3.0 };
58            /* Quadratic part in the first constraint: - 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
59            int      qc1_nnz    = 5;
60            MDOVar[] qc1_col1   = new MDOVar[] { x[0], x[1], x[2], x[3], x[0] };
61            MDOVar[] qc1_col2   = new MDOVar[] { x[0], x[1], x[2], x[3], x[1] };
62            double[] qc1_values = new double[] { -0.5, -0.5, -0.5, -0.5, -0.5 };
84            // Add 1st quadratic constraint. 
85            MDOQuadExpr c1 = new MDOQuadExpr();
86            c1.addTerms(c1_val, c1_idx);
87            c1.addTerms(qc1_values, qc1_col1, qc1_col2);
64            /* Linear part in the second constraint: 1 x0 - 1 x2 + 6 x3 */
65            int      c2_nnz = 3;
66            MDOVar[] c2_idx = new MDOVar[] { x[0], x[2], x[3] };
67            double[] c2_val = new double[] { 1.0,  -1.0, 6.0 };
68            /* Quadratic part in the second constraint: 1/2 [x1^2] */
69            int      qc2_nnz    = 1;
70            MDOVar[] qc2_col1   = new MDOVar[] { x[1] };
71            MDOVar[] qc2_col2   = new MDOVar[] { x[1] };
72            double[] qc2_values = new double[] { 0.5 };
90            // Add 2nd quadratic constraint. 
91            MDOQuadExpr c2 = new MDOQuadExpr();
92            c2.addTerms(c2_val, c2_idx);
93            c2.addTerms(qc2_values, qc2_col1, qc2_col2);

然后,我们调用 MDOModel.addQConstr 将二次约束添加至模型中。

88            model.addQConstr(c1, MDO.GREATER_EQUAL, 1.0, "c0");
94            model.addQConstr(c2, MDO.LESS_EQUAL, 1.0, "c1");  

问题输入完成后,调用 MDOModel.optimize 求解优化问题:

96            // Solve the problem and populate optimization result.
97            model.optimize();

示例 MdoQcoEx1.java 提供了完整源代码:

  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
 25import com.alibaba.damo.mindopt.*;
 26import java.util.*;
 27
 28public class MdoQcoEx1 { 
 29    public static void main(String[] args) throws MDOException {
 30        // Create model
 31        MDOEnv env = new MDOEnv(); 
 32        MDOModel model = new MDOModel(env); 
 33        model.set(MDO.StringAttr.ModelName, "QCP_01");
 34
 35        try {
 36            // Add variables.
 37            MDOVar[] x = new MDOVar[4];
 38            x[0] = model.addVar(0.0,         10.0, 0.0, 'C', "x0");
 39            x[1] = model.addVar(0.0, MDO.INFINITY, 0.0, 'C', "x1");
 40            x[2] = model.addVar(0.0, MDO.INFINITY, 0.0, 'C', "x2");
 41            x[3] = model.addVar(0.0, MDO.INFINITY, 0.0, 'C', "x3");
 42
 43            /* Prepare model data. */
 44            /* Linear part in the objective: 1 x0 + 1 x1 + 1 x2 + 1 x3 */
 45            int      obj_nnz = 4;
 46            MDOVar[] obj_idx = new MDOVar[] { x[0], x[1], x[2], x[3] };
 47            double[] obj_val = new double[] { 1.0,  1.0,  1.0,  1.0 };
 48            /* Quadratic part in the objective: 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
 49            int      qo_nnz    = 5;
 50            MDOVar[] qo_col1   = new MDOVar[] { x[0], x[1], x[2], x[3], x[0] };
 51            MDOVar[] qo_col2   = new MDOVar[] { x[0], x[1], x[2], x[3], x[1] };
 52            double[] qo_values = new double[] { 0.5,  0.5,  0.5,  0.5,  0.5 };
 53
 54            /* Linear part in the first constraint: 1 x0 + 1 x1 + 2 x2 + 3 x3 */
 55            int      c1_nnz = 4; 
 56            MDOVar[] c1_idx = new MDOVar[] { x[0], x[1], x[2], x[3] };
 57            double[] c1_val = new double[] { 1.0,  1.0,  2.0,  3.0 };
 58            /* Quadratic part in the first constraint: - 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] */
 59            int      qc1_nnz    = 5;
 60            MDOVar[] qc1_col1   = new MDOVar[] { x[0], x[1], x[2], x[3], x[0] };
 61            MDOVar[] qc1_col2   = new MDOVar[] { x[0], x[1], x[2], x[3], x[1] };
 62            double[] qc1_values = new double[] { -0.5, -0.5, -0.5, -0.5, -0.5 };
 63
 64            /* Linear part in the second constraint: 1 x0 - 1 x2 + 6 x3 */
 65            int      c2_nnz = 3;
 66            MDOVar[] c2_idx = new MDOVar[] { x[0], x[2], x[3] };
 67            double[] c2_val = new double[] { 1.0,  -1.0, 6.0 };
 68            /* Quadratic part in the second constraint: 1/2 [x1^2] */
 69            int      qc2_nnz    = 1;
 70            MDOVar[] qc2_col1   = new MDOVar[] { x[1] };
 71            MDOVar[] qc2_col2   = new MDOVar[] { x[1] };
 72            double[] qc2_values = new double[] { 0.5 };
 73
 74            /* Construct model. */
 75            // Create a QuadExpr for quadratic objective
 76            MDOQuadExpr obj = new MDOQuadExpr();
 77            // Add objective linear term: 1 x0 + 1 x1 + 1 x2 + 1 x3 
 78            obj.addTerms(obj_val, obj_idx);
 79            // Add quadratic part in objective: 1/2 [ x0^2 + x1^2 + x2^2 + x3^2 + x0 x1] 
 80            obj.addTerms(qo_values, qo_col1, qo_col2);
 81
 82            model.setObjective(obj, MDO.MINIMIZE);
 83
 84            // Add 1st quadratic constraint. 
 85            MDOQuadExpr c1 = new MDOQuadExpr();
 86            c1.addTerms(c1_val, c1_idx);
 87            c1.addTerms(qc1_values, qc1_col1, qc1_col2);
 88            model.addQConstr(c1, MDO.GREATER_EQUAL, 1.0, "c0");
 89
 90            // Add 2nd quadratic constraint. 
 91            MDOQuadExpr c2 = new MDOQuadExpr();
 92            c2.addTerms(c2_val, c2_idx);
 93            c2.addTerms(qc2_values, qc2_col1, qc2_col2);
 94            model.addQConstr(c2, MDO.LESS_EQUAL, 1.0, "c1");  
 95    
 96            // Solve the problem and populate optimization result.
 97            model.optimize();
 98
 99            if (model.get(MDO.IntAttr.Status) == MDO.OPTIMAL) {
100                System.out.println("Optimal objective value is: " + model.get(MDO.DoubleAttr.ObjVal));
101                System.out.println("Decision variables: ");
102                for (int i = 0; i < 4; i++) {
103                    System.out.println( "x[" + i + "] = " + x[i].get(MDO.DoubleAttr.X));
104                }
105            }
106            else {
107                System.out.println("No feasible solution.");
108            }
109        } catch (Exception e) { 
110            System.out.println("Exception during optimization");
111            e.printStackTrace();
112        } finally { 
113            model.dispose();
114            env.dispose();
115        }
116    }
117}