MIP start did not produce a new incumbent solution with a feasible MIPStart
AnsweredHi,
I am using a self-written heuristic to find an initial feasible solution that I can provide to Gurobi as a MIPStart. After that I use the NoRelHeur to improve the solution before solving it further. It has been working quite well, but now I am getting the message "MIP start did not produce a new incumbent solution". I have encountered this message before, when I was still developing my heuristic. My heuristic only determines the values of a part of the binary decision variables. At the time, I fixed the variables in the model to their values in my MIP start (in line with this article), which lead to an infeasible model. By computing an IIS I found which constraints made the model infeasible, and using that I improved my heuristic.
However, this time, fixing the the variables in the model to their values in my MIP start doesn't result in an infeasible model. On the contrary, the NoRel heuristic finished phase 1 really fast, which makes sense, since the "MIPStart constraints" make the problem way smaller and easier to solve.
I have provided the \(\texttt{.mps}\) and \(\texttt{.mst}\) files and part of the Gurobi log via this link. Both cases can be found over here:
1.) Case_1: The \(\texttt{.mps}\) and \(\texttt{.mst}\) files for the model that uses MIPStart, which doesn't lead to a new incumbent solution. It takes too long to come up with a first feasible solution, so I don't know whether the model is feasible or not (but it should be feasible since case 2 is feasible).
2.) Case_2: The \(\texttt{.mps}\) file of the model that uses the MIPStart values as constraints, which does lead to a feasible model. The added constraints are named "MIPStart_fixed-{...},{...}", with "..." being the indices of the decision variable involved.
For other users encountering problems with MIPStart, here are some other posts on the forum that might be useful: post1, post2, and post3.
Do you have any idea on what the problem is and/or how to solve this issue? And if you spot any other abnormalities in the log files, please let me know as well!
Thanks in advance!
Best regards,
Koen Timmermans
0
-
-
Gurobi Staff
Hi Koen,
Thanks for sharing the logs, MIP start files and model files.
I noticed that you have provided a partial MIP start with values for 135 binary variables out of 329,147 binary variables, which is approximately 0.04%. When a partial MIP start is given, Gurobi fixes the integer/binary variables to their MIP start values and solves a feasibility problem. However, since you only provide values for 0.04% of the binary variables in your MIP start, the resulting feasibility problem remains as large as your original model, making it hard to solve. This is also indicated by the warning message in the log:
Warning: Completing partial solution with 329012 unfixed non-continuous variables out of 329147
Partial MIP starts work best if they result in a lot of fixings of binary variables, such that the resulting model is quick to solve.
Now, when you manually fix variables as per the MIP start values and solve the "manually fixed" model, it solves relatively quickly (your case 2). This could be due to some additional presolve reductions Gurobi is able to do on the "manually fixed" model, which were not possible when the MIP start was given to the original model. Also, the NoRel heuristic, which finds the quick feasible solution for the "manually fixed" model, is not used when processing MIP starts.
There are a couple of things you can try:
- Provide start values for more binary variables in the MIP start, particularly those that will result in a higher number of fixings.
- Solve your "manually fixed" model to obtain a feasible solution, and then use it as a MIP start for your original model.
Best regards,
Simran
0 -
-
Hi Simran,
Thanks for the quick reply!
From what you explain, I understand why it is difficult for Gurobi to use my MIP start values for an initial feasible solution. I can make some changes to my heuristic, to get values for more binary decision variables. I hope that that makes it easier for Gurobi to solve the feasibility problem.
Your explanation also made me think of increasing the SubMIPNodes parameter value, to give Gurobi more time to explore my MIP start. I have increased the SubMIPNodes parameter to 25000, and now it finds a new incumbent solution (see the log below).
Set parameter LogFile to value "Gurobi_log_2"
Set parameter SubMIPNodes to value 25000
Set parameter MIPFocus to value 2
Set parameter TimeLimit to value 1800
Gurobi Optimizer version 10.0.1 build v10.0.1rc0 (win64)
CPU model: 11th Gen Intel(R) Core(TM) i7-11700 @ 2.50GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 8 physical cores, 16 logical processors, using up to 16 threads
Academic license - for non-commercial use only - registered to {}
Optimize a model with 1282346 rows, 367514 columns and 5483081 nonzeros
Model fingerprint: 0xd6381d48
Variable types: 38367 continuous, 329147 integer (329147 binary)
Coefficient statistics:
Matrix range [3e-01, 1e+03]
Objective range [1e+00, 5e+02]
Bounds range [1e+00, 7e+02]
RHS range [1e+00, 2e+03]
Warning: Completing partial solution with 329012 unfixed non-continuous variables out of 329147
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 5s
Processing user MIP start: 0 nodes explored in subMIP, total elapsed time 10s
Processing user MIP start: 201 nodes explored in subMIP, total elapsed time 15s
Processing user MIP start: 512 nodes explored in subMIP, total elapsed time 20s
Processing user MIP start: 541 nodes explored in subMIP, total elapsed time 25s
Processing user MIP start: 557 nodes explored in subMIP, total elapsed time 30s
Processing user MIP start: 579 nodes explored in subMIP, total elapsed time 35s
Processing user MIP start: 594 nodes explored in subMIP, total elapsed time 40s
Processing user MIP start: 754 nodes explored in subMIP, total elapsed time 45s
Processing user MIP start: 950 nodes explored in subMIP, total elapsed time 50s
Processing user MIP start: 1151 nodes explored in subMIP, total elapsed time 55s
Processing user MIP start: 1381 nodes explored in subMIP, total elapsed time 60s
Processing user MIP start: 1575 nodes explored in subMIP, total elapsed time 65s
Processing user MIP start: 1785 nodes explored in subMIP, total elapsed time 70s
Processing user MIP start: 2024 nodes explored in subMIP, total elapsed time 75s
Processing user MIP start: 2241 nodes explored in subMIP, total elapsed time 80s
Processing user MIP start: 2465 nodes explored in subMIP, total elapsed time 85s
Processing user MIP start: 2715 nodes explored in subMIP, total elapsed time 90s
Processing user MIP start: 2919 nodes explored in subMIP, total elapsed time 95s
Processing user MIP start: 3147 nodes explored in subMIP, total elapsed time 100s
Processing user MIP start: 3404 nodes explored in subMIP, total elapsed time 105s
Processing user MIP start: 3670 nodes explored in subMIP, total elapsed time 110s
Processing user MIP start: 3869 nodes explored in subMIP, total elapsed time 115s
Processing user MIP start: 4076 nodes explored in subMIP, total elapsed time 120s
Processing user MIP start: 4317 nodes explored in subMIP, total elapsed time 125s
Processing user MIP start: 4537 nodes explored in subMIP, total elapsed time 130s
Processing user MIP start: 4806 nodes explored in subMIP, total elapsed time 135s
Processing user MIP start: 5059 nodes explored in subMIP, total elapsed time 140s
Processing user MIP start: 5271 nodes explored in subMIP, total elapsed time 145s
Processing user MIP start: 5506 nodes explored in subMIP, total elapsed time 150s
Processing user MIP start: 5786 nodes explored in subMIP, total elapsed time 155s
Processing user MIP start: 6033 nodes explored in subMIP, total elapsed time 160s
Processing user MIP start: 6264 nodes explored in subMIP, total elapsed time 165s
Processing user MIP start: 6465 nodes explored in subMIP, total elapsed time 170s
Processing user MIP start: 6676 nodes explored in subMIP, total elapsed time 175s
Processing user MIP start: 6877 nodes explored in subMIP, total elapsed time 180s
Processing user MIP start: 7077 nodes explored in subMIP, total elapsed time 185s
Processing user MIP start: 7292 nodes explored in subMIP, total elapsed time 190s
Processing user MIP start: 7547 nodes explored in subMIP, total elapsed time 195s
Processing user MIP start: 7795 nodes explored in subMIP, total elapsed time 200s
Processing user MIP start: 8106 nodes explored in subMIP, total elapsed time 205s
Processing user MIP start: 8307 nodes explored in subMIP, total elapsed time 210s
Processing user MIP start: 8529 nodes explored in subMIP, total elapsed time 215s
Processing user MIP start: 8785 nodes explored in subMIP, total elapsed time 220s
Processing user MIP start: 8998 nodes explored in subMIP, total elapsed time 225s
Processing user MIP start: 9204 nodes explored in subMIP, total elapsed time 230s
Processing user MIP start: 9433 nodes explored in subMIP, total elapsed time 235s
Processing user MIP start: 9709 nodes explored in subMIP, total elapsed time 240s
Processing user MIP start: 9954 nodes explored in subMIP, total elapsed time 245s
Processing user MIP start: 10201 nodes explored in subMIP, total elapsed time 250s
Processing user MIP start: 10201 nodes explored in subMIP, total elapsed time 255s
Processing user MIP start: 10201 nodes explored in subMIP, total elapsed time 260s
Processing user MIP start: 10201 nodes explored in subMIP, total elapsed time 265s
Processing user MIP start: 10206 nodes explored in subMIP, total elapsed time 270s
Processing user MIP start: 10228 nodes explored in subMIP, total elapsed time 275s
Processing user MIP start: 10248 nodes explored in subMIP, total elapsed time 280s
Processing user MIP start: 10264 nodes explored in subMIP, total elapsed time 285s
Processing user MIP start: 10280 nodes explored in subMIP, total elapsed time 290s
Processing user MIP start: 10321 nodes explored in subMIP, total elapsed time 295s
Processing user MIP start: 10360 nodes explored in subMIP, total elapsed time 300s
Processing user MIP start: 10393 nodes explored in subMIP, total elapsed time 305s
Processing user MIP start: 10426 nodes explored in subMIP, total elapsed time 310s
Processing user MIP start: 10453 nodes explored in subMIP, total elapsed time 315s
Processing user MIP start: 10486 nodes explored in subMIP, total elapsed time 320s
Processing user MIP start: 10523 nodes explored in subMIP, total elapsed time 325s
Processing user MIP start: 10559 nodes explored in subMIP, total elapsed time 330s
Processing user MIP start: 10594 nodes explored in subMIP, total elapsed time 335s
Processing user MIP start: 10626 nodes explored in subMIP, total elapsed time 340s
Processing user MIP start: 10658 nodes explored in subMIP, total elapsed time 345s
Processing user MIP start: 10678 nodes explored in subMIP, total elapsed time 350s
Processing user MIP start: 10691 nodes explored in subMIP, total elapsed time 355s
Processing user MIP start: 10705 nodes explored in subMIP, total elapsed time 360s
Processing user MIP start: 10731 nodes explored in subMIP, total elapsed time 365s
Processing user MIP start: 10770 nodes explored in subMIP, total elapsed time 370s
Processing user MIP start: 10808 nodes explored in subMIP, total elapsed time 375s
Processing user MIP start: 10846 nodes explored in subMIP, total elapsed time 380s
Processing user MIP start: 10884 nodes explored in subMIP, total elapsed time 385s
Processing user MIP start: 10921 nodes explored in subMIP, total elapsed time 390s
Processing user MIP start: 10954 nodes explored in subMIP, total elapsed time 395s
Processing user MIP start: 10985 nodes explored in subMIP, total elapsed time 400s
Processing user MIP start: 11014 nodes explored in subMIP, total elapsed time 405s
Processing user MIP start: 11067 nodes explored in subMIP, total elapsed time 410s
Processing user MIP start: 11126 nodes explored in subMIP, total elapsed time 415s
Processing user MIP start: 11215 nodes explored in subMIP, total elapsed time 420s
Processing user MIP start: 11317 nodes explored in subMIP, total elapsed time 425s
Processing user MIP start: 11448 nodes explored in subMIP, total elapsed time 430s
Processing user MIP start: 11580 nodes explored in subMIP, total elapsed time 435s
Processing user MIP start: 11710 nodes explored in subMIP, total elapsed time 440s
Processing user MIP start: 11795 nodes explored in subMIP, total elapsed time 445s
Processing user MIP start: 11903 nodes explored in subMIP, total elapsed time 450s
Processing user MIP start: 11999 nodes explored in subMIP, total elapsed time 455s
Processing user MIP start: 12095 nodes explored in subMIP, total elapsed time 460s
Processing user MIP start: 12184 nodes explored in subMIP, total elapsed time 465s
Processing user MIP start: 12297 nodes explored in subMIP, total elapsed time 470s
Processing user MIP start: 12413 nodes explored in subMIP, total elapsed time 475s
Processing user MIP start: 12509 nodes explored in subMIP, total elapsed time 480s
Processing user MIP start: 12611 nodes explored in subMIP, total elapsed time 485s
Processing user MIP start: 12708 nodes explored in subMIP, total elapsed time 490s
Processing user MIP start: 12814 nodes explored in subMIP, total elapsed time 495s
Processing user MIP start: 12922 nodes explored in subMIP, total elapsed time 500s
Processing user MIP start: 13032 nodes explored in subMIP, total elapsed time 505s
Processing user MIP start: 13141 nodes explored in subMIP, total elapsed time 510s
Processing user MIP start: 13244 nodes explored in subMIP, total elapsed time 515s
Processing user MIP start: 13346 nodes explored in subMIP, total elapsed time 520s
Processing user MIP start: 13489 nodes explored in subMIP, total elapsed time 525s
Processing user MIP start: 13647 nodes explored in subMIP, total elapsed time 530s
Processing user MIP start: 13810 nodes explored in subMIP, total elapsed time 535s
Processing user MIP start: 13977 nodes explored in subMIP, total elapsed time 540s
Processing user MIP start: 14138 nodes explored in subMIP, total elapsed time 545s
Processing user MIP start: 14294 nodes explored in subMIP, total elapsed time 550s
Processing user MIP start: 14465 nodes explored in subMIP, total elapsed time 555s
Processing user MIP start: 14679 nodes explored in subMIP, total elapsed time 560s
Processing user MIP start: 14912 nodes explored in subMIP, total elapsed time 565s
Processing user MIP start: 15121 nodes explored in subMIP, total elapsed time 570s
User MIP start produced solution with objective 46085.4 (573.19s)
Processing user MIP start: 15322 nodes explored in subMIP, total elapsed time 575s
User MIP start produced solution with objective 45155 (576.00s)
Processing user MIP start: 15417 nodes explored in subMIP, total elapsed time 580s
User MIP start produced solution with objective 45152.5 (584.71s)
Processing user MIP start: 15517 nodes explored in subMIP, total elapsed time 585s
User MIP start produced solution with objective 45150 (589.49s)
Processing user MIP start: 15736 nodes explored in subMIP, total elapsed time 590s
User MIP start produced solution with objective 45093.5 (593.15s)
Processing user MIP start: 15767 nodes explored in subMIP, total elapsed time 595s
User MIP start produced solution with objective 45093.1 (596.64s)
Processing user MIP start: 15894 nodes explored in subMIP, total elapsed time 600s
User MIP start produced solution with objective 45087.9 (601.15s)
User MIP start produced solution with objective 45065.3 (602.13s)
Processing user MIP start: 16005 nodes explored in subMIP, total elapsed time 605s
User MIP start produced solution with objective 45062.6 (606.54s)
Processing user MIP start: 16126 nodes explored in subMIP, total elapsed time 610s
User MIP start produced solution with objective 45060.1 (611.38s)
User MIP start produced solution with objective 45058.8 (613.29s)
User MIP start produced solution with objective 45050.6 (614.98s)
Processing user MIP start: 16273 nodes explored in subMIP, total elapsed time 615s
User MIP start produced solution with objective 45037.7 (615.99s)
User MIP start produced solution with objective 45034.5 (616.82s)
User MIP start produced solution with objective 44995.1 (617.65s)
User MIP start produced solution with objective 44967.6 (618.09s)
User MIP start produced solution with objective 44966.8 (619.43s)
User MIP start produced solution with objective 44966.4 (619.87s)
Processing user MIP start: 16388 nodes explored in subMIP, total elapsed time 620s
User MIP start produced solution with objective 44956.4 (620.87s)
Processing user MIP start: 16473 nodes explored in subMIP, total elapsed time 625s
User MIP start produced solution with objective 44927.6 (626.35s)
Processing user MIP start: 16598 nodes explored in subMIP, total elapsed time 630s
User MIP start produced solution with objective 44925.3 (631.00s)
User MIP start produced solution with objective 44920.2 (632.47s)
User MIP start produced solution with objective 44917.9 (633.50s)
User MIP start produced solution with objective 44917.9 (634.41s)
Processing user MIP start: 16719 nodes explored in subMIP, total elapsed time 635s
Processing user MIP start: 16775 nodes explored in subMIP, total elapsed time 640s
Processing user MIP start: 16879 nodes explored in subMIP, total elapsed time 645s
Processing user MIP start: 16981 nodes explored in subMIP, total elapsed time 650s
Processing user MIP start: 17125 nodes explored in subMIP, total elapsed time 655s
Processing user MIP start: 17297 nodes explored in subMIP, total elapsed time 660s
Processing user MIP start: 17447 nodes explored in subMIP, total elapsed time 665s
Processing user MIP start: 17644 nodes explored in subMIP, total elapsed time 670s
Processing user MIP start: 17702 nodes explored in subMIP, total elapsed time 675s
Processing user MIP start: 17853 nodes explored in subMIP, total elapsed time 680s
Processing user MIP start: 18040 nodes explored in subMIP, total elapsed time 685s
Processing user MIP start: 18265 nodes explored in subMIP, total elapsed time 690s
Processing user MIP start: 18475 nodes explored in subMIP, total elapsed time 695s
Processing user MIP start: 18685 nodes explored in subMIP, total elapsed time 700s
Processing user MIP start: 18775 nodes explored in subMIP, total elapsed time 705s
Processing user MIP start: 18938 nodes explored in subMIP, total elapsed time 710s
Processing user MIP start: 19138 nodes explored in subMIP, total elapsed time 715s
Processing user MIP start: 19346 nodes explored in subMIP, total elapsed time 720s
Processing user MIP start: 19507 nodes explored in subMIP, total elapsed time 725s
Processing user MIP start: 19660 nodes explored in subMIP, total elapsed time 730s
Processing user MIP start: 19884 nodes explored in subMIP, total elapsed time 735s
Processing user MIP start: 20070 nodes explored in subMIP, total elapsed time 740s
Processing user MIP start: 20250 nodes explored in subMIP, total elapsed time 745s
Processing user MIP start: 20416 nodes explored in subMIP, total elapsed time 750s
User MIP start produced solution with objective 44915.4 (750.10s)
Processing user MIP start: 20664 nodes explored in subMIP, total elapsed time 755s
Processing user MIP start: 20873 nodes explored in subMIP, total elapsed time 760s
User MIP start produced solution with objective 44910 (761.13s)
Processing user MIP start: 20993 nodes explored in subMIP, total elapsed time 765s
Processing user MIP start: 21198 nodes explored in subMIP, total elapsed time 770s
Processing user MIP start: 21408 nodes explored in subMIP, total elapsed time 775s
Processing user MIP start: 21624 nodes explored in subMIP, total elapsed time 780s
Processing user MIP start: 21667 nodes explored in subMIP, total elapsed time 785s
Processing user MIP start: 21877 nodes explored in subMIP, total elapsed time 790s
Processing user MIP start: 22064 nodes explored in subMIP, total elapsed time 795s
Processing user MIP start: 22271 nodes explored in subMIP, total elapsed time 800s
Processing user MIP start: 22366 nodes explored in subMIP, total elapsed time 805s
Processing user MIP start: 22577 nodes explored in subMIP, total elapsed time 810s
Processing user MIP start: 22809 nodes explored in subMIP, total elapsed time 815s
Processing user MIP start: 23036 nodes explored in subMIP, total elapsed time 820s
Processing user MIP start: 23305 nodes explored in subMIP, total elapsed time 825s
Processing user MIP start: 23510 nodes explored in subMIP, total elapsed time 830s
Processing user MIP start: 23771 nodes explored in subMIP, total elapsed time 835s
Processing user MIP start: 23934 nodes explored in subMIP, total elapsed time 840s
Processing user MIP start: 24110 nodes explored in subMIP, total elapsed time 845s
Processing user MIP start: 24343 nodes explored in subMIP, total elapsed time 850s
Processing user MIP start: 24533 nodes explored in subMIP, total elapsed time 855s
Processing user MIP start: 24717 nodes explored in subMIP, total elapsed time 860s
Processing user MIP start: 24898 nodes explored in subMIP, total elapsed time 865s
Loaded user MIP start with objective 44910
Processed MIP start in 866.93 seconds (903.55 work units)
Presolve removed 619367 rows and 176965 columns (presolve time = 5s) ...
Presolve removed 648540 rows and 177304 columns (presolve time = 10s) ...
Presolve removed 648540 rows and 177304 columns (presolve time = 15s) ...
Presolve removed 648540 rows and 177304 columns (presolve time = 20s) ...
Presolve removed 648540 rows and 177304 columns (presolve time = 25s) ...
Presolve removed 648540 rows and 177304 columns (presolve time = 74s) ...
Presolve removed 648540 rows and 232338 columns (presolve time = 75s) ...
Presolve removed 648540 rows and 232338 columns (presolve time = 80s) ...
Presolve removed 648540 rows and 232338 columns (presolve time = 92s) ...
Presolve removed 817833 rows and 248460 columns (presolve time = 95s) ...
Presolve removed 817833 rows and 248460 columns (presolve time = 102s) ...
Presolve removed 825603 rows and 251177 columns (presolve time = 105s) ...
Presolve removed 826460 rows and 251430 columns (presolve time = 110s) ...
Presolve removed 826460 rows and 251430 columns (presolve time = 116s) ...
Presolve removed 826589 rows and 253162 columns (presolve time = 120s) ...
Presolve removed 826589 rows and 253162 columns (presolve time = 125s) ...
Presolve removed 826589 rows and 253162 columns (presolve time = 130s) ...
Presolve removed 829675 rows and 253217 columns (presolve time = 135s) ...
Presolve removed 829684 rows and 253218 columns (presolve time = 140s) ...
Presolve removed 829684 rows and 253218 columns (presolve time = 145s) ...
Presolve removed 829933 rows and 253385 columns
Presolve time: 147.35s
Presolved: 452413 rows, 114129 columns, 3106927 nonzeros
Variable types: 29557 continuous, 84572 integer (84564 binary)
Starting NoRel heuristic
Elapsed time for NoRel heuristic: 8s (best bound 5743.92)
Elapsed time for NoRel heuristic: 17s (best bound 8608.08)
Elapsed time for NoRel heuristic: 27s (best bound 9718.05)
Found heuristic solution: objective 44890.010000
Found heuristic solution: objective 44874.610000
Elapsed time for NoRel heuristic: 39s (best bound 10332.8)
Found heuristic solution: objective 44874.470000
Elapsed time for NoRel heuristic: 45s (best bound 10357)
Found heuristic solution: objective 44870.700000
Found heuristic solution: objective 44864.500000
Elapsed time for NoRel heuristic: 51s (best bound 10357)
Found heuristic solution: objective 44857.330000
Found heuristic solution: objective 44821.300000
Found heuristic solution: objective 44814.130000
Found heuristic solution: objective 44811.630000
Found heuristic solution: objective 44787.150000
Found heuristic solution: objective 44781.820000
Elapsed time for NoRel heuristic: 60s (best bound 10785.8)
Found heuristic solution: objective 44776.820000
Found heuristic solution: objective 44729.460000
Found heuristic solution: objective 44720.870000
Found heuristic solution: objective 44679.810000
Elapsed time for NoRel heuristic: 68s (best bound 11137.1)However, it took almost 10 minutes (570 seconds) to establish the first solution, which can be explained by your explanation. In previous versions of my model, it took only a couple of seconds to establish the first new incumbent solution. See the log that I posted here for example. My heuristic hasn't changed in between, so apparently I've changed something else to my model in the meantime, which makes it much more difficult now.
Anyway, I'm going to adjust my heuristic so that I can determine more binary decision variable values. Thanks again!
Best regards,
Koen Timmermans
1 -
Please sign in to leave a comment.
Comments
2 comments