时间戳

首页 > 解决方案 > 如何使用 Gurobi 解决这个优化问题？

java - 如何使用 Gurobi 解决这个优化问题？

问题描述

问题如下：

object:min z
s.t.
 r1 >= 0 
 r2 >= 0
 r3 >= 0 
 r1 + r2 + r3 = 1
 15 * (1 - r1) <= z
 12 * (1 - r2) <= z
 12 * (1 - r3) <= z
 240 * r1 <= z
 27 * r2 <= z
 27 * r3 <= z

或喜欢这种格式：

object:
 min z; z = max( 15 * (1 - r1), 12 * (1 - r2), 12 * (1 - r3) ,240 * r1, 27 * r2, 27 * r3)
s.t.
 r1 >= 0 
 r2 >= 0
 r3 >= 0 
 r1 + r2 + r3 = 1

这个问题来自一篇论文，在这篇论文中，作者使用 Gurobi 来解决这个问题。我下载了 Gurobi 并研究了 LP 示例，但示例的对象是min x + y + 2 z. 我想知道Guribo是否可以解决这个问题，如果答案是肯定的，如何编写模型。十分感谢。

标签： javagurobi

解决方案

我应该承认我不是 java 的忠实粉丝，这是我第一次使用 Gurobi 的 Java 接口，所以它可能不是最优雅的解决方案。无论如何，这是一种在 Java 中建模和解决问题的方法：

// example.java
import gurobi.*;

public class example {
  public static void main(String[] args) {
    try {
      GRBEnv    env   = new GRBEnv("example.log");
      GRBModel  model = new GRBModel(env);

      // Create variables
      GRBVar r1 = model.addVar(0.0, GRB.INFINITY, 0.0, GRB.CONTINUOUS, "r1");
      GRBVar r2 = model.addVar(0.0, GRB.INFINITY, 0.0, GRB.CONTINUOUS, "r2");
      GRBVar r3 = model.addVar(0.0, GRB.INFINITY, 0.0, GRB.CONTINUOUS, "r3");
      GRBVar z = model.addVar(-GRB.INFINITY, GRB.INFINITY, 1.0, GRB.CONTINUOUS, "z");

      // Set objective: minimize z
      GRBLinExpr expr = new GRBLinExpr();
      expr.addTerm(1.0, z);
      model.setObjective(expr, GRB.MINIMIZE);

      // Add constraint: r1 + r2 + r3 = 1
      expr = new GRBLinExpr();
      expr.addTerm(1.0, r1); expr.addTerm(1.0, r2); expr.addTerm(1.0, r3);
      model.addConstr(expr, GRB.EQUAL, 1.0, "c0");

      // Add constraint: 15 * (1-r1) <= z  <-> -15 r1 - z <= -15
      expr = new GRBLinExpr();
      expr.addTerm(-15.0, r1); expr.addTerm(-1.0, z);
      model.addConstr(expr, GRB.LESS_EQUAL, -15.0, "c1");

      // Add constraint: 12 * (1-r2) <= z  <-> -12 r2 - z <= -12
      expr = new GRBLinExpr();
      expr.addTerm(-12.0, r2); expr.addTerm(-1.0, z);
      model.addConstr(expr, GRB.LESS_EQUAL, -12.0, "c1");

      // Add constraint: 12 * (1-r3) <= z  <-> -12 r3 - z <= -12
      expr = new GRBLinExpr();
      expr.addTerm(-12.0, r3); expr.addTerm(-1.0, z);
      model.addConstr(expr, GRB.LESS_EQUAL, -12.0, "c1");

      // Add constraint: 240 r1 <= z  <-> 240 r1 - z <= 0
      expr = new GRBLinExpr();
      expr.addTerm(240.0, r1); expr.addTerm(-1.0, z);
      model.addConstr(expr, GRB.LESS_EQUAL, 0.0, "c1");

      // Add constraint: 27 r2 <= z  <-> 27 r2 - z <= 0
      expr = new GRBLinExpr();
      expr.addTerm(27.0, r2); expr.addTerm(-1.0, z);
      model.addConstr(expr, GRB.LESS_EQUAL, 0.0, "c1");

      // Add constraint: 27 r3 <= z  <-> 27 r3 - z <= 0
      expr = new GRBLinExpr();
      expr.addTerm(27.0, r3); expr.addTerm(-1.0, z);
      model.addConstr(expr, GRB.LESS_EQUAL, 0.0, "c1");

      // Optimize model
      model.write("model.lp");
      model.optimize();

      System.out.println(r1.get(GRB.StringAttr.VarName)
                         + " " +r1.get(GRB.DoubleAttr.X));
      System.out.println(r2.get(GRB.StringAttr.VarName)
                         + " " +r2.get(GRB.DoubleAttr.X));
      System.out.println(r3.get(GRB.StringAttr.VarName)
                         + " " +r3.get(GRB.DoubleAttr.X));

      System.out.println("Obj: " + model.get(GRB.DoubleAttr.ObjVal));

      // Dispose of model and environment

      model.dispose();
      env.dispose();

    } catch (GRBException e) {
      System.out.println("Error code: " + e.getErrorCode() + ". " +
                         e.getMessage());
    }
  }
}

这还将创建一个model.lp包含您的 LP 的文件：

Minimize
    obj: z
Subject To
    c0: r1 + r2 + r3 = 1
    c1: -15 r1 - z <= -15
    c2: -12 r2 - z <= -12
    c3: -12 r3 - z <= -12
    c4: 240 r1 - z <= 0
    c5: 27 r2 - z <= 0
    c6: 27 r3 - z <= 0
Bounds
    r1 >= 0
    r2 >= 0
    r3 >= 0
End

对于这样一个小问题，我建议将您的 LP 直接写入这样的模型文件中。然后你可以通过Gurobi 的命令行工具从命令行解决它：

gurobi_cl ResultFile=model.sol model.lp

model.sol包含解决方案的文件在哪里。

请注意，对于这样一个简单的 LP，您不需要使用 Gurobi。有一些很好的非商业求解器（ 例如lp_solve或GLPK）可以轻松解决这个问题。使用 GLPK，您可以通过

glpsol --cpxlp model.lp -o solution.txt

从命令行。该--cpxlp标志告诉glpk model.lp 以cplex 格式写入，同时-o solution.txt告诉glpk 将解决方案写入文件solution.txt。

推荐阅读