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…

3 comments:

  1. Your comment about scaling makes me wonder whether the model has numerical challenges. Do you get similar behavior from other solvers?

    ReplyDelete
  2. Other solvers including Gurobi seem fine. The model is not that big, and except for the somewhat large objective values of order 1e7 I don't see much that scares me.

    ReplyDelete
  3. In SAT we do fuzz-testing. A. Biere and R. Brummayer did this first, and it's a great way to find bugs. dl.acm.org/citation.cfm?id=2164081 I wonder if these solvers were tested with such tools? They are not easy to write (for proper testing -- i.e. generating meaningful and hard, but not too hard problems), but I have found that it's well worth the effort.

    ReplyDelete