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
- Matlab Optimization Toolbox Release Notes. https://www.mathworks.com/help/optim/release-notes.html
No comments:
Post a Comment