Friday, April 13, 2018

MATLAB: LP more expensive than MIP?

A strange report:

The model has variables that assume automatically 0-1 values. When we throw the model into intlinprog it solves much faster than when solving as an LP (using linprog).


Solve as LP
-----------

Optimization terminated.

obj =

  -1.4864e+03

Elapsed time is 102.261043 seconds.


Solve as MIP
------------


LP:                Optimal objective value is -1486.439509.                                         


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value,
options.TolGapAbs = 0 (the default value). The intcon variables are integer within tolerance,
options.TolInteger = 1e-05 (the default value).


obj =

  -1.4864e+03

Elapsed time is 3.679962 seconds.

I am not using Matlab extensively (mainly for translating prototype algorithms into "real" code -- sometimes suffering from what can be called "write-only" Matlab code).

So I was thinking: the MIP solver starts with an LP (solving the root). So how can this happen? An exotic reason can be: when using binary variables instead of continuous variables, additional reductions can be applied in the presolve. This sounds somewhat far-fetched however.

Luckily the reason was much more straightforward. In older versions of  linprog, the default LP solver is an interior point code which is much slower. Adding more logging showed:


Solve as LP: interior point
---------------------------

  Residuals:   Primal     Dual     Upper    Duality     Total
               Infeas    Infeas    Bounds     Gap        Rel
               A*x-b   A'*y+z-w-f {x}+s-ub  x'*z+s'*w   Error
  -------------------------------------------------------------
  Iter    0:  1.58e+06 1.07e+05 9.97e+04 1.61e+10 5.01e+04
  Iter    1:  8.61e+03 3.80e-11 5.42e+02 1.42e+08 2.72e+02
  Iter    2:  2.53e+00 1.39e-10 1.59e-01 2.07e+07 1.00e+00
  Iter    3:  2.32e+00 1.40e-10 1.46e-01 2.07e+07 1.00e+00
  Iter    4:  5.58e-14 1.79e-11 3.63e-14 2.18e+05 1.00e+00
  Iter    5:  5.75e-14 6.53e-12 4.10e-14 1.06e+05 1.00e+00
  Iter    6:  5.31e-14 1.82e-12 3.02e-14 7.26e+03 9.96e-01
  Iter    7:  5.41e-14 1.12e-12 2.88e-14 4.87e+03 9.73e-01
  Iter    8:  5.79e-14 5.98e-13 2.92e-14 2.84e+03 9.04e-01
  Iter    9:  4.47e-14 3.66e-13 3.00e-14 1.86e+03 8.04e-01
  Iter   10:  4.37e-14 2.89e-13 3.44e-14 1.63e+03 7.31e-01
  Iter   11:  3.90e-14 1.84e-13 3.58e-14 1.21e+03 6.23e-01
  Iter   12:  3.74e-14 1.66e-13 3.27e-14 8.01e+02 4.62e-01
  Iter   13:  4.10e-14 1.58e-13 2.95e-14 3.65e+02 2.28e-01
  Iter   14:  4.53e-14 1.47e-13 2.82e-14 1.14e+02 7.43e-02
  Iter   15:  4.45e-14 1.42e-13 2.74e-14 4.82e+01 3.19e-02
  Iter   16:  3.82e-14 1.39e-13 2.74e-14 2.66e+01 1.78e-02
  Iter   17:  2.16e-13 1.48e-13 2.79e-14 9.02e+00 6.05e-03
  Iter   18:  7.02e-14 1.66e-13 2.86e-14 8.61e-01 5.79e-04
  Iter   19:  2.31e-14 1.75e-13 2.93e-14 1.21e-03 8.13e-07
  Iter   20:  2.27e-14 1.70e-13 2.98e-14 1.23e-09 9.17e-13
Optimization terminated.

obj =

  -1.4864e+03

Elapsed time is 104.291608 seconds.


Solve as LP: dual simplex
-------------------------


LP preprocessing removed 251000 inequalities, 0 equalities,                                         
0 variables, and 251000 non-zero elements in 3.87 secs.                                             

    Iter      Time           Fval  Primal Infeas    Dual Infeas                                     
       0      4.07  -1.002605e+05   7.916327e+03   0.000000e+00                                     
     105      4.13  -7.847379e+04   6.550848e+03   0.000000e+00                                     
     210      4.18  -5.757528e+04   5.213011e+03   0.000000e+00                                     
     315      4.22  -3.717179e+04   3.843284e+03   0.000000e+00                                     
     420      4.26  -1.733225e+04   2.330379e+03   0.000000e+00                                     
     525      4.30  -1.699942e+03   2.700000e+01   0.000000e+00                                     
     630      4.32  -1.665130e+03   2.360085e+01   0.000000e+00                                     
     735      4.37  -1.648131e+03   2.567100e+01   0.000000e+00                                     
     840      4.42  -1.630944e+03   2.863564e+01   0.000000e+00                                     
     945      4.49  -1.615813e+03   3.931921e+01   0.000000e+00                                     
    1050      4.57  -1.598377e+03   5.398148e+01   0.000000e+00                                     
    1155      4.68  -1.580648e+03   1.585970e+02   0.000000e+00                                     
    1260      4.76  -1.513779e+03   4.815600e+01   0.000000e+00                                     
    1365      4.81  -1.502488e+03   4.176123e+01   0.000000e+00                                     
    1470      4.88  -1.496429e+03   3.964846e+01   0.000000e+00                                     
    1575      4.97  -1.493434e+03   2.932576e+01   0.000000e+00                                     
    1680      5.06  -1.489125e+03   1.624808e+01   0.000000e+00                                     
    1785      5.19  -1.486733e+03   2.319483e+01   0.000000e+00                                     
    1831      5.40  -1.486440e+03   0.000000e+00   0.000000e+00                                     

Optimal solution found.


obj =

  -1.4864e+03

Elapsed time is 6.533843 seconds.

Sometimes good old Simplex is not so bad. Or. may be. it is actually the presolve that makes a difference (I don't see in the log of  the interior point LP any mention of doing a presolve).

Note: newer versions of Matlab have different behavior (the default LP solver is now dual Simplex).

References



  1. Matlab Optimization Toolbox Release Notes. https://www.mathworks.com/help/optim/release-notes.html