MIP stuck in branch-and-cut in some situations
Answered
Hello everyone,
I am solving a series of similar MIP problems in size, #constraints, and other statistics. While some can be solved successfully, others may be stuck in branch-and-cut. It is quite strange and I am curious about why. I'll be grateful for any suggestions about the parameters and settings.
Logs of a successful case and a failed case are listed in the following. For the failed case, the logger stopped output after 325s but indeed, the optimal is not obtained. No more logs are printed between 325s and time-limit. We have tried setting MIPfocus to 1,2,3 in the failed case, but the result seems similar. As I need to reuse the program for time, solving time for each subproblem is limited and thus I set the parameter Timelimit to a smaller one.
Thanks
start optimization
Set parameter Crossover to value 0
Set parameter Method to value 2
Set parameter NodeMethod to value 2
Set parameter MIPFocus to value 2
Set parameter NonConvex to value 2
Set parameter DisplayInterval to value 10
Set parameter MIPGap to value 0.05
Set parameter PreSOS1Encoding to value 3
Gurobi Optimizer version 11.0.2 build v11.0.2rc0 (linux64 - "Ubuntu 22.04.4 LTS")
CPU model: AMD Ryzen Threadripper 2990WX 32-Core Processor, instruction set [SSE2|AVX|AVX2]
Thread count: 32 physical cores, 64 logical processors, using up to 32 threads
Optimize a model with 555812 rows, 542247 columns and 1156717 nonzeros
Model fingerprint: 0x8be6a43b
Model has 440287 quadratic constraints
Model has 998 general constraints
Variable types: 111111 continuous, 431136 integer (431136 binary)
Coefficient statistics:
Matrix range [2e-01, 1e+00]
QLMatrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+01]
RHS range [2e-03, 2e+03]
Presolve added 476879 rows and 373439 columns
Presolve time: 1.41s
Presolved: 1089650 rows, 931622 columns, 2433876 nonzeros
Variable types: 121349 continuous, 810273 integer (810033 binary)
Root relaxation presolve removed 47812 rows and 0 columns
Root relaxation presolve time: 11.18s
Root relaxation presolved: 121108 rows, 138915 columns, 598335 nonzeros
Root barrier log...
Ordering time: 2.93s
Barrier statistics:
AA' NZ : 3.622e+06
Factor NZ : 1.404e+07 (roughly 200 MB of memory)
Factor Ops : 3.552e+09 (less than 1 second per iteration)
Threads : 31
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 1.62829123e+05 -5.83251944e+06 1.09e+04 0.00e+00 2.78e+02 15s
1 7.38670935e+04 -4.75833456e+06 3.50e+03 6.13e-14 9.04e+01 15s
2 4.40887457e+04 -3.53233027e+06 7.80e+02 6.57e-14 2.46e+01 15s
3 4.03845193e+04 -1.61173375e+06 1.13e+02 6.13e-14 6.21e+00 15s
4 2.99249346e+04 -3.79840990e+05 2.56e+01 5.68e-14 1.36e+00 16s
5 2.60152946e+04 -1.47161948e+05 1.28e+01 2.84e-14 5.61e-01 16s
6 2.51523066e+04 -8.71893678e+04 7.44e+00 2.13e-14 3.58e-01 16s
7 2.48247965e+04 -4.69601555e+04 4.83e+00 1.62e-14 2.27e-01 16s
8 2.46325890e+04 -1.33896072e+04 3.06e+00 1.45e-14 1.20e-01 16s
9 2.45748988e+04 -4.06965375e+03 2.55e+00 2.03e-14 9.05e-02 16s
10 2.44698590e+04 9.62983641e+03 1.39e+00 4.64e-14 4.67e-02 16s
11 2.44033424e+04 1.79469524e+04 2.95e-01 2.99e-14 2.01e-02 17s
12 2.43964895e+04 2.21756301e+04 4.92e-02 8.53e-14 6.86e-03 17s
13 2.43939442e+04 2.32228116e+04 9.17e-03 8.53e-14 3.61e-03 17s
14 2.43925430e+04 2.43579920e+04 4.09e-04 9.24e-14 1.07e-04 17s
15 2.43921137e+04 2.43920594e+04 3.38e-07 3.55e-14 1.67e-07 17s
16 2.43921131e+04 2.43921131e+04 3.83e-08 2.75e-14 1.67e-10 17s
Barrier solved model in 16 iterations and 17.37 seconds (15.18 work units)
Optimal objective 2.43921131e+04
Root relaxation: objective 2.439211e+04, 0 iterations, 6.88 seconds (5.42 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 24392.1131 0 7207 - 24392.1131 - - 19s
0 0 24621.0141 0 7194 - 24621.0141 - - 31s
0 0 24621.0141 0 7194 - 24621.0141 - - 42s
H 0 0 515983.71253 24621.0141 95.2% - 44s
0 0 24647.3537 0 7198 515983.713 24647.3537 95.2% - 54s
H 0 0 250684.25086 24647.3537 90.2% - 56s
0 0 24647.3537 0 7198 250684.251 24647.3537 90.2% - 66s
0 0 24647.3537 0 7198 250684.251 24647.3537 90.2% - 73s
0 0 24647.4037 0 7198 250684.251 24647.4037 90.2% - 85s
0 0 24647.4037 0 7198 250684.251 24647.4037 90.2% - 93s
0 0 24647.4037 0 7198 250684.251 24647.4037 90.2% - 103s
0 0 24647.4037 0 7198 250684.251 24647.4037 90.2% - 111s
0 0 24708.4535 0 7197 250684.251 24708.4535 90.1% - 120s
0 0 24745.9410 0 7200 250684.251 24745.9410 90.1% - 134s
H 0 0 169486.71286 24745.9410 85.4% - 136s
0 0 24745.9410 0 7200 169486.713 24745.9410 85.4% - 144s
0 0 24745.9410 0 7200 169486.713 24745.9410 85.4% - 152s
0 0 24745.9410 0 7200 169486.713 24745.9410 85.4% - 153s
0 2 24745.9410 0 7200 169486.713 24745.9410 85.4% - 183s
1 4 24772.3170 1 7200 169486.713 24745.9410 85.4% 0.0 201s
3 8 24772.6077 2 7200 169486.713 24772.3170 85.4% 0.0 220s
7 16 24791.8357 3 7198 169486.713 24772.6077 85.4% 0.0 244s
15 32 24799.9682 4 7196 169486.713 24791.8357 85.4% 0.0 273s
H 31 64 136322.17166 24799.9682 81.8% 0.0 325s
H 33 64 123059.49567 24799.9682 79.8% 0.0 325s
H 47 64 114344.29144 24799.9682 78.3% 0.0 325s
start optimization
Set parameter TimeLimit to value 1500
Set parameter Crossover to value 0
Set parameter Method to value 2
Set parameter NodeMethod to value 2
Set parameter MIPFocus to value 1
Set parameter NonConvex to value 2
Set parameter MIPGap to value 0.05
Gurobi Optimizer version 11.0.2 build v11.0.2rc0 (linux64 - "Ubuntu 18.04.6 LTS")
CPU model: AMD Ryzen Threadripper 2990WX 32-Core Processor, instruction set [SSE2|AVX|AVX2]
Thread count: 32 physical cores, 64 logical processors, using up to 32 threads
Academic license - for non-commercial use only - registered to
Optimize a model with 556943 rows, 543305 columns and 1160270 nonzeros
Model fingerprint: 0x797a9d3f
Model has 440509 quadratic constraints
Model has 1000 general constraints
Variable types: 111305 continuous, 432000 integer (432000 binary)
Coefficient statistics:
Matrix range [2e-01, 1e+00]
QMatrix range [1e+00, 1e+00]
QLMatrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+01]
RHS range [3e-04, 8e+03]
Presolve added 479058 rows and 373392 columns
Presolve time: 1.54s
Presolved: 1095078 rows, 933553 columns, 2432046 nonzeros
Variable types: 121718 continuous, 811835 integer (811564 binary)
Root relaxation presolve removed 47928 rows and 0 columns
Root relaxation presolve time: 11.24s
Root relaxation presolved: 122153 rows, 136755 columns, 581374 nonzeros
Root barrier log...
Barrier statistics:
AA' NZ : 3.628e+06
Factor NZ : 1.216e+07 (roughly 200 MB of memory)
Factor Ops : 3.123e+09 (less than 1 second per iteration)
Threads : 31
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -6.75210436e+05 -5.39625154e+06 1.87e+04 7.26e-01 4.62e+02 13s
1 -9.68026199e+03 -4.99678099e+06 5.82e+03 3.83e-01 1.48e+02 13s
2 2.48370144e+05 -3.84724714e+06 5.63e+02 7.42e-14 2.34e+01 13s
3 2.50360230e+05 -1.38070703e+06 1.23e+02 8.44e-14 6.23e+00 14s
4 2.28654548e+05 -5.76581285e+05 5.99e+01 4.62e-14 2.84e+00 14s
5 2.16168648e+05 -1.29678209e+05 3.90e+01 3.20e-14 1.20e+00 14s
6 2.04799505e+05 5.05622171e+04 2.17e+01 2.18e-14 5.20e-01 14s
7 2.04053980e+05 1.30701213e+05 1.28e+01 8.88e-14 2.44e-01 14s
8 2.03025880e+05 1.80802488e+05 6.48e+00 9.59e-14 7.43e-02 15s
9 2.02691322e+05 1.92452759e+05 4.32e+00 4.27e-14 3.49e-02 15s
10 2.02571979e+05 2.00284587e+05 1.65e+00 6.04e-14 8.16e-03 15s
11 2.02498138e+05 2.02313610e+05 2.84e-02 7.46e-14 5.86e-04 15s
12 2.02495424e+05 2.02495206e+05 6.25e-06 8.17e-14 6.76e-07 16s
13 2.02495417e+05 2.02495417e+05 1.23e-07 4.65e-14 7.83e-13 16s
Barrier solved model in 13 iterations and 15.87 seconds (8.31 work units)
Optimal objective 2.02495417e+05
Root relaxation: objective 2.024954e+05, 0 iterations, 4.93 seconds (2.65 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 202495.417 0 8167 - 202495.417 - - 17s
H 0 0 673418.30691 202495.417 69.9% - 20s
0 0 202595.229 0 8154 673418.307 202595.229 69.9% - 26s
0 0 202595.229 0 8154 673418.307 202595.229 69.9% - 34s
0 0 202595.229 0 8154 673418.307 202595.229 69.9% - 41s
0 0 202609.267 0 8160 673418.307 202609.267 69.9% - 49s
H 0 0 545439.54947 202609.267 62.9% - 49s
0 0 202641.381 0 8159 545439.549 202641.381 62.8% - 58s
0 0 202651.374 0 8156 545439.549 202651.374 62.8% - 65s
0 0 202651.374 0 8156 545439.549 202651.374 62.8% - 72s
0 0 202651.374 0 8156 545439.549 202651.374 62.8% - 74s
H 0 0 204000.03119 202651.374 0.66% - 221s
Cutting planes:
MIR: 16
Flow cover: 60
RLT: 90
Explored 1 nodes (0 simplex iterations) in 222.01 seconds (138.46 work units)
Thread count was 32 (of 64 available processors)
Solution count 3: 204000 545440 673418
Optimal solution found (tolerance 5.00e-02)
Best objective 2.040000311921e+05, best bound 2.026513738764e+05, gap 0.6611%
0
-
Hi Sibo,
I think it would be worth looking at the performance variance for a single model first. I.e. for the last model, run it 30 times, each with a different value of Seed, and make sure the logs are written to file.
You can then "grep" the resulting log(s) for "Explored" to get a quick idea of the seconds used in each solve, or alternatively use gurobi-logtools to read the logfiles and create pandas dataframes rich in information.
- Riley
0 -
Thanks a lot, Riley,
I have been trying multiple times for one instance of our model, it seems that whether the problem can be solved is not random, but depends on the specific input of different cases.
For the logs, they are saved correctly to a file, but in branch-and-cut, it seems that nothing is output both in the file and the command lines. The final few lines of the log are appended:
Besides, I find that the failed cases have relatively small bounds or optimal values (observed by partial solution in logs). So will that make a difference?
Sibo Li15 32 24799.9682 4 7196 169486.713 24791.8357 85.4% 0.0 274s
H 31 64 136322.17166 24799.9682 81.8% 0.0 369s
H 33 64 123059.49567 24799.9682 79.8% 0.0 369s
H 47 64 114344.29144 24799.9682 78.3% 0.0 369s
^C
Interrupt request received
63 96 24826.9363 6 7193 114344.291 24812.8423 78.3% 0.0 1144s
Cutting planes:
Implied bound: 68
Projected implied bound: 19
MIR: 210
Flow cover: 790
RLT: 69
Relax-and-lift: 12
BQP: 56
PSD: 1
Explored 95 nodes (0 simplex iterations) in 1144.80 seconds (488.46 work units)
Thread count was 32 (of 64 available processors)
Solution count 6: 114344 123059 136322 ... 5159840 -
Hi Sibo,
The choice of Crossover=0 and NodeMethod=2 is an interesting one. Do the simplex algorithms fail terribly on this model?
- Riley
0 -
Hi Riley,
Thanks for reminding me that, actually Crossover=0 is set as I copied the parameters from another problem, where crossover takes too much time. I have tried enabling crossover and that helps to give a better dual bound and get a better solution.
However, the solution does not converge yet. Will there be some other parameters that helps generate a better solution?
Thanks a lot!Sibo Li
The log is attached here.CPU model: AMD Ryzen Threadripper 2990WX 32-Core Processor, instruction set [SSE2|AVX|AVX2]
Thread count: 32 physical cores, 64 logical processors, using up to 32 threads
Academic license 2426991 - for non-commercial use only - registered to li___@mails.tsinghua.edu.cn
Optimize a model with 555812 rows, 542247 columns and 1156717 nonzeros
Model fingerprint: 0xf9591bf0
Model has 440287 quadratic constraints
Model has 998 general constraints
Variable types: 111111 continuous, 431136 integer (431136 binary)
Coefficient statistics:
Matrix range [2e-01, 1e+00]
QMatrix range [1e+00, 1e+00]
QLMatrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+01]
RHS range [2e-03, 2e+03]
Presolve added 476879 rows and 373439 columns
Presolve time: 1.38s
Presolved: 1089650 rows, 931622 columns, 2433876 nonzeros
Variable types: 121349 continuous, 810273 integer (810033 binary)
Root relaxation presolve removed 47815 rows and 0 columns
Root relaxation presolved: 121182 rows, 138989 columns, 599392 nonzeros
Root barrier log...
Ordering time: 2.93s
Barrier statistics:
AA' NZ : 3.626e+06
Factor NZ : 1.403e+07 (roughly 200 MB of memory)
Factor Ops : 3.538e+09 (less than 1 second per iteration)
Threads : 31
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 1.62407985e+05 -5.80517257e+06 1.11e+04 0.00e+00 2.80e+02 14s
1 7.14118574e+04 -4.73912752e+06 3.38e+03 5.51e-14 8.77e+01 14s
2 4.24933082e+04 -3.49829370e+06 6.33e+02 7.64e-14 2.19e+01 14s
3 4.32761778e+04 -1.48320769e+06 1.16e+02 7.86e-14 5.80e+00 15s
4 3.51255401e+04 -2.74699646e+05 2.72e+01 5.68e-14 1.05e+00 15s
5 3.16413139e+04 -1.21619624e+05 1.36e+01 2.66e-14 5.02e-01 15s
6 3.10504039e+04 -8.43870662e+04 9.29e+00 1.95e-14 3.73e-01 15s
7 3.07055239e+04 -5.56081901e+04 6.00e+00 1.60e-14 2.75e-01 15s
8 3.06017574e+04 -4.30059186e+03 4.34e+00 1.98e-14 1.12e-01 15s
9 3.03428283e+04 6.94274367e+03 2.32e+00 2.35e-14 7.42e-02 15s
10 3.02552179e+04 2.19024667e+04 1.51e+00 1.78e-14 2.68e-02 16s
11 3.01884377e+04 2.49192606e+04 8.52e-01 2.23e-14 1.68e-02 16s
12 3.01674918e+04 2.67793641e+04 7.23e-01 1.96e-14 1.09e-02 16s
13 3.01565325e+04 2.77763405e+04 6.02e-01 2.62e-14 7.72e-03 16s
14 3.01359694e+04 2.87463465e+04 3.83e-01 1.75e-14 4.53e-03 16s
15 3.01196445e+04 2.91945054e+04 1.49e-01 1.52e-14 2.94e-03 16s
16 3.01122517e+04 2.93435812e+04 8.03e-02 1.60e-14 2.41e-03 17s
17 3.01104657e+04 2.94340663e+04 5.39e-02 1.94e-14 2.11e-03 17s
18 3.01092692e+04 2.97699403e+04 4.10e-02 2.82e-14 1.07e-03 17s
19 3.01075776e+04 2.98387513e+04 2.71e-02 3.84e-14 8.44e-04 17s
20 3.01074455e+04 2.99386768e+04 2.28e-02 3.59e-14 5.33e-04 17s
21 3.01069566e+04 3.00945433e+04 1.14e-02 2.41e-14 4.52e-05 17s
22 3.01064806e+04 3.01060608e+04 8.91e-05 2.87e-14 1.34e-06 17s
23 3.01064676e+04 3.01064672e+04 2.58e-06 2.50e-14 1.35e-09 18s
24 3.01064676e+04 3.01064676e+04 2.53e-07 5.26e-14 1.03e-14 18s
Barrier solved model in 24 iterations and 17.74 seconds (16.25 work units)
Optimal objective 3.01064676e+04
Root crossover log...
4459 DPushes remaining with DInf 0.0000000e+00 18s
0 DPushes remaining with DInf 0.0000000e+00 18s
60843 PPushes remaining with PInf 0.0000000e+00 18s
20943 PPushes remaining with PInf 0.0000000e+00 20s
0 PPushes remaining with PInf 0.0000000e+00 24s
Push phase complete: Pinf 0.0000000e+00, Dinf 3.8344558e-10 24s
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
63998 3.0106468e+04 0.000000e+00 0.000000e+00 24s
63998 3.0106468e+04 0.000000e+00 0.000000e+00 24s
Root relaxation: objective 3.010647e+04, 63998 iterations, 14.76 seconds (14.25 work units)
Total elapsed time = 24.48s (DegenMoves)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 30106.4676 0 3713 - 30106.4676 - - 161s
H 0 0 512890.75441 30106.4676 94.1% - 256s
0 0 30652.0267 0 3055 512890.754 30652.0267 94.0% - 305s
H 0 0 39165.805084 30652.0267 21.7% - 347s
0 0 30673.8973 0 3031 39165.8051 30673.8973 21.7% - 349s
0 0 30673.8986 0 3026 39165.8051 30673.8986 21.7% - 350s
0 0 30941.5909 0 2829 39165.8051 30941.5909 21.0% - 377s
0 0 30986.5760 0 2802 39165.8051 30986.5760 20.9% - 383s
0 0 30987.0836 0 2798 39165.8051 30987.0836 20.9% - 384s
0 0 31156.0703 0 2749 39165.8051 31156.0703 20.5% - 398s
H 0 0 39130.605084 31176.0703 20.3% - 458s
0 0 31176.0703 0 2735 39130.6051 31176.0703 20.3% - 460s
0 0 31309.7660 0 2704 39130.6051 31309.7660 20.0% - 465s
0 0 31316.4326 0 2701 39130.6051 31316.4326 20.0% - 477s
0 0 31448.6798 0 2655 39130.6051 31448.6798 19.6% - 482s
0 0 31468.8187 0 2652 39130.6051 31468.8187 19.6% - 487s
0 0 31468.8643 0 2652 39130.6051 31468.8643 19.6% - 487s
0 0 31523.7499 0 2630 39130.6051 31523.7499 19.4% - 494s
0 0 31533.7499 0 2630 39130.6051 31533.7499 19.4% - 496s
0 0 31548.3720 0 2602 39130.6051 31548.3720 19.4% - 500s
0 0 31550.0243 0 2606 39130.6051 31550.0243 19.4% - 512s
0 0 31550.0243 0 2604 39130.6051 31550.0243 19.4% - 514s
0 0 31559.6898 0 2604 39130.6051 31559.6898 19.3% - 522s
0 0 31559.6898 0 2604 39130.6051 31559.6898 19.3% - 524s
0 0 31559.6898 0 2604 39130.6051 31559.6898 19.3%0 -
Hi Sibo,
It's fairly typical to have trouble closing the gap on a model with nonconvex quadratic constraints. I would certainly start with default parameters and only change values if there is substantial evidence that it improves (this means running the models with competing parameter sets over many values of Seed). You will also want to make sure you are specifying the tightest bounds on variables you can. I'd also run the No Relaxation heuristic for a while (NoRelHeurTime= ) and see how that performs. It may perform well but plateau, or it may not run well at all. You would use the results to gauge what a good value for this parameter could be.
- Riley
0 -
Hi Riley,
I set the model with default parameters, but no improvement is observed. And No Relaxation Heuristic seems not working either.
However, a gap of about 20% is not perfect but acceptable for my question. And further improvement seems to be quite difficult. So I'll stop here, and again, thanks for the suggestions.
Sibo Li0
Please sign in to leave a comment.
Comments
6 comments