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