Friday, April 24, 2015

MIQP bounds and performance

Cplex automatic reformulations

The performance of MIQP models is not always predictable. Here are the results for a small model we used to reproduce a performance issue with Cplex:

image

Looks like Cplex is attempting a smart reformulation that fails terribly. An indication is the log line:

Reduced MIQP objective Q matrix has 1 nonzeros.

Also the negative best bound (compare this to the relaxed objective) is an indication.

There are two ways to fix the problem. A small reformulation that simplifies the objective, leads to much better performance:

image  

In this case the objective is written as a sum of squares of continuous variables, and this prohibits Cplex to do their reformulations. The second way is to use option qtolin and set it to zero.

image

See: http://www-01.ibm.com/support/knowledgecenter/SSSA5P_12.6.1/ilog.odms.cplex.help/CPLEX/Parameters/topics/QToLin.html?lang=en.

The same issue is discussed in:

With a slight variation of this model we can make Mosek look bad. This variant of the model can be easily linearized, which helps tremendously in this case.

image

The linearized model solves very easily, although there are some bugs with reporting the correct gap. This gap should be 0%, but instead we see:

Best possible: +inf
Absolute gap:       3.000000E+300
Relative gap:            1.000000

This could be related to the relaxed LP having integer values.