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

erda Source

I need your help. For my thesis i need to solve a mixed integer quadratic problem (MIQP) with quadratic constraints using Gurobi. When I write the problem into a file the implementation is fine, the solving part is the problem because the best bound and objective for it is 0....... which can't be! Definition of the problem:

          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

Implementation Using Java interface:

    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());
    }
  }
 }

Can Gurobi solve this kind of mixed integer quadratic problem, since the variable x_ij is BINARY and c_ij is CONTINUOUS. If I set c_ij to be also BINARY i get a plausible result. Does this mean that the problem is not a concave maximisation problem??? (As far as i know Gurobi can solve only this kind of special MIQP). Thanks in advance!!

javagurobi

Answers

answered 4 years ago cdhagmann #1

A new reformulation-linearization technique for bilinear programming problems goes through a reformulation technique that would be useful for your problem. Assuming I understand you right, the below is your optimization problem

enter image description here

This can be reformulated to

enter image description here

where

enter image description here

This reformulated problem is a MILP and should be easy to solve in Gurobi.

EDIT: As b is the upper bound of c the problem could be written more simply as:

enter image description here

comments powered by Disqus