在 Gurobi 中求解混合整数二次规划 (MIQP) 的问题

Question

我需要你的帮助。对于我的论文，我需要使用 Gurobi 解决具有二次约束的混合整数二次问题 (MIQP)。当我将问题写入文件时，实现很好，解决部分就是问题，因为最佳界限和 objective 是 0 ......这不可能！问题定义：

          maximize: \sum_{i \in A, j \in Q} c_ij*x_ij

          \sum_{i \in A} c_ij*x_ij <= B_i
                              c_ij <= b_ij 
                        x_ij, c_ij >=0

使用Java接口实现：

    public class Gurobi_mod {
public static int m = 10; //number of items
public static int n = 5; //number of agents 
public static double b_ij[][] = new double [n][m];
public static double B_i[] = new double [n];

public static void main(String[] args) throws IOException {

    try {

    GRBEnv env = new GRBEnv();
    GRBModel model = new GRBModel(env);

      GRBVar[][] xij = new GRBVar[n][m];
      for (int i = 0; i < n; i++){
          for (int j = 0; j < m; j++){
              xij[i][j] =
                        model.addVar(0.0, 1.0, 1, GRB.BINARY, "x" + i + "," + j);
          }
      }
      model.update();
      GRBVar[][] cij = new GRBVar[n][m];
        for (int i = 0; i < n; i++){
          for (int j = 0; j < m; j++){
              cij[i][j] =
                        model.addVar(0.0, GRB.INFINITY, 1, GRB.CONTINUOUS, "c" + i + "," + j); 
          }
        }

        model.update();
        double coeff = 1;

        GRBQuadExpr linearobj = new GRBQuadExpr();
        for (int i = 0; i < n; ++i){
            GRBQuadExpr obj = new GRBQuadExpr();
              for (int j = 0; j < m; ++j){
                  obj.addTerm(1, xij[i][j], cij[i][j]);
              }
              linearobj.multAdd (coeff, obj);//addTerm(coeff, var);add(obj);
        }

        model.setObjective(linearobj, GRB.MAXIMIZE);
        model.update();    


    for (int i = 0; i < n; i++){
        GRBQuadExpr thexpr1 = new GRBQuadExpr();
        for (int j = 0; j < m; j++){
            thexpr1.addTerm(1, cij[i][j], xij[i][j]);   
        }
        model.addQConstr(thexpr1, GRB.LESS_EQUAL, B_i[i], "Budget"+ i); 
    }
    model.update();  

    for (int j = 0; j < m; ++j){    
        GRBLinExpr thexpr = new GRBLinExpr();
        for (int i = 0; i < n; ++i){            
            thexpr.addTerm(1, xij[i][j]);               
        }
        model.addConstr(thexpr, GRB.LESS_EQUAL, 1, "Item"+j);
    }
    model.update();  

    for (int i = 0; i < n; i++){    
        for (int j = 0; j < m; j++){
            GRBLinExpr thexprcij = new GRBLinExpr();
            thexprcij.addTerm(1, cij [i][j]);   
            model.addConstr(thexprcij, GRB.LESS_EQUAL, b_ij[i][j], "Bid"+ i + j);   
        }
    }

    // Solve 
    model.optimize();

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

Gurobi能否解决这种混合整数二次问题，因为变量x_ij是BINARY而c_ij是CONTINUOUS。如果我将 c_ij 也设置为 BINARY，我会得到一个合理的结果。这是否意味着问题不是凹最大化问题？？？（据我所知Gurobi只能解决这种特殊的MIQP）。提前致谢！！

Answer 1

A new reformulation-linearization technique for bilinear programming problems 经历了一种对您的问题有用的重新表述技术。假设我没看错，下面是你的优化问题

这可以重新表述为

哪里

这个重新表述的问题是一个 MILP，在 Gurobi 中应该很容易解决。

编辑： 由于 b 是 c 的上限，问题可以更简单地写为：

在 Gurobi 中求解混合整数二次规划 (MIQP) 的问题

Problems solving a mixed integer quadratic program (MIQP) in Gurobi

java

gurobi