VarHint where MIP Start is not applicable (with pyomo)

Answered

Comments

8 comments

  • Jaromił Najman

    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ł

    0
    Comment actions Permalink
  • Jacob Mannhardt

    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 nonzeros
    Variable 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+06

    Presolve removed 2675 rows and 7652 columns
    Presolve time: 0.06s
    Presolved: 3053 rows, 3010 columns, 9035 nonzeros
    Variable types: 1853 continuous, 1157 integer (1154 binary)

    Root relaxation: objective 2.562045e+06, 1610 iterations, 0.07 seconds

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

    0 0 2573833.14 0 52 2645820.22 2573833.14 2.72% - 0s
    0 0 2581942.56 0 328 2645820.22 2581942.56 2.41% - 0s
    0 0 2581942.56 0 328 2645820.22 2581942.56 2.41% - 0s
    0 0 2582296.76 0 280 2645820.22 2582296.76 2.40% - 1s
    0 0 2582673.81 0 287 2645820.22 2582673.81 2.39% - 1s
    0 0 2582673.81 0 281 2645820.22 2582673.81 2.39% - 1s
    0 0 2582673.81 0 171 2645820.22 2582673.81 2.39% - 1s
    0 2 2582673.81 0 105 2645820.22 2582673.81 2.39% - 2s
    174 175 2592923.50 20 238 2645820.22 2582679.03 2.39% 601 5s
    H 266 239 2645820.2166 2582679.03 2.39% 500 6s
    H 300 273 2645820.2130 2582679.03 2.39% 502 7s
    360 344 2594580.54 35 343 2645820.21 2582679.03 2.39% 470 10s
    501 470 2603188.40 53 148 2645820.21 2582679.03 2.39% 380 15s
    768 601 2582679.03 9 396 2645820.21 2582679.03 2.39% 293 20s
    1051 815 2592923.50 26 265 2645820.21 2582679.03 2.39% 280 25s
    1504 1036 2586484.68 20 171 2645820.21 2582679.03 2.39% 257 30s
    1515 1048 2582679.03 13 339 2645820.21 2582679.03 2.39% 265 35s
    1841 1223 2591306.28 32 339 2645820.21 2582679.03 2.39% 261 40s
    2252 1313 2600946.43 54 386 2645820.21 2582679.03 2.39% 255 46s
    2551 1433 infeasible 80 2645820.21 2582679.03 2.39% 249 51s
    H 2660 1351 2645820.1771 2582679.03 2.39% 247 52s
    H 2661 1301 2645820.0226 2582679.03 2.39% 247 52s
    2794 1367 2593960.31 21 464 2645820.02 2582679.03 2.39% 247 56s
    3136 1450 2594509.96 23 487 2645820.02 2582679.03 2.39% 239 61s
    3366 1558 2594662.61 23 428 2645820.02 2582679.03 2.39% 248 66s
    3619 1579 2633159.21 22 466 2645820.02 2582679.03 2.39% 252 71s
    H 3623 1531 2645820.0144 2582679.03 2.39% 252 71s
    4005 1760 2587858.62 20 454 2645820.01 2582679.03 2.39% 242 76s
    4400 1899 infeasible 23 2645820.01 2582694.21 2.39% 240 80s
    H 4431 1899 2645819.9985 2582695.61 2.39% 240 80s
    4768 2212 2603082.01 28 239 2645820.00 2582712.52 2.39% 250 85s
    H 4878 2212 2645819.9604 2582712.52 2.39% 246 85s
    5415 2575 infeasible 19 2645819.96 2582742.04 2.38% 247 91s
    5766 2834 2585149.39 26 709 2645819.96 2582760.15 2.38% 250 95s
    6072 2948 infeasible 26 2645819.96 2582794.44 2.38% 254 100s
    6696 3324 2592917.88 25 290 2645819.96 2582828.05 2.38% 255 106s
    7126 3711 2603082.01 40 88 2645819.96 2582996.72 2.37% 258 112s
    7647 3850 2603108.07 29 267 2645819.96 2583116.49 2.37% 256 116s
    8092 4019 2594362.65 28 480 2645819.96 2583207.60 2.37% 262 122s
    8564 4217 2603108.07 43 134 2645819.96 2583374.40 2.36% 265 127s
    H 8589 4217 2645819.9410 2583374.40 2.36% 265 127s
    8726 4372 2593951.42 32 517 2645819.94 2583378.18 2.36% 267 130s
    9367 4625 2603085.76 46 237 2645819.94 2583648.60 2.35% 273 136s
    9928 5010 2603082.01 32 285 2645819.94 2583855.37 2.34% 278 142s
    10391 5141 infeasible 27 2645819.94 2583880.07 2.34% 278 145s
    11034 5323 2594144.90 22 562 2645819.94 2584242.47 2.33% 283 152s
    11335 5397 infeasible 36 2645819.94 2584254.99 2.33% 286 155s
    11994 5638 infeasible 30 2645819.94 2584714.21 2.31% 288 162s
    12286 5748 2594171.84 32 525 2645819.94 2584796.84 2.31% 289 166s
    12618 5873 2590406.62 19 475 2645819.94 2584912.50 2.30% 292 170s
    13048 5984 2587930.60 32 577 2645819.94 2585199.22 2.29% 294 175s
    13947 6220 2603065.89 43 289 2645819.94 2585548.97 2.28% 298 184s
    14309 6279 infeasible 36 2645819.94 2585779.85 2.27% 300 189s
    14708 6475 2635316.65 52 414 2645819.94 2586214.37 2.25% 301 194s
    15267 6613 2593337.38 29 718 2645819.94 2586703.10 2.23% 302 199s
    15729 7015 2598451.77 29 270 2645819.94 2587140.07 2.22% 303 205s
    16748 7145 2603162.35 66 178 2645819.94 2587258.42 2.21% 299 210s
    17268 7262 infeasible 35 2645819.94 2587832.31 2.19% 302 215s
    17705 7391 2592057.79 27 636 2645819.94 2588133.20 2.18% 305 220s
    18173 7633 infeasible 33 2645819.94 2588733.64 2.16% 308 226s
    18893 8165 2598381.93 33 478 2645819.94 2589055.18 2.15% 309 233s
    20224 8404 2592216.65 31 705 2645819.94 2589511.51 2.13% 305 239s
    20892 8499 infeasible 46 2645819.94 2589810.12 2.12% 307 247s
    21541 8678 2602842.26 40 377 2645819.94 2589987.17 2.11% 310 254s
    22284 8934 2598198.05 43 544 2645819.94 2590753.91 2.08% 310 262s
    H22565 8934 2645819.8935 2590805.03 2.08% 309 262s
    23104 8974 infeasible 32 2645819.89 2591092.07 2.07% 309 270s
    23534 9092 2596394.40 45 631 2645819.89 2591207.28 2.06% 311 277s
    24226 9216 infeasible 30 2645819.89 2591516.99 2.05% 313 285s
    25067 9696 2593571.49 41 549 2645819.89 2591900.68 2.04% 313 293s
    26751 9747 infeasible 34 2645819.89 2592100.71 2.03% 308 300s
    27545 9880 2601421.81 38 412 2645819.89 2592349.87 2.02% 309 308s
    28377 10313 2593004.81 34 567 2645819.89 2592479.61 2.02% 310 316s
    29763 10625 infeasible 46 2645819.89 2592571.73 2.01% 306 326s
    30972 10851 2596557.50 42 501 2645819.89 2592656.72 2.01% 305 336s
    32238 11420 2603072.30 53 225 2645819.89 2592750.51 2.01% 305 347s
    34542 11501 infeasible 24 2645819.89 2592851.63 2.00% 300 355s
    35370 11770 infeasible 31 2645819.89 2592864.74 2.00% 300 362s
    36339 12048 2594172.75 30 553 2645819.89 2592917.88 2.00% 302 371s
    37180 12360 2603082.01 35 241 2645819.89 2592917.88 2.00% 304 379s
    38042 12646 2593001.50 38 504 2645819.89 2592917.88 2.00% 307 388s
    39043 13195 2599312.88 36 423 2645819.89 2592917.88 2.00% 310 398s
    40363 13719 2596012.04 34 489 2645819.89 2592917.88 2.00% 309 407s
    41540 14904 2645294.69 56 183 2645819.89 2592917.88 2.00% 309 416s
    43725 15385 infeasible 40 2645819.89 2592917.88 2.00% 304 424s
    44696 16057 2593213.02 35 427 2645819.89 2592917.88 2.00% 303 434s
    46036 17246 2592933.98 36 541 2645819.89 2592917.88 2.00% 302 443s
    48307 17525 infeasible 56 2645819.89 2592917.88 2.00% 297 449s
    48911 17827 2592917.88 34 325 2645819.89 2592917.88 2.00% 297 457s
    49787 18251 2603082.01 33 239 2645819.89 2592917.88 2.00% 297 464s
    50594 18754 2603082.01 50 163 2645819.89 2592917.88 2.00% 297 473s
    51776 19140 2603082.01 34 263 2645819.89 2592917.88 2.00% 297 482s
    52864 19902 2595948.58 39 469 2645819.89 2592917.88 2.00% 296 489s
    54394 20304 2592917.88 41 418 2645819.89 2592917.88 2.00% 295 497s
    55212 20703 2603082.01 45 263 2645819.89 2592917.88 2.00% 294 505s
    56246 21382 2602383.23 45 329 2645819.89 2592917.88 2.00% 294 514s
    57978 21666 infeasible 42 2645819.89 2592917.88 2.00% 292 523s
    58902 22023 2592977.39 27 414 2645819.89 2592917.88 2.00% 293 531s
    59938 23185 2599113.81 48 394 2645819.89 2592917.88 2.00% 292 542s
    62432 23403 infeasible 45 2645819.89 2592917.88 2.00% 289 547s
    63033 23674 2603082.01 37 214 2645819.89 2592917.88 2.00% 289 553s
    63724 23973 2592917.88 37 395 2645819.89 2592917.88 2.00% 289 560s
    64487 24249 2593069.69 42 456 2645819.89 2592917.88 2.00% 289 566s
    65229 24575 2603162.35 41 173 2645819.89 2592917.88 2.00% 289 574s
    66171 25019 2644994.17 63 152 2645819.89 2592917.88 2.00% 289 581s
    67068 25713 2645758.13 74 177 2645819.89 2592917.88 2.00% 289 589s
    68829 25890 infeasible 49 2645819.89 2592917.88 2.00% 287 597s
    69313 26176 2592917.88 42 409 2645819.89 2592917.88 2.00% 287 605s
    70209 26493 2595364.50 41 383 2645819.89 2592917.88 2.00% 287 612s
    71196 26950 2593546.37 46 455 2645819.89 2592917.88 2.00% 287 621s
    72299 27702 2593732.49 39 438 2645819.89 2592917.88 2.00% 287 630s
    73909 28184 infeasible 47 2645819.89 2592917.88 2.00% 286 640s
    74942 28557 2645809.44 79 213 2645819.89 2592917.88 2.00% 286 650s
    75946 29001 2617195.83 43 209 2645819.89 2592917.88 2.00% 286 662s
    77243 30177 infeasible 42 2645819.89 2592917.88 2.00% 287 674s
    79852 30464 infeasible 32 2645819.89 2592917.88 2.00% 285 681s
    80666 30890 infeasible 38 2645819.89 2592917.88 2.00% 285 690s
    81617 31263 2645797.82 60 184 2645819.89 2592917.88 2.00% 285 698s
    82442 31664 2627878.35 38 534 2645819.89 2592917.88 2.00% 285 707s
    83442 31945 infeasible 35 2645819.89 2592917.88 2.00% 285 716s
    84402 32458 2603082.01 44 273 2645819.89 2592917.88 2.00% 286 725s

    Solver Options:
    "ObjScale": -0.5,
    "LogToConsole": 1,
    "NumericFocus": 2,
    "ScaleFlag": 2,
    "NodeMethod": 1,
    "InfUnbdInfo": 1,
    "DualReductions": 1,
    "Heuristics": 0.2,
    "Threads": 8
    0
    Comment actions Permalink
  • Jaromił Najman

    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ł

    0
    Comment actions Permalink
  • Jacob Mannhardt

    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

    0
    Comment actions Permalink
  • Jaromił Najman

    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ł

    0
    Comment actions Permalink
  • Jacob Mannhardt

    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

    0
    Comment actions Permalink
  • Jaromił Najman

    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ł

    0
    Comment actions Permalink
  • Jacob Mannhardt

    Dear Jaromił,

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

    Best wishes
    Jacob

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk