Friday, November 30, 2012

Don’t always trust what a solver is saying

This is supposed to be a fairly difficult MIQP. However, when I run it I get quickly: INFEASIBLE:

Tried aggregator 2 times.
MIQP Presolve eliminated 1 rows and 1 columns.
MIQP Presolve modified 248 coefficients.
Aggregator did 52 substitutions.
Reduced MIQP has 125 rows, 548 columns, and 3696 nonzeros.
Reduced MIQP has 496 binaries, 0 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 52 nonzeros.
Presolve time =    0.00 sec.
Probing time =    0.00 sec.
Clique table members: 654.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Tried aggregator 1 time.
No QP presolve or aggregator reductions.
Presolve time =    0.00 sec.
Parallel mode: none, using 1 thread for barrier
Number of nonzeros in lower triangle of A*A' = 2360
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.00 sec.
Summary statistics for Cholesky factor:
  Rows in Factor            = 125
  Integer space required    = 241
  Total non-zeros in factor = 3007
  Total FP ops to factor    = 90075
Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf         
   0  1.4172319e+007 -1.4172911e+007 2.45e+003 5.04e+002 2.77e+007
   1  1.2037355e+007  1.0009350e+007 1.78e+002 3.66e+001 2.01e+006
   2  1.1903244e+007  1.1658232e+007 2.15e+001 4.42e+000 2.43e+005
   3  1.1888608e+007  1.1839300e+007 4.33e+000 8.90e-001 4.89e+004
   4  1.1885153e+007  1.1882071e+007 2.71e-001 5.56e-002 3.05e+003
   5  1.1884924e+007  1.1884909e+007 1.33e-003 2.73e-004 1.50e+001
Barrier time =    0.05 sec.

Total time on 1 threads =    0.05 sec.
Root relaxation solution time =    0.05 sec.

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0    infeasible                                          5        

Root node processing (before b&c):
  Real time             =    0.05
Sequential b&c:
  Real time             =    0.00
                          -------
Total (root+branch&cut) =    0.05 sec.
MIQP status(119): integer infeasible or unbounded

Problem is integer infeasible.

**** SOLVER STATUS     1 Normal Completion        
**** MODEL STATUS      10 Integer Infeasible      
**** OBJECTIVE VALUE               NA

OK, but that sounds not really correct. I found a good integer solution with a linearized objective (same constraints). So lets fix the integer variables and see what happens:

* solve MIP
solve gms1 minimizing z using mip;
* fix integer variables

x.fx(i,t) = x.l(i,t);
* and feed it into MIQP solver
solve gms2 minimizing z using miqcp;

Now I see:

Tried aggregator 1 time.
MIQP Presolve eliminated 178 rows and 601 columns.
All rows and columns eliminated.
Presolve time =    0.00 sec.
MIQP status(101): integer optimal solution
Fixing integer variables, and solving final QP..
Tried aggregator 1 time.
QP Presolve eliminated 178 rows and 601 columns.
All rows and columns eliminated.
Presolve time =    0.00 sec.

Total time on 1 threads =    0.00 sec.
QP status(1): optimal

Proven optimal solution.

MIP Solution:     14817439.000000    (0 iterations, 0 nodes)
Final Solve:      14817439.000000    (0 iterations)

Hmm, so not integer infeasible after all. Some more experiments yielded:

  • Using MIPSTART with the MIP solution allowed the MIQP solver to proceed
  • Scaling the objective cause the MIQP to proceed also. The scaling looks like:
    objective2.. z =e= sum(t,sqr(reserves(t)))/1e6;

Don’t always trust the messages from the solvers…