Why the primal and dual simplex process is so long?
AnsweredHi,
Are there any errors in my MILP model? Why the primal and dual simplex process is so long?
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 237631 rows, 80249 columns and 704176 nonzeros
Model fingerprint: 0xf25a92e6
Variable types: 59650 continuous, 20599 integer (20599 binary)
Coefficient statistics:
Matrix range [8e-03, 1e+03]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [3e-01, 4e+03]
Presolve removed 65465 rows and 21904 columns (presolve time = 5s) ...
Presolve removed 69863 rows and 22598 columns
Presolve time: 7.57s
Presolved: 167768 rows, 57651 columns, 552504 nonzeros
Variable types: 40769 continuous, 16882 integer (16872 binary)
Deterministic concurrent LP optimizer: primal and dual simplex (primal and dual model)
Showing first log only...
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 1.5835398e+05 7.858324e+05 8.557586e+10 10s
69772 1.7765987e+05 6.209551e+04 1.939003e+10 15s
83573 1.8264821e+05 4.489968e+04 1.391591e+10 20s
91964 1.8376322e+05 3.649676e+04 1.224387e+10 25s
98767 1.8423574e+05 3.082040e+04 1.314723e+10 30s
101730 1.8413240e+05 2.850518e+04 1.095721e+10 35s
104651 1.8398127e+05 2.649255e+04 1.243670e+10 40s
108015 1.8406991e+05 2.448995e+04 1.028574e+10 45s
110017 1.8439475e+05 2.334205e+04 2.012878e+10 51s
111814 1.8436416e+05 2.221591e+04 9.035619e+09 56s
114078 1.8454821e+05 2.070535e+04 9.002919e+09 60s
116990 1.8470399e+05 1.898181e+04 9.887864e+09 65s
119208 1.8493650e+05 1.785280e+04 8.276973e+09 71s
120979 1.8524552e+05 1.722959e+04 9.731032e+09 75s
122531 1.8557781e+05 1.666174e+04 7.808426e+09 80s
124076 1.8557394e+05 1.602598e+04 8.225182e+09 86s
126077 1.8553324e+05 1.523612e+04 7.827085e+09 91s
127627 1.8560587e+05 1.442821e+04 2.333896e+10 96s
129169 1.8557480e+05 1.371521e+04 8.966419e+09 101s
130496 1.8559259e+05 1.332402e+04 1.126647e+10 106s
131603 1.8575897e+05 1.255995e+04 7.689996e+10 110s
132927 1.8579288e+05 1.183813e+04 7.744583e+09 116s
134031 1.8580096e+05 1.139663e+04 2.262951e+10 120s
135369 1.8584919e+05 1.059988e+04 1.187270e+10 126s
136484 1.8605660e+05 1.019838e+04 8.520134e+09 131s
137365 1.8609508e+05 1.004228e+04 7.785611e+09 136s
138249 1.8625943e+05 9.896621e+03 6.974723e+09 141s
139135 1.8622938e+05 9.652879e+03 1.042053e+10 145s
140237 1.8612938e+05 9.325961e+03 1.852941e+10 151s
141343 1.8661184e+05 9.039795e+03 6.571374e+09 156s
142225 1.8680323e+05 8.826590e+03 1.645956e+10 160s
143554 1.8685118e+05 8.211666e+03 2.783079e+10 166s
144676 1.8702824e+05 7.841552e+03 8.040096e+09 170s
145999 1.8720689e+05 7.544978e+03 5.345381e+09 175s
147102 1.8734222e+05 7.357345e+03 1.274289e+10 180s
148216 1.8742240e+05 7.173884e+03 9.108161e+09 185s
149541 1.8756461e+05 6.856894e+03 5.904931e+09 191s
150422 1.8748379e+05 6.818844e+03 4.961328e+09 195s
151304 1.8731973e+05 6.663208e+03 4.991932e+09 200s
152637 1.8720190e+05 6.341967e+03 7.061325e+09 205s
153965 1.8721014e+05 6.005740e+03 7.750839e+09 210s
155289 1.8692780e+05 5.705981e+03 4.910716e+09 216s
156173 1.8663958e+05 5.542779e+03 7.290290e+09 221s
157275 1.8653067e+05 5.402089e+03 5.074602e+09 226s
158160 1.8648726e+05 5.244749e+03 8.169584e+09 231s
159264 1.8649697e+05 4.995952e+03 5.213389e+09 235s
160367 1.8645642e+05 4.904448e+03 9.592675e+09 241s
161252 1.8636993e+05 4.699836e+03 3.739634e+09 246s
162133 1.8637078e+05 4.632101e+03 5.940627e+09 251s
163015 1.8638908e+05 4.526834e+03 9.578555e+09 256s
164119 1.8596037e+05 4.312896e+03 3.345277e+09 261s
165000 1.8594909e+05 4.274703e+03 3.588981e+09 266s
165886 1.8596581e+05 4.189501e+03 3.627120e+09 271s
166768 1.8595675e+05 4.146085e+03 2.224373e+10 276s
167653 1.8595002e+05 4.013027e+03 3.226375e+09 280s
168757 1.8593705e+05 3.898801e+03 6.443860e+09 286s
169641 1.8586828e+05 3.780861e+03 5.179915e+09 291s
170304 1.8589935e+05 3.724583e+03 1.647260e+10 296s
171186 1.8590785e+05 3.661149e+03 4.067675e+09 301s
172067 1.8591240e+05 3.616058e+03 2.946748e+09 306s
172728 1.8588899e+05 3.580758e+03 1.517489e+10 310s
173836 1.8593368e+05 3.367625e+03 3.899654e+09 316s
174721 1.8611960e+05 3.288351e+03 4.083259e+09 321s
175603 1.8611987e+05 3.072449e+03 8.871509e+10 325s
176703 1.8615072e+05 2.895320e+03 9.646969e+09 331s
177584 1.8614696e+05 2.830512e+03 3.925572e+09 336s
178466 1.8620723e+05 2.664952e+03 9.047777e+09 341s
179348 1.8621071e+05 2.557788e+03 6.149083e+09 345s
180457 1.8630919e+05 2.437374e+03 3.501993e+09 351s
181339 1.8648103e+05 2.403302e+03 7.775800e+09 356s
182222 1.8659711e+05 2.373412e+03 3.321005e+09 360s
183331 1.8653859e+05 2.300856e+03 4.053791e+09 366s
184213 1.8659848e+05 2.229473e+03 7.143518e+09 370s
185315 1.8663655e+05 2.134862e+03 2.133740e+10 376s
186197 1.8666406e+05 2.109100e+03 3.764982e+09 380s
187298 1.8662552e+05 2.056274e+03 4.311399e+09 386s
188179 1.8662394e+05 2.011638e+03 3.379005e+10 390s
189059 1.8663064e+05 1.957823e+03 5.790050e+09 395s
190162 1.8666765e+05 1.897156e+03 5.561120e+09 401s
191046 1.8669781e+05 1.861243e+03 6.916100e+09 405s
192150 1.8668094e+05 1.724464e+03 7.561999e+10 411s
193032 1.8669693e+05 1.681760e+03 5.802093e+09 415s
194138 1.8664319e+05 1.631453e+03 5.791430e+09 421s
195020 1.8666083e+05 1.597511e+03 5.093323e+09 425s
196121 1.8664788e+05 1.520253e+03 5.853222e+10 431s
197002 1.8667740e+05 1.488521e+03 3.932338e+09 436s
197889 1.8668226e+05 1.394265e+03 1.438993e+10 440s
198990 1.8671187e+05 1.324270e+03 5.545416e+10 446s
200090 1.8672683e+05 1.255734e+03 1.519824e+10 451s
200971 1.8674893e+05 1.228975e+03 8.459789e+09 455s
202075 1.8667586e+05 1.178603e+03 6.293673e+09 461s
202958 1.8667495e+05 1.134906e+03 1.347318e+10 465s
204060 1.8662529e+05 1.079514e+03 4.890325e+09 471s
204944 1.8659870e+05 1.031551e+03 7.111685e+09 475s
205826 1.8661379e+05 9.980596e+02 2.599603e+10 480s
206934 1.8663150e+05 9.399790e+02 6.435159e+09 486s
207815 1.8659074e+05 9.157861e+02 1.409936e+10 490s
208707 1.8656811e+05 8.476881e+02 9.075462e+09 495s
209812 1.8655598e+05 7.800427e+02 4.185455e+10 501s
210695 1.8653384e+05 7.253918e+02 3.762860e+10 505s
211795 1.8650844e+05 6.724957e+02 1.127997e+10 511s
212678 1.8655717e+05 6.311658e+02 8.953582e+09 515s
213560 1.8655832e+05 5.658602e+02 1.710218e+11 520s
214441 1.8659573e+05 5.218181e+02 1.274771e+10 525s
215545 1.8664258e+05 4.471376e+02 5.181049e+10 531s
216425 1.8666818e+05 4.107299e+02 1.812370e+10 535s
217529 1.8666850e+05 3.616213e+02 4.180570e+10 541s
218633 1.8665606e+05 2.915651e+02 2.709788e+10 546s
219522 1.8665398e+05 2.592241e+02 9.184051e+09 550s
220392 1.8665706e+05 2.348108e+02 5.657733e+09 555s
221274 1.8665517e+05 2.163828e+02 1.791258e+10 560s
222147 1.8666734e+05 1.933671e+02 2.412486e+09 566s
223037 1.8666202e+05 1.596716e+02 1.347814e+10 570s
223910 1.8666494e+05 1.414366e+02 4.453598e+10 575s
224794 1.8666517e+05 1.227328e+02 3.844377e+11 580s
225655 1.8666624e+05 1.008402e+02 2.995921e+10 585s
226757 1.8665754e+05 8.123949e+01 1.151308e+10 591s
227639 1.8661491e+05 7.328418e+01 7.324113e+11 596s
228719 1.8653516e+05 6.358634e+01 6.467372e+10 601s
229560 1.8654644e+05 5.712249e+01 1.155688e+10 606s
230391 1.8650666e+05 4.997813e+01 1.119549e+10 611s
231184 1.8649524e+05 4.549700e+01 1.051105e+10 616s
231624 1.8646002e+05 4.347416e+01 5.719067e+11 620s
232144 1.8644183e+05 4.195990e+01 5.115246e+10 626s
232494 1.8641675e+05 4.088485e+01 3.932155e+10 630s
232864 1.8635849e+05 3.568513e+01 5.800561e+10 635s
233364 1.8625701e+05 3.385523e+01 1.654161e+10 641s
233734 1.8623683e+05 3.275832e+01 2.666245e+10 645s
234244 1.8619651e+05 3.149142e+01 1.990263e+10 651s
234614 1.8613628e+05 3.063576e+01 8.683806e+11 655s
234984 1.8609425e+05 2.978990e+01 4.831139e+11 660s
235494 1.8608073e+05 2.902377e+01 2.926507e+10 666s
235874 1.8607625e+05 2.838668e+01 3.408627e+11 671s
236294 1.8607110e+05 2.713920e+01 3.672722e+10 675s
236674 1.8605995e+05 2.653865e+01 1.492328e+12 680s
237064 1.8606715e+05 2.611670e+01 1.373042e+10 686s
237454 1.8606310e+05 2.555935e+01 1.166007e+11 691s
237834 1.8604854e+05 2.503143e+01 1.269399e+11 696s
238234 1.8603256e+05 2.406037e+01 5.650475e+10 701s
238604 1.8603546e+05 2.363320e+01 4.820783e+10 706s
238974 1.8600541e+05 2.297167e+01 5.135326e+10 711s
239474 1.8596438e+05 2.183257e+01 2.053648e+10 716s
239844 1.8593587e+05 2.145699e+01 2.668936e+10 721s
240214 1.8588354e+05 2.089583e+01 1.716365e+11 726s
240594 1.8586213e+05 1.984121e+01 1.736667e+11 731s
240984 1.8585008e+05 1.901016e+01 1.691413e+11 736s
241364 1.8589562e+05 1.781209e+01 3.969664e+10 740s
241874 1.8584168e+05 1.702389e+01 4.265889e+10 747s
242264 1.8582332e+05 1.625699e+01 1.759175e+11 751s
242634 1.8578929e+05 1.606547e+01 2.036670e+10 756s
242994 1.8580043e+05 1.586751e+01 1.340579e+11 761s
243354 1.8576345e+05 1.515401e+01 2.535509e+10 766s
243744 1.8574522e+05 1.740733e+01 1.851444e+12 772s
244004 1.8571856e+05 1.401303e+01 2.419219e+12 775s
244394 1.8568140e+05 1.307775e+01 5.704508e+11 781s
244794 1.8566865e+05 1.476975e+01 1.106431e+12 786s
245194 1.8566226e+05 1.244979e+01 1.814975e+10 791s
245584 1.8564418e+05 1.199041e+01 9.949517e+10 797s
245954 1.8563551e+05 1.171000e+01 1.823748e+12 802s
Warning: Markowitz tolerance tightened to 0.0625
246214 1.8564201e+05 1.148015e+01 7.299891e+10 805s
246504 1.8564189e+05 1.139556e+01 1.084369e+11 810s
246764 1.8564422e+05 1.107322e+01 2.023808e+11 817s
247024 1.8563946e+05 1.079576e+01 1.482089e+10 822s
247284 1.8560982e+05 1.050139e+01 5.087048e+10 826s
247694 1.8560885e+05 1.018526e+01 3.623216e+11 831s
247954 1.8559650e+05 9.570785e+00 5.662408e+10 836s
248364 1.8557351e+05 8.836481e+00 2.852328e+11 841s
248755 1.8559022e+05 8.535647e+00 8.899886e+10 847s
249015 1.8561727e+05 7.847137e+00 7.040676e+10 851s
249405 1.8560610e+05 7.546617e+00 1.903231e+11 856s
249665 1.8558301e+05 7.496584e+00 3.352072e+09 860s
250055 1.8556708e+05 7.139414e+00 1.597238e+10 866s
250335 1.8555789e+05 6.890722e+00 1.360821e+10 871s
250765 1.8553629e+05 6.436104e+00 2.248658e+09 877s
251045 1.8553856e+05 6.383071e+00 1.440343e+10 881s
251465 1.8557047e+05 5.713765e+00 9.191366e+09 887s
251745 1.8554500e+05 5.590575e+00 3.209212e+09 891s
252165 1.8548986e+05 5.387923e+00 2.704302e+09 897s
252455 1.8547776e+05 5.289538e+00 5.107755e+09 901s
252715 1.8547805e+05 5.070617e+00 2.063836e+10 905s
253125 1.8543623e+05 4.671895e+00 9.796057e+10 913s
253265 1.8543353e+05 4.307509e+00 2.047010e+10 918s
253405 1.8543401e+05 4.155408e+00 9.105084e+10 921s
253815 1.8543247e+05 3.330486e+00 2.235687e+10 928s
253945 1.8543625e+05 3.214457e+00 2.994807e+11 931s
254215 1.8543831e+05 2.917506e+00 1.102451e+12 936s
254475 1.8543994e+05 2.313365e+00 3.712719e+10 942s
254755 1.8541483e+05 2.280610e+00 3.751747e+10 947s
254895 1.8539665e+05 2.242246e+00 1.034877e+10 950s
255305 1.8541791e+05 2.063813e+00 7.495526e+09 958s
255445 1.8540853e+05 2.780463e+00 1.969473e+12 961s
255725 1.8543057e+05 2.038004e+00 2.024434e+11 965s
256155 1.8542811e+05 1.977862e+00 3.272120e+10 972s
256435 1.8541908e+05 1.883360e+00 4.129224e+09 976s
256715 1.8539116e+05 1.851388e+00 1.009122e+10 981s
257015 1.8531397e+05 1.814500e+00 3.630747e+09 987s
257295 1.8530401e+05 1.660973e+00 4.662511e+09 992s
257575 1.8528771e+05 1.615145e+00 5.050369e+09 997s
257865 1.8526325e+05 1.547213e+00 3.383612e+10 1002s
258165 1.8522653e+05 1.466645e+00 5.989212e+09 1008s
258315 1.8522079e+05 1.425855e+00 6.837440e+10 1010s
258735 1.8521073e+05 1.328872e+00 1.459199e+10 1017s
259015 1.8522308e+05 1.251218e+00 1.169284e+10 1021s
259315 1.8522947e+05 1.176397e+00 2.286356e+10 1025s
259605 1.8521538e+05 8.660580e-01 6.714199e+09 1031s
259895 1.8520289e+05 8.549427e-01 1.424079e+09 1037s
260195 1.8519916e+05 8.422071e-01 5.453427e+09 1042s
260505 1.8521535e+05 8.206899e-01 1.477949e+09 1047s
260805 1.8520037e+05 7.956245e-01 5.564157e+09 1053s
261085 1.8519440e+05 7.761469e-01 7.417874e+09 1057s
261355 1.8514302e+05 6.865800e-01 3.175453e+10 1062s
261505 1.8513515e+05 2.752975e+01 3.357888e+13 1067s
261785 1.8510792e+05 4.456093e-01 4.101381e+11 1072s
262055 1.8502281e+05 3.487429e-02 9.097312e+10 1077s
262086 1.8502271e+05 0.000000e+00 1.842786e+07 1078s
262274 1.8490356e+05 0.000000e+00 8.716691e+07 1081s
262604 1.8475613e+05 0.000000e+00 7.174921e+07 1086s
262894 1.8462218e+05 0.000000e+00 3.476769e+07 1091s
263184 1.8449180e+05 0.000000e+00 9.994797e+06 1097s
263444 1.8429695e+05 0.000000e+00 4.386319e+08 1101s
263714 1.8410458e+05 0.000000e+00 1.247043e+08 1106s
264074 1.8387945e+05 0.000000e+00 9.915656e+06 1111s
264344 1.8361279e+05 0.000000e+00 3.256195e+09 1116s
264634 1.8327602e+05 0.000000e+00 1.042808e+08 1120s
264924 1.8293191e+05 0.000000e+00 3.984499e+08 1125s
265224 1.8273691e+05 0.000000e+00 6.906496e+07 1131s
265524 1.8261991e+05 0.000000e+00 9.576359e+07 1136s
265855 1.8231199e+05 0.000000e+00 2.154374e+07 1142s
266175 1.8212163e+05 0.000000e+00 5.147882e+07 1148s
266305 1.8190732e+05 0.000000e+00 9.543525e+07 1151s
266605 1.8156296e+05 0.000000e+00 3.027931e+08 1156s
266915 1.8145905e+05 0.000000e+00 8.146914e+06 1162s
267215 1.8124344e+05 0.000000e+00 1.031673e+08 1167s
267375 1.8122247e+05 0.000000e+00 1.622602e+07 1170s
267695 1.8096746e+05 0.000000e+00 3.680660e+07 1177s
267865 1.8082669e+05 0.000000e+00 3.457553e+07 1181s
268205 1.8069867e+05 0.000000e+00 4.630135e+07 1186s
268495 1.8035876e+05 0.000000e+00 4.019748e+07 1192s
268645 1.8021939e+05 0.000000e+00 1.072439e+08 1195s
268975 1.7989781e+05 0.000000e+00 2.462202e+07 1201s
269315 1.7971061e+05 0.000000e+00 3.607220e+07 1207s
269475 1.7948968e+05 0.000000e+00 2.443554e+08 1211s
269805 1.7928474e+05 0.000000e+00 4.166538e+07 1216s
270145 1.7891750e+05 0.000000e+00 1.055914e+07 1222s
270315 1.7885453e+05 0.000000e+00 8.648432e+06 1225s
Interrupt request received
Root relaxation: interrupted, 270551 iterations, 1221.39 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 - 0 - 27097.3333 - - 1229s
Explored 0 nodes (270551 simplex iterations) in 1229.74 seconds
Thread count was 8 (of 8 available processors)
Solution count 0
Solve interrupted
Best objective -, best bound 2.709733333333e+04, gap -
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
Hi Yansong,
You might want to try the barrier algorithm (Method=2) to solve the root node LP relaxation. Maybe this is faster than the simplex on this model.
Sometimes, also relatively small models can have an unexpectedly long solving time - even just to solve the LP relaxation.
Cheers,
Matthias0 -
Thank you for this valuable advice. I will have a try.
0 -
Hello, Matthias,
I have a similar problem with my MILP model.
At Root relaxation, the corresponding LP problem is solved fast by the barrier method + crossover. After that Gurobi proceeds with simplex and stuckles for hours, even for Method=2.
With best regards,
Michael0 -
In very rare cases it may even help to also use barrier for the local node relaxations. There is of course the very big downside that barrier cannot benefit from the warm start information that you have when solving node LPs, such that every single LP solve needs to start again from scratch. But sometimes, simplex struggles so much that even this severe limitation of barrier can be accepted. To use barrier also for local nodes, you can set NodeMethod=2. But as I said, this is only useful in very exceptional cases.
Regards,
Tobias
1
Post is closed for comments.
Comments
5 comments