Early termination of Barrier solver
175 views
Skip to first unread message
bahadır zeren
Aug 19, 2015, 9:10:42 AM8/19/15
to Gurobi Optimization
Hi,
I am trying to solve a very large LP problem using barrier method.
If I run it with crossover, it takes too much time (more than 8 hours).
If I run it without crossover, generated solutions will not be basic.
Is it possible to get solution just after push phases are completed ? Because the last simplex (cleanup) phase takes the majority of the time.
Thanks!
Renan Garcia
Aug 19, 2015, 5:14:02 PM8/19/15
to gur...@googlegroups.com
Unfortunately, it's not possible to get solutions in the middle of crossover. You can try tuning some of the barrier-related parameters at http://www.gurobi.com/documentation/6.0/refman/parameters.html like BarConvTol, Crossover and CrossoverBasis. What does the initial 'Coefficient statistics' log show?
--
---
You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
bahadır zeren
Aug 20, 2015, 8:37:27 AM8/20/15
to Gurobi Optimization
Hello Renan,
Thank you!
The log of an earlier barrier run is like below.
I tried to use different Crossover and CrossoverBasis parameters.. I will try to use BarConvTol as well.
Do you have any other suggestion ?
Objective ResidualIter Primal Dual Primal Dual Compl Time 0 1.35079265e+10 -4.34638631e+11 8.31e+05 1.51e+03 8.05e+06 172s
Objective ResidualIter Primal Dual Primal Dual Compl Time 0 1.79981012e+10 -4.51184323e+11 6.95e+05 5.93e+03 6.38e+06 221s 1 1.19292136e+10 -1.59807655e+11 4.85e+05 4.08e+04 3.83e+06 251s 1 1.33193944e+10 -1.09542050e+11 2.51e+05 1.11e+04 2.15e+06 327s 2 6.33898788e+09 -5.12604464e+10 5.18e+04 7.71e+02 5.21e+05 333s 3 3.38684115e+09 -3.17484250e+10 2.38e+04 3.90e+02 2.59e+05 416s 2 4.08912746e+09 -4.95829686e+10 3.96e+04 1.75e+03 3.85e+05 428s 4 9.82306260e+08 -2.09845311e+10 2.56e+03 1.54e-08 9.61e+04 498s 3 2.39848416e+09 -3.84292417e+10 1.75e+04 1.24e+03 1.99e+05 531s 5 6.48827791e+08 -4.58045659e+09 6.78e+01 2.15e-09 2.05e+04 580s 4 1.03661658e+09 -1.67047730e+10 1.58e+03 5.39e+01 4.18e+04 640s 6 4.28268108e+08 -9.36421456e+08 3.61e-01 3.64e-10 5.32e+03 662s 7 1.13035144e+08 -3.44265038e+08 2.11e-02 7.55e-11 1.78e+03 750s 5 6.65635176e+08 -1.53436381e+09 6.69e+01 8.15e-10 4.30e+03 749s 8 2.84443253e+07 -1.71408890e+08 1.47e-03 1.02e-10 7.77e+02 836s 6 1.76896289e+08 -4.82692320e+08 1.42e+00 9.31e-10 1.18e+03 855s 9 2.47088729e+07 -3.58130808e+07 1.19e-04 4.06e-10 2.35e+02 923s 7 4.05147496e+07 -1.95130461e+08 3.28e-01 1.40e-09 4.25e+02 964s 10 1.84671106e+07 -2.76227834e+07 6.61e-05 2.86e-10 1.79e+02 1011s 8 3.89781756e+07 -3.48206008e+07 8.84e-03 2.79e-09 1.31e+02 1075s 11 4.25185665e+06 -1.12582006e+07 1.67e-05 5.75e-11 6.03e+01 1097s 12 1.77641605e+06 -7.20004892e+06 1.07e-05 3.43e-11 3.49e+01 1184s 9 7.66735880e+06 -1.52489170e+07 5.98e-04 2.24e-08 4.07e+01 1188s 13 1.05345464e+06 -2.29253876e+06 2.74e-06 5.66e-12 1.30e+01 1268s 10 2.55761739e+06 -9.34625469e+06 2.99e-04 2.24e-08 2.11e+01 1294s 14 7.43203875e+05 4.38719897e+05 3.49e-10 1.59e-12 1.18e+00 1353s 11 1.55554253e+06 -1.25499932e+06 2.86e-07 2.24e-08 4.96e+00 1411s 15 6.23231191e+05 4.92754461e+05 8.51e-10 1.40e-11 5.07e-01 1442s 12 6.18817450e+05 3.46816659e+05 5.85e-10 2.24e-08 4.80e-01 1519s 16 5.98485154e+05 5.14133849e+05 2.64e-10 2.61e-12 3.28e-01 1532s 17 5.78388653e+05 5.33827929e+05 3.62e-10 4.52e-13 1.73e-01 1621s 13 6.14101088e+05 4.07220465e+05 8.91e-10 1.77e-08 3.65e-01 1621s 18 5.66941822e+05 5.43202378e+05 1.03e-10 2.93e-11 9.23e-02 1705s 14 6.04171672e+05 4.69773217e+05 6.22e-10 1.21e-08 2.37e-01 1735s 19 5.62988490e+05 5.46495430e+05 2.91e-10 8.77e-12 6.41e-02 1786s 15 5.96563850e+05 4.79724709e+05 4.16e-10 1.02e-08 2.06e-01 1843s 20 5.57223258e+05 5.52470041e+05 1.32e-10 6.61e-12 1.85e-02 1878s 16 5.80318344e+05 4.94398620e+05 4.12e-10 7.92e-09 1.52e-01 1954s 21 5.55489701e+05 5.53970634e+05 1.43e-10 6.62e-13 5.91e-03 1965s 22 5.54792190e+05 5.54435985e+05 2.38e-10 7.27e-11 1.38e-03 2054s 17 5.70853248e+05 5.21128169e+05 5.54e-10 4.66e-09 8.78e-02 2059s 23 5.54592271e+05 5.54545316e+05 3.58e-10 1.53e-11 1.83e-04 2144s 18 5.65379300e+05 5.36703500e+05 3.48e-10 2.79e-09 5.06e-02 2164s 24 5.54578962e+05 5.54570960e+05 1.28e-10 3.83e-11 3.11e-05 2233s 19 5.61024589e+05 5.44350819e+05 6.67e-11 1.63e-09 2.94e-02 2269s 25 5.54576642e+05 5.54575634e+05 4.66e-10 5.52e-11 3.92e-06 2320s 20 5.58773079e+05 5.48714842e+05 9.52e-11 8.15e-10 1.78e-02 2376s 26 5.54576321e+05 5.54576100e+05 2.32e-09 4.66e-11 8.56e-07 2406s 21 5.56892667e+05 5.51583631e+05 1.04e-10 4.07e-10 9.37e-03 2484s 27 5.54576297e+05 5.54576205e+05 7.08e-10 1.88e-11 3.56e-07 2488s 28 5.54576278e+05 5.54576260e+05 8.87e-09 4.10e-12 6.98e-08 2577s 22 5.55339938e+05 5.53804292e+05 1.61e-10 1.67e-10 2.71e-03 2602s 29 5.54576276e+05 5.54576274e+05 4.51e-09 5.87e-11 9.39e-09 2663s
Barrier solved model in 29 iterations and 2663.38 secondsOptimal objective 5.54576276e+05
Building initial crossover basis 2680s Building initial crossover basis 2685s Building initial crossover basis 2690s Building initial crossover basis 2697s 23 5.54878104e+05 5.54241700e+05 1.03e-10 6.55e-11 1.12e-03 2697s Building initial crossover basis 2701s Building initial crossover basis 2705s Building initial crossover basis 2710s Building initial crossover basis 2717s Building initial crossover basis 2722s Building initial crossover basis 2727s Building initial crossover basis 2731s Building initial crossover basis 2737s Building initial crossover basis 2742s Building initial crossover basis 2747s Building initial crossover basis 2752s Building initial crossover basis 2756s Building initial crossover basis 2760s Building initial crossover basis 2765s Building initial crossover basis 2770s Building initial crossover basis 2779s Building initial crossover basis 2786s Building initial crossover basis 2791s Building initial crossover basis 2796s Building initial crossover basis 2801s Building initial crossover basis 2806s Building initial crossover basis 2810s 24 5.54575361e+05 5.54535977e+05 5.28e-10 2.34e-11 6.95e-05 2810s Building initial crossover basis 2817s Building initial crossover basis 2821s Building initial crossover basis 2825s Building initial crossover basis 2830sCrossover log...
89303 variables added to crossover basis 2835s
1173 PPushes remaining with PInf 2.7239779e+00 2837s 935 PPushes remaining with PInf 1.5184221e+00 2845s 704 PPushes remaining with PInf 1.2303223e+00 2852s 491 PPushes remaining with PInf 9.6683763e-01 2857s 275 PPushes remaining with PInf 6.0832954e-01 2863s 45 PPushes remaining with PInf 3.6903659e-01 2869s 0 PPushes remaining with PInf 2.9549879e-01 2871s
13539 DPushes remaining with DInf 6.4115413e+02 2871s 25 5.54561269e+05 5.54551658e+05 4.68e-10 4.49e-11 1.70e-05 2881s 26 5.54557084e+05 5.54554260e+05 1.40e-09 1.15e-11 4.98e-06 2937s 3852 DPushes remaining with DInf 5.4533449e+06 2967s 1541 DPushes remaining with DInf 2.8209818e+06 2992s 840 DPushes remaining with DInf 1.2379807e+07 2999s 27 5.54555671e+05 5.54555250e+05 4.78e-09 1.35e-11 7.43e-07 3002s 466 DPushes remaining with DInf 6.7347238e+06 3005s 363 DPushes remaining with DInf 7.0575665e+06 3007s 181 DPushes remaining with DInf 1.3112484e+06 3012s 9 DPushes remaining with DInf 1.0921187e+06 3018s 0 DPushes remaining with DInf 1.0920987e+06 3020s
Push phase complete: Pinf 2.9549879e-01, Dinf 1.0920987e+06 3020s
Iteration Objective Primal Inf. Dual Inf. Time 14710 5.5455785e+05 0.000000e+00 1.105611e+06 3022s 14891 5.5455785e+05 1.349168e-04 8.384931e+11 3034s 15092 5.5455785e+05 6.224528e-06 3.526524e+10 3048s 15298 5.5455785e+05 0.000000e+00 3.956383e+06 3059s 15519 5.5455785e+05 0.000000e+00 1.513115e+06 3069s 28 5.54555504e+05 5.54555420e+05 8.50e-09 1.46e-11 1.48e-07 3069s 15746 5.5455785e+05 0.000000e+00 6.072977e+06 3079s 15966 5.5455785e+05 0.000000e+00 2.819724e+06 3093s 16201 5.5455785e+05 0.000000e+00 2.089435e+06 3108s 16424 5.5455785e+05 0.000000e+00 3.518403e+06 3123s 16640 5.5455785e+05 0.000000e+00 1.932018e+07 3137s 29 5.54555483e+05 5.54555477e+05 9.67e-09 5.85e-11 9.42e-09 3137s
Barrier solved model in 29 iterations and 3137.22 secondsOptimal objective 5.54555483e+05
16850 5.5455784e+05 0.000000e+00 1.286029e+07 3144s 17063 5.5455784e+05 0.000000e+00 1.559388e+07 3149s 17266 5.5455784e+05 0.000000e+00 1.937514e+07 3153s 17469 5.5455783e+05 0.000000e+00 2.680928e+07 3158s 17668 5.5455783e+05 0.000000e+00 1.363523e+07 3162s 17858 5.5455782e+05 0.000000e+00 1.567542e+07 3167s 18043 5.5455782e+05 0.000000e+00 1.040354e+07 3171s 18224 5.5455781e+05 0.000000e+00 1.956738e+07 3175s 18588 5.5455779e+05 0.000000e+00 3.095692e+07 3183s 18769 5.5455778e+05 0.000000e+00 3.208778e+07 3187s 18950 5.5455777e+05 0.000000e+00 1.941818e+07 3191s 19131 5.5455775e+05 0.000000e+00 1.918116e+07 3195s 19493 5.5455771e+05 0.000000e+00 2.810402e+07 3203s 19674 5.5455768e+05 0.000000e+00 1.856439e+07 3207s 19855 5.5455765e+05 0.000000e+00 4.811763e+07 3211s 20217 5.5455756e+05 0.000000e+00 1.889492e+07 3218s 20398 5.5455751e+05 0.000000e+00 1.539930e+07 3222s 20579 5.5455743e+05 0.000000e+00 9.171214e+07 3226s 20941 5.5455719e+05 0.000000e+00 4.418194e+07 3233s 21122 5.5455708e+05 0.000000e+00 2.105121e+07 3237s 21303 5.5455692e+05 0.000000e+00 2.631381e+08 3241s 21665 5.5455624e+05 0.000000e+00 7.276482e+07 3248s 21846 5.5455587e+05 0.000000e+00 6.260372e+07 3251s 22027 5.5455558e+05 0.000000e+00 2.581057e+07 3255s 22389 5.5455469e+05 0.000000e+00 6.775362e+07 3262s 22570 5.5455441e+05 0.000000e+00 1.451977e+07 3266s 22932 5.5455385e+05 0.000000e+00 1.682035e+07 3273s 23113 5.5455350e+05 0.000000e+00 1.512303e+07 3276s 23475 5.5455282e+05 0.000000e+00 9.440870e+06 3283s 23656 5.5455250e+05 0.000000e+00 1.139945e+07 3287s 23837 5.5455187e+05 0.000000e+00 3.072557e+07 3290s 24199 5.5455080e+05 0.000000e+00 6.880656e+07 3297s 24380 5.5455034e+05 0.000000e+00 6.046367e+07 3301s 24742 5.5454909e+05 0.000000e+00 6.500860e+07 3308s 24923 5.5454856e+05 0.000000e+00 1.311327e+07 3311s 25285 5.5454771e+05 0.000000e+00 1.214198e+07 3318s 25466 5.5454741e+05 0.000000e+00 1.437075e+07 3321s 25828 5.5454663e+05 0.000000e+00 3.136785e+07 3328s 26009 5.5454620e+05 0.000000e+00 3.201086e+07 3332s 26190 5.5454563e+05 0.000000e+00 4.237835e+06 3335s20 Ağustos 2015 Perşembe 00:14:02 UTC+3 tarihinde Renan Garcia yazdı:
Renan Garcia
Aug 20, 2015, 9:45:27 AM8/20/15
to gur...@googlegroups.com
What you've posted is the interleaved logs from 2 different solves, which indicates you're likely running these algorithms simultaneously on the same machine. Note that the barrier method is parallelizable and will use all of the available cores on your machine by default. As a result, each solve should run twice as slow. Moreover, since your models are very large you should verify you have enough RAM. Otherwise, you might be using virtual memory which is much slower.
For more guidance on tuning LPs, see http://www.gurobi.com/documentation/6.0/refman/continuous_models.html.
bahadır zeren
Aug 22, 2015, 8:41:27 AM8/22/15
to Gurobi Optimization
Exactly!
There are two simultaneous runs. Each of them uses half of the cores because I set number of Thread parameters before optimization.
One of them is solved without crossover to get dual information. The second one is solved with crossover to get primal information. But second one is much slower.
The crossover logs in the previous message are completely belong to this slower one.
There is no memory problem because %36 of the total memory is in use.
But I will try your other recommendations especially setting that BarConvTol parameter.
If there is any other suggestions please let me know.
Thank you very much!
20 Ağustos 2015 Perşembe 16:45:27 UTC+3 tarihinde Renan Garcia yazdı:
Reply all
Reply to author
Forward
0 new messages