• Gurobi Staff

Hi Jacob,

1.) Can I check why my B&B algorithm is slow? I have tried the measures proposed here in the forum, but nothing has really helped. It takes roughly 500 iterations per node to solve the above mentioned problem, even with aggressive Cuts and Presolve. Additionally, the best bound is almost stuck. Any ideas?

Could you post the log file? Did you have a look at the list of most important parameters? You could also try Gurobi's command line tuning tool if the problem solves within a considerable amount of time.

2.) Is it good practice to use explicit Big-M Formulations (with a rather good estimation of the Big-M) or are SOS or different formulations better in Gurobi?

Yes, if you have a good Big-M estimation then Big-M formulations tend to work very well.

EDIT: I've now achieved to set the VarHintVal attribute but I can't say that it solves the problem quicker. It seems to be equally slow. Is there a way to check if it a) worked to set the value and b) if it helped?

In addition to VarHintVal, you could also set the VarHintPri attribute to provide your confidence level for the hint. Usually, one would see Gurobi find a feasible point faster or at least change the optimization path to lean more towards the user's hints. If the hints are rather poor then the runtime may increase instead of decreasing.

Best regards,
Jaromił

Hi Jaromił,

thank you for your kind answer and sorry for my late response! Please find my (preliminary) log and my selected solver options below - the algorithm is still running.

As I have described above, my problem is not too large (1853 continuous, 1154 binary variables after presolve [how come presolve added non-binary integer variables?]). The binary variables are predominantly used in Big-M linearizations of complementarity constraints, and very few because of a binary expansion of a bilinear term in the objective function. The matrix and RHS ranges are unfortunately quite large, which is due to the fact that my problem has a wide range of physical values. I have designed a constraint (row) and variable (column) scaling algorithm myself, which already reduces the Frobenius Norm from 7.8e+5 to 2.5e+3 before the problem is passed to the solver. As you can see, my initial warmstart guess is already quite good, with an initial optimality gap of only 2.72%. Unfortunately, it is only reduced to 1.97% in 2300s (not depicted below). Especially the incumbent solution is almost stuck. Judging from experience, the incumbent solution might well be the optimal solution.

I have read the tuning manuals thoroughly and tried a multitude of solver options, some with better results (Heuristics) and some with worse (NodeMethod = 2, because barrier has the lowest worst-case-speed, correct?). I have not yet tried the tuning tool, but will do so if you say it can significantly improve the solution speed and quality.

If the warmstart is used and an incumbent value is found, the VarHint procedure is probably neglected, right?

Can you give me an indication as where to look (within the realm of gurobi or my own algorithm) to improve this slow optimization? Thank you so much for your help, Jaromił!

Cheers Jacob

P.S.: an additional information I should give: I'm currently running the problem from a debugger in an IDE, so command prompt runs should be faster. But nevertheless, the current run for this model is incredibly slow.

