gurobi struggles to narrow the gap of MIP
Answered
Hi gurobi support team
I'm now solving a MIP problem with quardratic objectives and linear constraints(along with PWL constraints).The result shows that gurobi quickly narrwo the gap to less than 0.5%,but it seems to struggle with the proving of optimality of the solution:it spends a lot of time to narrow the gap from 0.2% to 0.1%.As you can see the solution is very big,so the small gap still leads to great difference of the optimal solution.I'm wondering is there any way to solve this problem.
Set parameter Username
Set parameter OptimalityTol to value 1e-07
Set parameter CrossoverBasis to value 0
Set parameter MIPFocus to value 3
Set parameter NodefileDir to value ""
Set parameter NoRelHeurTime to value 5
Set parameter NonConvex to value 2
Set parameter PreSOS2BigM to value 0
Set parameter TuneTrials to value 3
Academic license - for non-commercial use only - expires 2024-06-06
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)
CPU model: Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 21457 rows, 6193 columns and 239396 nonzeros
Model fingerprint: 0x7d815e2e
Model has 2050 quadratic objective terms
Coefficient statistics:
Matrix range [3e-04, 4e+02]
Objective range [9e-02, 2e+04]
QObjective range [6e-01, 2e+02]
Bounds range [0e+00, 0e+00]
RHS range [3e-03, 6e+04]
Presolve removed 12964 rows and 518 columns
Continuous model is non-convex -- solving as a MIP
Presolve removed 13247 rows and 311 columns
Presolve time: 0.21s
Presolved: 10549 rows, 7713 columns, 52625 nonzeros
Presolved model has 661 quadratic constraint(s)
Presolved model has 1169 bilinear constraint(s)
Variable types: 7713 continuous, 0 integer (0 binary)
Starting NoRel heuristic
Found phase-1 solution: relaxation 2.38865e+09
Elapsed time for NoRel heuristic: 5s (best bound -2.08198e+07)
Root relaxation presolve removed 807 rows and 661 columns
Root relaxation presolved: 9742 rows, 7348 columns, 46342 nonzeros
Root simplex log...
Iteration Objective Primal Inf. Dual Inf. Time
0 -2.3382792e+07 9.693703e+05 0.000000e+00 5s
3507 -2.0819816e+07 0.000000e+00 0.000000e+00 5s
3507 -2.0819816e+07 0.000000e+00 0.000000e+00 5s
Root relaxation: objective -2.081982e+07, 3507 iterations, 0.15 seconds (0.14 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -2.082e+07 0 252 - -2.082e+07 - - 5s
H 0 0 7.350425e+07 -2.082e+07 128% - 5s
H 0 0 5.360970e+07 -2.082e+07 139% - 8s
H 0 0 1.687757e+07 -2.082e+07 223% - 8s
H 0 0 1.420333e+07 -2.082e+07 247% - 8s
H 0 0 5729798.8836 -2.082e+07 463% - 8s
0 0 -3779300.8 0 100 5729798.88 -3779300.8 166% - 8s
0 0 -3779300.8 0 109 5729798.88 -3779300.8 166% - 8s
0 0 1688469.76 0 122 5729798.88 1688469.76 70.5% - 8s
0 0 2003990.77 0 123 5729798.88 2003990.77 65.0% - 9s
0 0 2711632.43 0 148 5729798.88 2711632.43 52.7% - 9s
H 0 0 3669023.1180 2711632.43 26.1% - 9s
0 0 2725654.72 0 151 3669023.12 2725654.72 25.7% - 9s
0 0 3019158.97 0 158 3669023.12 3019158.97 17.7% - 9s
H 0 0 3499724.8774 3019158.97 13.7% - 9s
0 0 3023954.71 0 166 3499724.88 3023954.71 13.6% - 9s
0 0 3130796.96 0 164 3499724.88 3130796.96 10.5% - 9s
H 0 0 3366526.2507 3130796.96 7.00% - 9s
0 0 3136566.13 0 165 3366526.25 3136566.13 6.83% - 9s
0 0 3166982.90 0 163 3366526.25 3166982.90 5.93% - 9s
H 0 0 3263366.4573 3166982.90 2.95% - 9s
0 0 3167812.46 0 168 3263366.46 3167812.46 2.93% - 9s
0 0 3178170.14 0 166 3263366.46 3178170.14 2.61% - 10s
0 0 3185266.32 0 167 3263366.46 3185266.32 2.39% - 10s
0 0 3188096.20 0 172 3263366.46 3188096.20 2.31% - 10s
0 0 3189512.37 0 172 3263366.46 3189512.37 2.26% - 10s
0 0 3190502.22 0 174 3263366.46 3190502.22 2.23% - 10s
0 0 3191179.83 0 173 3263366.46 3191179.83 2.21% - 10s
0 0 3191802.88 0 172 3263366.46 3191802.88 2.19% - 10s
0 0 3192432.13 0 173 3263366.46 3192432.13 2.17% - 10s
0 0 3192857.69 0 172 3263366.46 3192857.69 2.16% - 10s
0 0 3193210.71 0 173 3263366.46 3193210.71 2.15% - 10s
0 0 3193413.82 0 173 3263366.46 3193413.82 2.14% - 10s
0 0 3193592.25 0 173 3263366.46 3193592.25 2.14% - 10s
0 0 3193791.77 0 173 3263366.46 3193791.77 2.13% - 10s
0 0 3193964.48 0 170 3263366.46 3193964.48 2.13% - 10s
0 0 3194080.41 0 170 3263366.46 3194080.41 2.12% - 10s
0 0 3194163.68 0 169 3263366.46 3194163.68 2.12% - 10s
0 0 3194246.96 0 170 3263366.46 3194246.96 2.12% - 10s
0 0 3194353.10 0 170 3263366.46 3194353.10 2.11% - 10s
0 0 3194471.31 0 173 3263366.46 3194471.31 2.11% - 10s
0 0 3194572.37 0 174 3263366.46 3194572.37 2.11% - 10s
0 0 3194663.89 0 176 3263366.46 3194663.89 2.11% - 10s
0 0 3194725.69 0 176 3263366.46 3194725.69 2.10% - 10s
0 0 3194781.98 0 176 3263366.46 3194781.98 2.10% - 10s
0 0 3194832.11 0 176 3263366.46 3194832.11 2.10% - 10s
0 0 3194884.61 0 177 3263366.46 3194884.61 2.10% - 10s
0 0 3194928.96 0 176 3263366.46 3194928.96 2.10% - 10s
0 0 3194976.07 0 176 3263366.46 3194976.07 2.10% - 10s
0 0 3195018.24 0 176 3263366.46 3195018.24 2.09% - 10s
0 0 3195045.19 0 176 3263366.46 3195045.19 2.09% - 10s
0 0 3195073.88 0 175 3263366.46 3195073.88 2.09% - 10s
0 0 3195102.11 0 175 3263366.46 3195102.11 2.09% - 10s
0 0 3195126.15 0 175 3263366.46 3195126.15 2.09% - 10s
0 0 3195146.31 0 175 3263366.46 3195146.31 2.09% - 10s
0 0 3195165.87 0 175 3263366.46 3195165.87 2.09% - 11s
0 0 3195188.99 0 175 3263366.46 3195188.99 2.09% - 11s
0 0 3195202.93 0 175 3263366.46 3195202.93 2.09% - 11s
0 0 3195215.87 0 175 3263366.46 3195215.87 2.09% - 11s
0 0 3195230.57 0 175 3263366.46 3195230.57 2.09% - 11s
0 0 3195243.05 0 175 3263366.46 3195243.05 2.09% - 11s
0 0 3195260.69 0 176 3263366.46 3195260.69 2.09% - 11s
0 0 3195272.28 0 176 3263366.46 3195272.28 2.09% - 11s
0 0 3195284.38 0 176 3263366.46 3195284.38 2.09% - 11s
0 0 3195296.09 0 176 3263366.46 3195296.09 2.09% - 11s
0 0 3195308.70 0 176 3263366.46 3195308.70 2.09% - 11s
0 0 3195324.17 0 176 3263366.46 3195324.17 2.09% - 11s
0 0 3195334.85 0 176 3263366.46 3195334.85 2.08% - 11s
0 0 3195343.51 0 176 3263366.46 3195343.51 2.08% - 11s
0 0 3195353.35 0 175 3263366.46 3195353.35 2.08% - 11s
0 0 3195364.31 0 175 3263366.46 3195364.31 2.08% - 11s
0 0 3195373.39 0 175 3263366.46 3195373.39 2.08% - 11s
0 0 3195384.25 0 175 3263366.46 3195384.25 2.08% - 11s
0 0 3195395.35 0 175 3263366.46 3195395.35 2.08% - 11s
0 0 3195405.68 0 175 3263366.46 3195405.68 2.08% - 11s
0 0 3195415.29 0 175 3263366.46 3195415.29 2.08% - 11s
0 0 3195425.60 0 175 3263366.46 3195425.60 2.08% - 11s
0 0 3195434.12 0 175 3263366.46 3195434.12 2.08% - 11s
0 0 3195442.40 0 175 3263366.46 3195442.40 2.08% - 11s
0 0 3195449.56 0 175 3263366.46 3195449.56 2.08% - 11s
0 0 3195456.31 0 175 3263366.46 3195456.31 2.08% - 11s
0 0 3195464.82 0 175 3263366.46 3195464.82 2.08% - 11s
0 0 3195471.67 0 175 3263366.46 3195471.67 2.08% - 11s
0 0 3195479.26 0 175 3263366.46 3195479.26 2.08% - 11s
0 0 3195485.66 0 175 3263366.46 3195485.66 2.08% - 11s
0 0 3195490.88 0 175 3263366.46 3195490.88 2.08% - 11s
0 0 3195498.18 0 175 3263366.46 3195498.18 2.08% - 11s
0 0 3195504.19 0 175 3263366.46 3195504.19 2.08% - 11s
0 0 3195509.18 0 175 3263366.46 3195509.18 2.08% - 11s
0 0 3195513.72 0 175 3263366.46 3195513.72 2.08% - 11s
0 0 3195517.46 0 175 3263366.46 3195517.46 2.08% - 11s
0 0 3195522.35 0 175 3263366.46 3195522.35 2.08% - 11s
0 0 3195528.26 0 175 3263366.46 3195528.26 2.08% - 11s
0 0 3195533.50 0 175 3263366.46 3195533.50 2.08% - 11s
0 0 3195538.01 0 175 3263366.46 3195538.01 2.08% - 12s
0 0 3195541.62 0 175 3263366.46 3195541.62 2.08% - 12s
0 0 3195544.87 0 175 3263366.46 3195544.87 2.08% - 12s
0 0 3195550.22 0 175 3263366.46 3195550.22 2.08% - 12s
0 0 3195556.24 0 175 3263366.46 3195556.24 2.08% - 12s
0 0 3195561.00 0 175 3263366.46 3195561.00 2.08% - 12s
0 0 3195565.95 0 175 3263366.46 3195565.95 2.08% - 12s
0 0 3195570.17 0 175 3263366.46 3195570.17 2.08% - 12s
0 0 3195573.67 0 175 3263366.46 3195573.67 2.08% - 12s
0 0 3195578.01 0 175 3263366.46 3195578.01 2.08% - 12s
0 0 3195582.09 0 175 3263366.46 3195582.09 2.08% - 12s
0 0 3195585.64 0 175 3263366.46 3195585.64 2.08% - 12s
0 0 3195588.93 0 175 3263366.46 3195588.93 2.08% - 12s
0 0 3195592.84 0 175 3263366.46 3195592.84 2.08% - 12s
0 0 3195596.14 0 175 3263366.46 3195596.14 2.08% - 12s
0 0 3195599.44 0 175 3263366.46 3195599.44 2.08% - 12s
0 0 3195602.72 0 175 3263366.46 3195602.72 2.08% - 12s
0 0 3195605.94 0 175 3263366.46 3195605.94 2.08% - 12s
0 0 3195610.99 0 175 3263366.46 3195610.99 2.08% - 12s
0 0 3195614.89 0 175 3263366.46 3195614.89 2.08% - 12s
0 0 3195617.88 0 175 3263366.46 3195617.88 2.08% - 12s
0 0 3195621.74 0 171 3263366.46 3195621.74 2.08% - 12s
H 0 0 3208870.7090 3195621.74 0.41% - 12s
H 0 0 3204188.3695 3195621.74 0.27% - 12s
0 2 3195621.74 0 171 3204188.37 3195621.74 0.27% - 14s
27 32 3196238.28 8 185 3204188.37 3196138.01 0.25% 509 59s
31 36 3196319.34 9 185 3204188.37 3196228.18 0.25% 536 60s
H 107 157 3204073.7711 3196319.34 0.24% 270 61s
464 465 3197525.51 19 0 3204073.77 3196444.27 0.24% 133 68s
466 466 3197840.83 29 0 3204073.77 3196444.27 0.24% 132 80s
467 467 3197102.73 18 0 3204073.77 3196444.27 0.24% 132 170s
490 482 3197567.76 20 0 3204073.77 3196881.42 0.22% 126 177s
H 490 457 3201226.2772 3196881.42 0.14% 126 186s
H 490 434 3201080.2919 3196881.42 0.13% 126 191s
549 586 3196881.42 20 224 3201080.29 3196881.42 0.13% 218 195s
844 850 3197023.57 19 225 3201080.29 3196881.42 0.13% 258 201s
1209 1190 3196881.42 20 228 3201080.29 3196881.42 0.13% 276 206s
1753 1595 3196881.42 23 220 3201080.29 3196881.42 0.13% 283 213s
2071 1915 3196881.42 24 223 3201080.29 3196881.42 0.13% 279 216s
2405 2247 3196881.42 23 225 3201080.29 3196881.42 0.13% 272 220s
3080 2915 3196896.96 25 219 3201080.29 3196881.42 0.13% 262 228s
3405 3237 3196933.54 25 218 3201080.29 3196881.42 0.13% 269 233s
3727 3589 3196998.30 25 223 3201080.29 3196881.42 0.13% 274 237s
4079 3906 3196881.42 26 225 3201080.29 3196881.42 0.13% 272 242s
4396 4305 3197032.37 24 225 3201080.29 3196881.42 0.13% 280 247s
4795 4731 3196881.42 23 225 3201080.29 3196881.42 0.13% 278 252s
5221 5167 3196881.42 26 223 3201080.29 3196881.42 0.13% 275 258s
5657 5550 3196890.18 22 222 3201080.29 3196881.42 0.13% 274 263s
6040 5969 3197087.58 22 217 3201080.29 3196881.42 0.13% 279 269s
6459 6435 3196881.42 26 223 3201080.29 3196881.42 0.13% 279 275s
6925 6877 3197079.77 26 221 3201080.29 3196881.42 0.13% 278 281s
7367 7409 3196881.47 25 224 3201080.29 3196881.42 0.13% 281 287s
7899 7915 3196917.05 27 222 3201080.29 3196881.42 0.13% 279 295s
8405 8459 3197120.01 26 221 3201080.29 3196881.42 0.13% 283 301s
8949 9011 3196923.77 22 221 3201080.29 3196881.42 0.13% 281 309s
9501 9594 3196916.37 24 218 3201080.29 3196881.42 0.13% 282 316s
10084 10176 3197206.47 24 219 3201080.29 3196888.59 0.13% 282 324s
10666 10751 3197003.12 28 218 3201080.29 3196896.96 0.13% 283 332s
11241 11365 3197150.41 28 222 3201080.29 3196908.89 0.13% 287 341s
11855 11893 3197000.89 26 221 3201080.29 3196916.86 0.13% 286 349s
11970 11893 3196997.36 24 221 3201080.29 3196916.86 0.13% 286 396s
12383 12499 3197204.39 23 217 3201080.29 3196924.70 0.13% 286 404s
12989 13131 3196994.38 26 219 3201080.29 3196928.21 0.13% 289 412s
13621 13768 3197047.73 29 220 3201080.29 3196935.50 0.13% 289 421s
14258 14413 3197016.91 27 222 3201080.29 3196941.10 0.13% 289 429s
14903 14904 3196965.04 27 221 3201080.29 3196949.88 0.13% 288 438s
14958 14904 3197832.19 32 201 3201080.29 3196949.88 0.13% 288 491s
15394 15558 3197252.75 27 219 3201080.29 3196955.92 0.13% 291 499s
16048 16160 3197034.68 27 218 3201080.29 3196961.09 0.13% 291 508s
16650 16748 3197049.32 26 220 3201080.29 3196966.08 0.13% 294 518s
17238 17410 3197049.56 26 220 3201080.29 3196971.93 0.13% 298 527s
17900 17951 3197052.54 25 218 3201080.29 3196979.46 0.13% 298 535s
18441 18594 3197077.60 31 215 3201080.29 3196987.71 0.13% 298 544s
19084 19211 3197322.90 27 217 3201080.29 3196992.68 0.13% 299 553s
19701 19867 3197283.47 28 217 3201080.29 3196996.22 0.13% 301 562s
20357 20546 3197074.35 26 219 3201080.29 3197001.24 0.13% 302 571s
21036 21127 3197030.00 26 219 3201080.29 3197007.54 0.13% 302 580s
21617 21724 3197105.46 29 221 3201080.29 3197011.52 0.13% 305 588s
22214 22341 3197119.66 23 220 3201080.29 3197016.28 0.13% 308 598s
22831 22861 3197093.21 26 219 3201080.29 3197020.26 0.13% 309 606s
22934 22861 3197782.30 33 197 3201080.29 3197020.26 0.13% 309 672s
23351 23535 3197103.58 27 220 3201080.29 3197024.33 0.13% 309 682s
24025 24194 3197145.59 23 221 3201080.29 3197029.27 0.13% 311 691s
24684 24908 3197057.73 22 223 3201080.29 3197035.25 0.13% 313 701s
25398 25623 3197329.88 25 217 3201080.29 3197039.33 0.13% 312 711s
26113 26264 3197316.57 27 217 3201080.29 3197046.89 0.13% 312 720s
26754 26887 3197122.90 21 225 3201080.29 3197050.83 0.13% 313 730s
27377 27553 3197366.88 28 219 3201080.29 3197056.41 0.13% 315 739s
28043 28142 3197111.20 24 218 3201080.29 3197061.34 0.13% 315 749s
28632 28856 3197139.21 26 221 3201080.29 3197065.79 0.13% 318 759s
29346 29457 3197323.16 21 221 3201080.29 3197069.81 0.13% 318 768s
29947 30136 3197145.39 25 220 3201080.29 3197072.13 0.13% 319 778s
30626 30760 3197318.96 27 218 3201080.29 3197076.33 0.13% 319 788s
31250 31447 3197153.37 26 216 3201080.29 3197078.96 0.12% 319 798s
31937 32038 3197310.00 28 214 3201080.29 3197083.61 0.12% 319 807s
32528 32700 3197111.30 16 224 3201080.29 3197087.48 0.12% 320 817s
33190 33282 3197331.41 28 218 3201080.29 3197090.67 0.12% 320 826s
33772 33800 3197446.33 24 220 3201080.29 3197092.30 0.12% 322 835s
34017 33800 3198057.43 36 187 3201080.29 3197092.81 0.12% 323 896s
34290 34454 3197472.27 29 210 3201080.29 3197095.58 0.12% 323 906s
34944 35042 3197175.96 25 221 3201080.29 3197098.29 0.12% 324 917s
35532 35643 3197387.49 24 217 3201080.29 3197100.49 0.12% 325 927s
36133 36314 3197169.97 29 215 3201080.29 3197104.69 0.12% 327 938s
36804 36862 3197137.42 17 226 3201080.29 3197108.10 0.12% 328 948s
37352 37571 3197205.07 28 222 3201080.29 3197111.17 0.12% 328 959s
38061 38260 3197137.43 24 218 3201080.29 3197114.68 0.12% 328 970s
38750 38821 3197192.71 28 216 3201080.29 3197118.47 0.12% 328 981s
39311 39517 3197455.04 23 216 3201080.29 3197120.96 0.12% 328 992s
40007 40149 3197198.49 27 219 3201080.29 3197124.93 0.12% 328 1002s
40639 40789 3197200.69 28 220 3201080.29 3197127.47 0.12% 329 1013s
41279 41417 3197375.61 28 215 3201080.29 3197130.03 0.12% 330 1024s
41907 42087 3197340.88 22 215 3201080.29 3197131.42 0.12% 331 1035s
42577 42756 3197375.80 29 218 3201080.29 3197134.63 0.12% 332 1046s
43246 43444 3197182.20 22 224 3201080.29 3197137.77 0.12% 332 1056s
43934 44072 3197228.53 28 219 3201080.29 3197140.90 0.12% 331 1066s
44562 44651 3197231.07 29 218 3201080.29 3197143.54 0.12% 332 1076s
45141 45339 3197219.78 28 215 3201080.29 3197145.02 0.12% 333 1087s
45829 45881 3197221.51 28 215 3201080.29 3197147.64 0.12% 333 1096s
45868 45881 3197763.59 31 205 3201080.29 3197147.64 0.12% 333 1153s
46371 46594 3197220.63 31 212 3201080.29 3197149.81 0.12% 333 1165s
47084 47209 3197318.17 29 214 3201080.29 3197152.51 0.12% 333 1175s
47699 47910 3197240.56 29 216 3201080.29 3197153.48 0.12% 334 1186s
48400 48579 3197400.84 29 215 3201080.29 3197156.73 0.12% 334 1198s
Interrupt request received
49069 49136 3197338.84 23 219 3201080.29 3197159.49 0.12% 334 1207s
Cutting planes:
RLT: 599
Explored 49626 nodes (16652985 simplex iterations) in 1207.93 seconds (1294.85 work units)
Thread count was 8 (of 8 available processors)
Solution count 10: 3.20108e+06 3.20123e+06 3.20407e+06 ... 5.7298e+06
Solve interrupted
Best objective 3.201080291913e+06, best bound 3.197162135060e+06, gap 0.1224%
0
-
Hi Riley
I've tried to experiment with MIPFocus and Cuts to set them to 3,and try different branch direction,but all these measures make no difference.What do you mean by "improving the lower bound", say improving the lower bound of matrix range?
Thanks in advance!
0 -
Hi Suyue,
The "lower bound" here refers to the BestBd value in the node log. In this case "lower" because this is a minimization problem. It seems to be steadily improving so it would be nice if it improved a little faster.
You could always try our Parameter Tuning Tool - perhaps tuning for MIP gap with a 10 minute time limit.
- Riley
0 -
Thank you for your advice!
0
Please sign in to leave a comment.
Comments
4 comments