Как использовать Gurobi для решения этой проблемы оптимизации? - PullRequest
Новая
       11

Как использовать Gurobi для решения этой проблемы оптимизации?

0 голосов
/ 15 ноября 2018

проблема заключается в следующем: 

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 и изучаю примеры LP, но объект примера похож на min x + y + 2 z. Я хочу знать, если Guribo может решить эту проблему, если ответ «да», как написать модель. Большое спасибо.

1 Ответ

0 голосов
/ 16 ноября 2018

Я должен признать, что я не большой поклонник Java, и я впервые использую Java-интерфейс Gurobi, так что это может быть не самым элегантным решением. В любом случае, вот способ смоделировать и решить вашу проблему в 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 - файл, содержащий решение.

Обратите внимание, что вам не нужно использовать Gurobi для такого простого LP. Есть несколько хороших некоммерческих решателей ( lp_solve или GLPK , например), которые могут легко решить эту проблему. С GLPK вы можете решить это через 

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

из командной строки. Флаг --cpxlp сообщает glpk, что model.lp записан в формате cplex, а -o solution.txt указывает glpk записать решение в файл solution.txt.

...