Optimize a model with 5728 rows, 10662 columns and 15181 nonzerosVariable types: 6354 continuous, 4308 integer (4308 binary)Coefficient statistics:Matrix range [7e-06, 3e+02]Objective range [3e+01, 6e+05]Bounds range [1e+00, 1e+00]RHS range [5e-06, 5e+06]User MIP start produced solution with objective 2.64582e+06 (0.05s)Loaded user MIP start with objective 2.64582e+06Presolve removed 2675 rows and 7652 columnsPresolve time: 0.06sPresolved: 3053 rows, 3010 columns, 9035 nonzerosVariable types: 1853 continuous, 1157 integer (1154 binary)Root relaxation: objective 2.562045e+06, 1610 iterations, 0.07 secondsNodes | Current Node | Objective Bounds | WorkExpl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time0 0 2573833.14 0 52 2645820.22 2573833.14 2.72% - 0s0 0 2581942.56 0 328 2645820.22 2581942.56 2.41% - 0s0 0 2581942.56 0 328 2645820.22 2581942.56 2.41% - 0s0 0 2582296.76 0 280 2645820.22 2582296.76 2.40% - 1s0 0 2582673.81 0 287 2645820.22 2582673.81 2.39% - 1s0 0 2582673.81 0 281 2645820.22 2582673.81 2.39% - 1s0 0 2582673.81 0 171 2645820.22 2582673.81 2.39% - 1s0 2 2582673.81 0 105 2645820.22 2582673.81 2.39% - 2s174 175 2592923.50 20 238 2645820.22 2582679.03 2.39% 601 5sH 266 239 2645820.2166 2582679.03 2.39% 500 6sH 300 273 2645820.2130 2582679.03 2.39% 502 7s360 344 2594580.54 35 343 2645820.21 2582679.03 2.39% 470 10s501 470 2603188.40 53 148 2645820.21 2582679.03 2.39% 380 15s768 601 2582679.03 9 396 2645820.21 2582679.03 2.39% 293 20s1051 815 2592923.50 26 265 2645820.21 2582679.03 2.39% 280 25s1504 1036 2586484.68 20 171 2645820.21 2582679.03 2.39% 257 30s1515 1048 2582679.03 13 339 2645820.21 2582679.03 2.39% 265 35s1841 1223 2591306.28 32 339 2645820.21 2582679.03 2.39% 261 40s2252 1313 2600946.43 54 386 2645820.21 2582679.03 2.39% 255 46s2551 1433 infeasible 80 2645820.21 2582679.03 2.39% 249 51sH 2660 1351 2645820.1771 2582679.03 2.39% 247 52sH 2661 1301 2645820.0226 2582679.03 2.39% 247 52s2794 1367 2593960.31 21 464 2645820.02 2582679.03 2.39% 247 56s3136 1450 2594509.96 23 487 2645820.02 2582679.03 2.39% 239 61s3366 1558 2594662.61 23 428 2645820.02 2582679.03 2.39% 248 66s3619 1579 2633159.21 22 466 2645820.02 2582679.03 2.39% 252 71sH 3623 1531 2645820.0144 2582679.03 2.39% 252 71s4005 1760 2587858.62 20 454 2645820.01 2582679.03 2.39% 242 76s4400 1899 infeasible 23 2645820.01 2582694.21 2.39% 240 80sH 4431 1899 2645819.9985 2582695.61 2.39% 240 80s4768 2212 2603082.01 28 239 2645820.00 2582712.52 2.39% 250 85sH 4878 2212 2645819.9604 2582712.52 2.39% 246 85s5415 2575 infeasible 19 2645819.96 2582742.04 2.38% 247 91s5766 2834 2585149.39 26 709 2645819.96 2582760.15 2.38% 250 95s6072 2948 infeasible 26 2645819.96 2582794.44 2.38% 254 100s6696 3324 2592917.88 25 290 2645819.96 2582828.05 2.38% 255 106s7126 3711 2603082.01 40 88 2645819.96 2582996.72 2.37% 258 112s7647 3850 2603108.07 29 267 2645819.96 2583116.49 2.37% 256 116s8092 4019 2594362.65 28 480 2645819.96 2583207.60 2.37% 262 122s8564 4217 2603108.07 43 134 2645819.96 2583374.40 2.36% 265 127sH 8589 4217 2645819.9410 2583374.40 2.36% 265 127s8726 4372 2593951.42 32 517 2645819.94 2583378.18 2.36% 267 130s9367 4625 2603085.76 46 237 2645819.94 2583648.60 2.35% 273 136s9928 5010 2603082.01 32 285 2645819.94 2583855.37 2.34% 278 142s10391 5141 infeasible 27 2645819.94 2583880.07 2.34% 278 145s11034 5323 2594144.90 22 562 2645819.94 2584242.47 2.33% 283 152s11335 5397 infeasible 36 2645819.94 2584254.99 2.33% 286 155s11994 5638 infeasible 30 2645819.94 2584714.21 2.31% 288 162s12286 5748 2594171.84 32 525 2645819.94 2584796.84 2.31% 289 166s12618 5873 2590406.62 19 475 2645819.94 2584912.50 2.30% 292 170s13048 5984 2587930.60 32 577 2645819.94 2585199.22 2.29% 294 175s13947 6220 2603065.89 43 289 2645819.94 2585548.97 2.28% 298 184s14309 6279 infeasible 36 2645819.94 2585779.85 2.27% 300 189s14708 6475 2635316.65 52 414 2645819.94 2586214.37 2.25% 301 194s15267 6613 2593337.38 29 718 2645819.94 2586703.10 2.23% 302 199s15729 7015 2598451.77 29 270 2645819.94 2587140.07 2.22% 303 205s16748 7145 2603162.35 66 178 2645819.94 2587258.42 2.21% 299 210s17268 7262 infeasible 35 2645819.94 2587832.31 2.19% 302 215s17705 7391 2592057.79 27 636 2645819.94 2588133.20 2.18% 305 220s18173 7633 infeasible 33 2645819.94 2588733.64 2.16% 308 226s18893 8165 2598381.93 33 478 2645819.94 2589055.18 2.15% 309 233s20224 8404 2592216.65 31 705 2645819.94 2589511.51 2.13% 305 239s20892 8499 infeasible 46 2645819.94 2589810.12 2.12% 307 247s21541 8678 2602842.26 40 377 2645819.94 2589987.17 2.11% 310 254s22284 8934 2598198.05 43 544 2645819.94 2590753.91 2.08% 310 262sH22565 8934 2645819.8935 2590805.03 2.08% 309 262s23104 8974 infeasible 32 2645819.89 2591092.07 2.07% 309 270s23534 9092 2596394.40 45 631 2645819.89 2591207.28 2.06% 311 277s24226 9216 infeasible 30 2645819.89 2591516.99 2.05% 313 285s25067 9696 2593571.49 41 549 2645819.89 2591900.68 2.04% 313 293s26751 9747 infeasible 34 2645819.89 2592100.71 2.03% 308 300s27545 9880 2601421.81 38 412 2645819.89 2592349.87 2.02% 309 308s28377 10313 2593004.81 34 567 2645819.89 2592479.61 2.02% 310 316s29763 10625 infeasible 46 2645819.89 2592571.73 2.01% 306 326s30972 10851 2596557.50 42 501 2645819.89 2592656.72 2.01% 305 336s32238 11420 2603072.30 53 225 2645819.89 2592750.51 2.01% 305 347s34542 11501 infeasible 24 2645819.89 2592851.63 2.00% 300 355s35370 11770 infeasible 31 2645819.89 2592864.74 2.00% 300 362s36339 12048 2594172.75 30 553 2645819.89 2592917.88 2.00% 302 371s37180 12360 2603082.01 35 241 2645819.89 2592917.88 2.00% 304 379s38042 12646 2593001.50 38 504 2645819.89 2592917.88 2.00% 307 388s39043 13195 2599312.88 36 423 2645819.89 2592917.88 2.00% 310 398s40363 13719 2596012.04 34 489 2645819.89 2592917.88 2.00% 309 407s41540 14904 2645294.69 56 183 2645819.89 2592917.88 2.00% 309 416s43725 15385 infeasible 40 2645819.89 2592917.88 2.00% 304 424s44696 16057 2593213.02 35 427 2645819.89 2592917.88 2.00% 303 434s46036 17246 2592933.98 36 541 2645819.89 2592917.88 2.00% 302 443s48307 17525 infeasible 56 2645819.89 2592917.88 2.00% 297 449s48911 17827 2592917.88 34 325 2645819.89 2592917.88 2.00% 297 457s49787 18251 2603082.01 33 239 2645819.89 2592917.88 2.00% 297 464s50594 18754 2603082.01 50 163 2645819.89 2592917.88 2.00% 297 473s51776 19140 2603082.01 34 263 2645819.89 2592917.88 2.00% 297 482s52864 19902 2595948.58 39 469 2645819.89 2592917.88 2.00% 296 489s54394 20304 2592917.88 41 418 2645819.89 2592917.88 2.00% 295 497s55212 20703 2603082.01 45 263 2645819.89 2592917.88 2.00% 294 505s56246 21382 2602383.23 45 329 2645819.89 2592917.88 2.00% 294 514s57978 21666 infeasible 42 2645819.89 2592917.88 2.00% 292 523s58902 22023 2592977.39 27 414 2645819.89 2592917.88 2.00% 293 531s59938 23185 2599113.81 48 394 2645819.89 2592917.88 2.00% 292 542s62432 23403 infeasible 45 2645819.89 2592917.88 2.00% 289 547s63033 23674 2603082.01 37 214 2645819.89 2592917.88 2.00% 289 553s63724 23973 2592917.88 37 395 2645819.89 2592917.88 2.00% 289 560s64487 24249 2593069.69 42 456 2645819.89 2592917.88 2.00% 289 566s65229 24575 2603162.35 41 173 2645819.89 2592917.88 2.00% 289 574s66171 25019 2644994.17 63 152 2645819.89 2592917.88 2.00% 289 581s67068 25713 2645758.13 74 177 2645819.89 2592917.88 2.00% 289 589s68829 25890 infeasible 49 2645819.89 2592917.88 2.00% 287 597s69313 26176 2592917.88 42 409 2645819.89 2592917.88 2.00% 287 605s70209 26493 2595364.50 41 383 2645819.89 2592917.88 2.00% 287 612s71196 26950 2593546.37 46 455 2645819.89 2592917.88 2.00% 287 621s72299 27702 2593732.49 39 438 2645819.89 2592917.88 2.00% 287 630s73909 28184 infeasible 47 2645819.89 2592917.88 2.00% 286 640s74942 28557 2645809.44 79 213 2645819.89 2592917.88 2.00% 286 650s75946 29001 2617195.83 43 209 2645819.89 2592917.88 2.00% 286 662s77243 30177 infeasible 42 2645819.89 2592917.88 2.00% 287 674s79852 30464 infeasible 32 2645819.89 2592917.88 2.00% 285 681s80666 30890 infeasible 38 2645819.89 2592917.88 2.00% 285 690s81617 31263 2645797.82 60 184 2645819.89 2592917.88 2.00% 285 698s82442 31664 2627878.35 38 534 2645819.89 2592917.88 2.00% 285 707s83442 31945 infeasible 35 2645819.89 2592917.88 2.00% 285 716s84402 32458 2603082.01 44 273 2645819.89 2592917.88 2.00% 286 725sSolver Options:"ObjScale": -0.5,"LogToConsole": 1,"NumericFocus": 2,"ScaleFlag": 2,"NodeMethod": 1,"InfUnbdInfo": 1,"DualReductions": 1,"Heuristics": 0.2,"Threads": 8
• Gurobi Staff

Hi Jacob,

As I have described above, my problem is not too large

Please note that the complexity of a model cannot be measured by its size. There are still small problems in the MIPLib2017 which are still unsolved or cannot be solved quickly.

how come presolve added non-binary integer variables?

What do you mean exactly? The number of variables after presolve is lower

Variable types: 6354 continuous, 4308 integer (4308 binary)[...]Variable types: 1853 continuous, 1157 integer (1154 binary)

NodeMethod = 2, because barrier has the lowest worst-case-speed, correct?

Yes, however it does not profit from warm-start in the B&B tree.

If the warmstart is used and an incumbent value is found, the VarHint procedure is probably neglected, right?

No, the VarHint values are still used and may significantly change the optimization path. If finding a feasible solution is not a problem, you might as well omit using VarHint attributes.

Can you give me an indication as where to look (within the realm of gurobi or my own algorithm) to improve this slow optimization?

Given the fact that the lower bound "gets stuck" at $$2592917.88$$ for quite some time, it might be worth to try searching for a better feasible point. You could try the parameter NoRelHeurTime=300 to let the no relaxation heuristic run for 300 seconds. It will try to improve the feasible point provided by your MIP start before solving the root node relaxation. For now, you should also try avoid setting the parameters ObjScale, NumericFocus, and ScaleFlag as they may negatively affect performance and should rather only be used when you suspect that your problem suffers from numerical issues. While large rhs values are not ideal, they are not as bad as large matrix and objective coefficients and variable bounds. You could also experiment with the MIPFocus parameter.

Best regards,
Jaromił

Dear Jaromił,

thank you once again for your quick and extensive answer - brilliant community support here!

What do you mean exactly? The number of variables after presolve is lower

I was wondering why my problem has 1157 integer variables but only 1154 binary variables after presolve, even though all my integer variables in the original model were binary. Thus, presolve added three non-binary integer variables. Though, this was more an observation than an actual question.

No, the VarHint values are still used and may significantly change the optimization path. If finding a feasible solution is not a problem, you might as well omit using VarHint attributes.

That is good to know, thank you!

For now, you should also try avoid setting the parameters ObjScale, NumericFocus, and ScaleFlag as they may negatively affect performance and should rather only be used when you suspect that your problem suffers from numerical issues.

That is an important point that I didn't know. I thought these parameters would generally improve the solution and thus performance.

Thanks again, Jaromił!
Best wishes
Jacob

• Gurobi Staff

Hi Jacob,

I was wondering why my problem has 1157 integer variables but only 1154 binary variables after presolve, even though all my integer variables in the original model were binary. Thus, presolve added three non-binary integer variables. Though, this was more an observation than an actual question.

I didn't notice this, thank you for pointing out. Gurobi detects specific structure and reformulates the problem in a way it thinks, that it is most beneficial for the solution process. Aggregation of variables and constraints may lead to the introduction of integer variables by condensing multiple binaries into one integer variable, or by exploiting specific structure which requires the introduction of integer variables.

In a case where you would add general constraints or quadratic terms to your problem, you could observe that Gurobi adds variables and constraints to reformulate some of the general constraints and/or quadratic terms. This means, that in extreme cases, the presolved model might have more variables and constraints than the original one.

thank you once again for your quick and extensive answer - brilliant community support here!

Thank you for your kind words! Any feedback is always highly appreciated!

Best regards,
Jaromił

Hi Jaromił,

interesting fact about the Presolve algorithm!

As you have recommended, I have executed the Tuning Tool, with few new hints (only setting DegenMoves, a parameter I had not previously heard about). Currently my solution is stuck at a 1.62% gap with the exact same Best Bd and Incumbent Solution for 1400 out of 3000 seconds and 460,000 out of 540,000 explored nodes. Interestingly, my provided initial solution is still (with very little improvement) the current incumbent solution. Is there a feature (maybe by changing BranchDir?) to rather search in the vicinity of the incumbent solution to close the gap more quickly?

Maybe on a more abstract note, I have the feeling that my multitude of binary variables in the Big-M constraints slows my problem incredibly down. Do you have any experience with other approaches to complementarity constraints in Gurobi (SOS, regularization, penalty, ...)? If this leads too far away, I absolutely understand if this exceeds the purpose of this forum!

Thank you again for your brilliant help,
Jacob

• Gurobi Staff

Hi Jacob,

If you have the feeling that the dual bound is the problem in this case, you can try setting

RINS=0
Heuristics=0.001
MIPFocus=3
BranchDir=1
VarBranch=3

This will focus heavily on the improvement of the dual bound while almost completely disabling feasible point heuristics. You could further experiment with the different settings for BranchDir and VarBranch.

Maybe on a more abstract note, I have the feeling that my multitude of binary variables in the Big-M constraints slows my problem incredibly down. Do you have any experience with other approaches to complementarity constraints in Gurobi (SOS, regularization, penalty, ...)?

Big-M formulations work well as long as the Big-M value is chosen carefully, i.e., the values are rather tight. In general, one can say the same for the other approaches you listed. They all may work well in one case or another. If the parameter tuning approach is not successful, you should consider improving the coefficient ranges and also the rhs range. A different approach would be to increase the feasibility tolerances and see whether this helps.

Best regards,
Jaromił

Dear Jaromił,

thank you once again for your help! I will try this approach!

Best wishes
Jacob