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 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

This can be reformulated to

where

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: