Very slow MIQCP- Problem with negative best bound and high MIP gap

[mayfam]

Hello,

I have a challenge with my MIQCP model which i believe Gurobi can handle since a smaller case was solved in 1minute.

It is a relatively large scheduling problem with 2550 variables and 101 linear constraints and 1 quadratic constraint. 

I can see that gurobi gives a feasible solution very early in the optimisation routine. 

However i noticed that the minimum of the optimal objective values from relaxation (best bound) gives a negative value and consequently led to a very high gap (200%) that shouldn't happen if all constraints were satisfied.

After running the optimization for 8 hours there is no significant improvement in the gap (still close to 200%). I have tried to tune the parameters with possible parameters such as MIPFocus but no improvement. 

The incumbent objective value is a feasible solution that is good enough for my purpose but the gap is large. What can be done to make the optimisation converge with low gap (<1%). Is there a numerical issue with my model that is given in the attached lp file?

Thanks in advance.

Stephen

[Ed Rothberg]

It solves in just over a second with PreQLinearize=1...

Explored 0 nodes (5484 simplex iterations) in 1.37 seconds

Best objective 3.324248000000e+05, best bound 3.324248000000e+05, gap 0.0%

[mayfam]

Thanks so much Ed. 

That's a perfect solution

Could you kindly explain (or give additional reference besides Gurobi reference manual) what PreQLinearize =1 does that is different from setting MIQP method=1?

All i know is that it linearizes the quadratic term in the obj. function or constraint. 

[David Nehme]

Stephen,
   Your problem is a pure binary problem.  I'll go on a limb to say there are no cases where you should put quadratic functions of binary variables into Gurobi.  For binary variables x*x == x, so terms like that are trivial to linearize.  For x*y, you can replace it with and new variable z and the constraints
z <= x
z <= y
z >= x + y - 1

That's some of what PreQLinearize does for you.

- David Nehme
  ne...@abremod.com