The best objective bound doesn't change and it takes too long to get an optimal solution

Hi everyone, i'm trying to solve a MILP problem, but the best objective bound doesn't change (and is the upper limit of the variable, that is 250) in a lot of time and also it takes too long to find a feasible solution, even more in finding an optimal solution, and i think is not a big problem (there are few variables and constraints compared other posts). Is there any recommendation that you could give me?

Thanks for your response.

Academic license - for non-commercial use only - expires 2021-02-05
Read LP format model from file ./problem.lp
Reading time = 0.88 seconds
OBJ: 86268 rows, 43596 columns, 421171 nonzeros
Changed value of parameter Presolve to 2
Prev: -1 Min: -1 Max: 2 Default: -1
Changed value of parameter MIPGap to 0.05
Prev: 0.0001 Min: 0.0 Max: inf Default: 0.0001
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Optimize a model with 86268 rows, 43596 columns and 421171 nonzeros
Model fingerprint: 0x668c8460
Variable types: 32723 continuous, 10873 integer (10825 binary)
Coefficient statistics:
Matrix range [1e-04, 5e+03]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 3e+02]
RHS range [5e-01, 1e+02]
Presolve removed 12807 rows and 14327 columns (presolve time = 11s) ...
Presolve removed 12807 rows and 16362 columns (presolve time = 18s) ...
Presolve removed 28858 rows and 17299 columns (presolve time = 24s) ...
Presolve removed 28858 rows and 17321 columns (presolve time = 29s) ...
Presolve removed 31071 rows and 17365 columns (presolve time = 34s) ...
Presolve removed 31071 rows and 17365 columns (presolve time = 39s) ...
Presolve removed 31071 rows and 17365 columns (presolve time = 44s) ...
Presolve removed 30996 rows and 17290 columns
Presolve time: 44.10s
Presolved: 55272 rows, 26306 columns, 236573 nonzeros
Variable types: 18822 continuous, 7484 integer (7454 binary)

Deterministic concurrent LP optimizer: primal and dual simplex (primal and dual model)
Showing first log only...

Presolve removed 8822 rows and 4408 columns
Presolved: 46450 rows, 21898 columns, 218910 nonzeros


Root simplex log...

Iteration Objective Primal Inf. Dual Inf. Time
0 7.0435295e+02 4.502305e+02 2.923712e+10 45s
29199 0.0000000e+00 4.764191e+01 7.215860e+09 50s
36555 0.0000000e+00 1.616805e+01 1.513443e+10 55s
41475 -2.5000000e+02 4.966314e+00 4.937544e+10 60s
43705 -2.5000000e+02 2.352993e+00 9.306284e+10 65s
45835 -2.5000000e+02 4.683854e-01 4.021249e+10 70s
47775 -2.5000000e+02 5.397259e-02 1.470991e+11 75s
49190 -2.5000000e+02 3.492057e+02 0.000000e+00 80s
50640 -2.5000000e+02 0.000000e+00 0.000000e+00 85s
50640 -2.5000000e+02 0.000000e+00 0.000000e+00 85s
Concurrent spin time: 13.45s

Solved with dual simplex (dual model)

Root relaxation: objective -2.500000e+02, 39667 iterations, 53.69 seconds
Total elapsed time = 112.43s
Total elapsed time = 146.57s
Total elapsed time = 152.79s

Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

