MIP is faster than LP relaxation of the same problem
209 views
Skip to first unread message
Evren Guney
Jun 20, 2017, 6:13:27 AM6/20/17
to Gurobi Optimization
I've a mid-size problem which is normally a binary integer program (BIP). Most of the time Gurobi solves it at the root node and finds the integer solution pretty fast.
I also tried the full LP version (by defining the variables as GRB.Continous with 0<=x <=1 lower and upper bounds.
Again 95% of the time the LP solution is integral and very rarely I get fractional values. (I use c# by the way)
In all cases BIP version solves much much faster than the LP version. The model construction, the constaints construction...etc are exactly the same. Just in the first lines where I define the variables one says GRB.BINARY, the other one says GRB.continous.
The issue is this:
I want to develop an LP-relaxation based heuristic (may be some rounding scheme) so I need to be able to solve the LP relaxation as fast as possible.
Now if BIP version's root solution is a much faster option, should I be preferring it instead of using the LP version?
Or how can I speed up the LP version?
Also, can I get dual values for the root node solution of BIP version?
Best regards,
Asst.Prof.Dr. Evren Guney
Tobias Achterberg
Jun 20, 2017, 6:30:29 AM6/20/17
to gur...@googlegroups.com
My guess is that with binary variables presolve is able to reduce the problem
significantly, while it is not possible that much if you declare the variables
to be continuous. Please check the log output to find the presolving statistics.
If you want to implement a rounding heuristic, you can just install a callback
that queries the LP relaxation solution at the current node, then does whatever
you want to do to round it, and then provide the rounded integer solution back
to Gurobi.
Regards,
Tobias
significantly, while it is not possible that much if you declare the variables
to be continuous. Please check the log output to find the presolving statistics.
If you want to implement a rounding heuristic, you can just install a callback
that queries the LP relaxation solution at the current node, then does whatever
you want to do to round it, and then provide the rounded integer solution back
to Gurobi.
Regards,
Tobias
Evren Guney
Jun 20, 2017, 9:28:48 AM6/20/17
to Gurobi Optimization
Hi again,
*************** BIP***********************
20 Haziran 2017 Salı 13:30:29 UTC+3 tarihinde Tobias Achterberg yazdı:
The logs are inline with your comment...
So if that many columns and rows are removable, may be I can also simplify my model at the very first step. I remember there was a presentation about the methods used in Presolve
and also I've found a paper by you :)
https://opus4.kobv.de/opus4-zib/files/6037/Presolve.pdf
Do you recommend any other sources for this issue?
https://opus4.kobv.de/opus4-zib/files/6037/Presolve.pdf
Do you recommend any other sources for this issue?
*************** BIP***********************
Gurobi 7.0.2 (win64, .NET) logging started 06/19/17 00:39:29
Optimize a model with 1213501 rows, 1225635 columns and 6542569 nonzeros
Variable types: 1213500 continuous, 12135 integer (12135 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [7e+00, 7e+00]
Found heuristic solution: objective 1100
Presolve removed 1019994 rows and 1020000 columns (presolve time = 5s) ...
Presolve removed 1025546 rows and 1025552 columns (presolve time = 10s) ...
Presolve removed 1025546 rows and 1025602 columns (presolve time = 15s) ...
Presolve removed 1025546 rows and 1025602 columns
Presolve time: 18.48s
Presolved: 187955 rows, 200033 columns, 3207676 nonzeros
Variable types: 187954 continuous, 12079 integer (12076 binary)
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 4.9951600e+05 1.879540e+05 0.000000e+00 20s
15472 4.3223000e+05 1.704480e+05 0.000000e+00 20s
75326 1.8983700e+05 1.009900e+05 0.000000e+00 25s
120245 1.0360900e+05 6.528500e+04 0.000000e+00 30s
141729 7.6626000e+04 3.908100e+04 0.000000e+00 35s
151969 6.7543000e+04 4.134200e+04 0.000000e+00 40s
161212 6.1271000e+04 1.971000e+04 0.000000e+00 45s
169981 5.5776000e+04 1.505200e+04 0.000000e+00 50s
178276 5.1429000e+04 8.285000e+03 0.000000e+00 55s
185623 4.8716000e+04 8.786000e+03 0.000000e+00 60s
191289 4.7583000e+04 0.000000e+00 0.000000e+00 63s
Root relaxation: objective 4.758300e+04, 191289 iterations, 44.15 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
* 0 0 0 47583.000000 47583.0000 0.00% - 64s
Explored 0 nodes (191289 simplex iterations) in 64.33 seconds
Thread count was 8 (of 8 available processors)
Solution count 2: 47583 1100
Pool objective bound 47583
Optimal solution found (tolerance 1.00e-04)
Best objective 4.758300000000e+04, best bound 4.758300000000e+04, gap 0.0000%
*************** LP RELAX ***********************
Gurobi 7.0.2 (win64, .NET) logging started 06/19/17 00:40:54
Optimize a model with 1213501 rows, 1225635 columns and 6542569 nonzeros
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [7e+00, 7e+00]
Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...
Presolve removed 714684 rows and 714740 columns (presolve time = 5s) ...
Presolve removed 714684 rows and 714740 columns
Presolve time: 5.56s
Presolved: 498817 rows, 510895 columns, 5079739 nonzeros
Elapsed ordering time = 5s
Elapsed ordering time = 10s
Ordering time: 12.50s
Barrier statistics:
Dense cols : 2198
AA' NZ : 4.287e+07
Factor NZ : 5.315e+07 (roughly 800 MBytes of memory)
Factor Ops : 1.395e+10 (less than 1 second per iteration)
Threads : 3
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 2.38037001e+07 1.78083157e+07 2.36e+05 1.39e+01 6.83e+02 31s
1 2.05161397e+07 1.71703066e+07 2.04e+05 1.59e+01 5.47e+02 32s
2 1.30386780e+07 1.66086918e+07 1.27e+05 7.24e+00 3.33e+02 34s
3 9.46917567e+06 1.60777995e+07 9.13e+04 3.35e+00 2.31e+02 36s
4 6.77534460e+06 1.55917224e+07 6.46e+04 1.72e+00 1.62e+02 37s
5 4.88234016e+06 1.49358868e+07 4.60e+04 9.63e-01 1.15e+02 39s
6 3.70631731e+06 1.39278922e+07 3.45e+04 5.05e-01 8.48e+01 41s
7 2.75959535e+06 1.28050389e+07 2.52e+04 3.07e-01 6.13e+01 42s
8 1.98296837e+06 1.17244607e+07 1.76e+04 1.91e-01 4.29e+01 44s
9 1.41130038e+06 9.59020200e+06 1.20e+04 8.38e-02 2.85e+01 45s
10 8.66126422e+05 7.48497802e+06 6.73e+03 3.44e-02 1.63e+01 47s
11 6.71848429e+05 5.57378293e+06 4.92e+03 1.04e-02 1.13e+01 48s
12 4.81670425e+05 3.98026568e+06 3.18e+03 6.10e-10 7.26e+00 50s
13 4.18932530e+05 3.18738001e+06 2.64e+03 4.31e-10 5.82e+00 52s
14 3.28580992e+05 2.42403564e+06 1.89e+03 2.96e-10 4.20e+00 53s
15 2.88334550e+05 1.73505633e+06 1.57e+03 1.70e-10 3.25e+00 55s
16 1.91621249e+05 1.25674542e+06 8.23e+02 1.13e-10 1.91e+00 57s
17 1.38201463e+05 8.09598559e+05 4.58e+02 1.06e-10 1.13e+00 58s
18 1.14381357e+05 5.21289172e+05 3.23e+02 1.73e-10 7.78e-01 59s
19 8.18166938e+04 1.75247237e+05 1.52e+02 1.57e-10 3.18e-01 61s
20 6.75652499e+04 7.52496864e+04 7.63e+01 1.34e-10 1.37e-01 63s
21 6.32457283e+04 6.66318554e+04 5.55e+01 1.08e-10 9.94e-02 64s
22 6.05776967e+04 6.32836905e+04 4.40e+01 8.50e-11 7.94e-02 66s
23 5.88236081e+04 5.86739538e+04 3.67e+01 1.20e-10 6.54e-02 67s
24 5.68447245e+04 5.36391426e+04 2.63e+01 6.58e-11 4.59e-02 69s
25 5.58484444e+04 5.28222644e+04 2.26e+01 1.06e-10 3.94e-02 71s
26 5.43662066e+04 5.22893273e+04 1.78e+01 6.25e-11 3.14e-02 72s
27 5.30684727e+04 5.15476564e+04 1.32e+01 1.80e-10 2.35e-02 73s
28 5.14794342e+04 4.81960980e+04 5.65e+00 9.14e-11 9.05e-03 75s
29 4.82498010e+04 4.76944799e+04 1.81e+00 1.76e-10 3.38e-03 77s
30 4.76078702e+04 4.75999954e+04 1.14e-01 1.79e-10 2.32e-04 79s
31 4.75830013e+04 4.75830170e+04 6.72e-06 1.97e-10 2.43e-08 80s
32 4.75830000e+04 4.75830000e+04 1.54e-11 1.82e-10 5.69e-14 82s
Barrier solved model in 32 iterations and 81.84 seconds
Optimal objective 4.75830000e+04
Crossover log...
45246 DPushes remaining with DInf 0.0000000e+00 85s
34807 DPushes remaining with DInf 0.0000000e+00 90s
23709 DPushes remaining with DInf 0.0000000e+00 95s
12648 DPushes remaining with DInf 0.0000000e+00 100s
894 DPushes remaining with DInf 0.0000000e+00 105s
0 DPushes remaining with DInf 0.0000000e+00 106s
0 PPushes remaining with PInf 0.0000000e+00 106s
Push phase complete: Pinf 0.0000000e+00, Dinf 0.0000000e+00 106s
Iteration Objective Primal Inf. Dual Inf. Time
494331 4.7583000e+04 0.000000e+00 0.000000e+00 106s
494331 4.7583000e+04 0.000000e+00 0.000000e+00 108s
Solved with barrier
Solved in 494331 iterations and 107.77 seconds
Optimal objective 4.758300000e+04
20 Haziran 2017 Salı 13:30:29 UTC+3 tarihinde Tobias Achterberg yazdı:
Tobias Achterberg
Jun 20, 2017, 11:18:26 AM6/20/17
to gur...@googlegroups.com
Most of the simple presolve reductions (like removing fixed variables or
redundant rows) are also available in LP presolve, because these do not depend
on integrality of the variables. The fact that MIP presolve is so much stronger
on your model than LP presolve means that there is more complicated stuff going
on (like probing). I doubt that you want to implement all this. This is not so
easy to do.
The presolve paper that you mention lists all presolve reductions that are
available in Gurobi 6. Many of them are explained in detail (with pseudo code)
in my thesis. But as I said: I doubt you want to implement them manually.
The best way to implement a rounding heuristic is to use the callback, as I said
in my previous answer.
Hope this helps,
Tobias
redundant rows) are also available in LP presolve, because these do not depend
on integrality of the variables. The fact that MIP presolve is so much stronger
on your model than LP presolve means that there is more complicated stuff going
on (like probing). I doubt that you want to implement all this. This is not so
easy to do.
The presolve paper that you mention lists all presolve reductions that are
available in Gurobi 6. Many of them are explained in detail (with pseudo code)
in my thesis. But as I said: I doubt you want to implement them manually.
The best way to implement a rounding heuristic is to use the callback, as I said
in my previous answer.
Hope this helps,
Tobias
Evren Guney
Jun 20, 2017, 1:24:32 PM6/20/17
to Gurobi Optimization
Got your point, thanks for the recommendations.
Evren
20 Haziran 2017 Salı 18:18:26 UTC+3 tarihinde Tobias Achterberg yazdı:
20 Haziran 2017 Salı 18:18:26 UTC+3 tarihinde Tobias Achterberg yazdı:
Reply all
Reply to author
Forward
0 new messages