0 0 -250.00000 0 1102 - -250.00000 - - 167s
0 0 -250.00000 0 1271 - -250.00000 - - 199s
0 0 -250.00000 0 1427 - -250.00000 - - 223s
0 0 -250.00000 0 142 - -250.00000 - - 363s
0 0 -250.00000 0 403 - -250.00000 - - 372s
0 0 -250.00000 0 148 - -250.00000 - - 399s
0 0 -250.00000 0 308 - -250.00000 - - 408s
0 0 -250.00000 0 120 - -250.00000 - - 439s
0 0 -250.00000 0 175 - -250.00000 - - 445s
0 0 -250.00000 0 111 - -250.00000 - - 495s
0 0 -250.00000 0 111 - -250.00000 - - 500s
0 2 -250.00000 0 111 - -250.00000 - - 536s
1 4 -250.00000 1 227 - -250.00000 - 10330 546s
3 8 -250.00000 2 424 - -250.00000 - 7904 554s
7 16 -250.00000 3 883 - -250.00000 - 6684 570s
15 24 -250.00000 4 843 - -250.00000 - 6556 588s
23 32 -250.00000 5 825 - -250.00000 - 7210 590s
47 58 -250.00000 8 589 - -250.00000 - 4259 625s
61 82 -250.00000 8 567 - -250.00000 - 3876 647s
89 264 -250.00000 11 84 - -250.00000 - 4663 672s
305 579 -250.00000 32 146 - -250.00000 - 2472 705s
827 981 -250.00000 30 51 - -250.00000 - 1722 750s
1560 1190 -250.00000 52 144 - -250.00000 - 1318 779s
2003 1191 -250.00000 12 111 - -250.00000 - 1251 937s
2005 1192 -250.00000 57 772 - -250.00000 - 1249 1074s
2006 1193 -250.00000 20 996 - -250.00000 - 1249 1114s
2007 1194 -250.00000 42 1309 - -250.00000 - 1248 1136s
2008 1194 -250.00000 55 1196 - -250.00000 - 1247 1213s
2009 1195 -196.62156 65 1321 - -250.00000 - 1247 1232s
2010 1196 -250.00000 39 1132 - -250.00000 - 1246 1395s
2011 1196 -250.00000 37 1499 - -250.00000 - 1246 1423s
2012 1197 -250.00000 36 842 - -250.00000 - 1245 1555s
2013 1198 -250.00000 41 1315 - -250.00000 - 1244 1578s
2014 1198 -231.78180 78 1486 - -250.00000 - 1244 1716s
2015 1199 -250.00000 31 1186 - -250.00000 - 1243 1810s
2016 1200 -250.00000 56 1186 - -250.00000 - 1242 1871s
2017 1203 -250.00000 13 1197 - -250.00000 - 283 2008s
2019 1207 -250.00000 14 1361 - -250.00000 - 299 2088s
2023 1211 -250.00000 15 950 - -250.00000 - 339 2153s
2031 1215 -250.00000 16 766 - -250.00000 - 374 2220s
2039 1216 -250.00000 17 729 - -250.00000 - 401 2283s
2047 1219 -250.00000 17 716 - -250.00000 - 425 2315s
2055 1223 infeasible 18 - -250.00000 - 470 2347s
2063 1235 -250.00000 18 725 - -250.00000 - 498 2402s
2078 1239 -250.00000 19 1505 - -250.00000 - 537 2459s
2087 1240 -250.00000 19 1805 - -250.00000 - 593 2499s
2098 1243 infeasible 20 - -250.00000 - 624 2569s
2111 1254 infeasible 20 - -250.00000 - 681 2730s
2136 1267 -250.00000 20 706 - -250.00000 - 806 2914s
2173 1402 -250.00000 21 653 - -250.00000 - 942 3156s
2414 1366 infeasible 41 - -250.00000 - 1271 3375s
2674 1561 -250.00000 40 459 - -250.00000 - 1474 3802s
3641 1518 -183.02700 31 1076 - -250.00000 - 1742 4153s
4549 1295 -250.00000 43 884 - -250.00000 - 1830 4373s
4795 1523 -250.00000 48 806 - -250.00000 - 1953 4713s
5681 1257 infeasible 51 - -250.00000 - 1999 4886s
5739 1441 infeasible 35 - -250.00000 - 2059 5224s
6444 1615 -250.00000 35 1085 - -250.00000 - 2132 5560s
7029 1614 infeasible 29 - -250.00000 - 2214 5732s
7118 1855 -97.95833 41 874 - -250.00000 - 2269 6087s
7897 2015 -250.00000 37 934 - -250.00000 - 2299 6469s
8396 2030 -153.82015 31 1443 - -250.00000 - 2361 6723s

正式なコメント

Simranjit Kaur

Gurobi Staff

2025年06月23日 03:03 編集済み

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?.

Jaromił Najman

2020年12月11日 10:40 編集済み

Hi Erick,

The size of a problem is not always a good indicator of its complexity. There are problems with only a couple of variables in the MIPLIB which are still unsolved or the solution process requires a lot of computation time.

Did you have a look at the documentation of most important parameters for MIPs? I would try the new no relaxation heuristic first to possibly get a good feasible point before the B&B algorithm starts.

You could also try to provide an initial point or at least some variable hints if you have any. The Knowledge Base article How do I use MIP starts? documents both.

Did you try different formulations of the model? Maybe, you can find some in the literature.

Best regards,
Jaromił

Erick Sanhueza

2021年05月21日 02:46

Thanks a lot Jaromił for your response!

The best objective bound doesn't change and it takes too long to get an optimal solution

コメント

お探しのものを見つけられませんでしたか？