User MIP start did not produce a new incumbent solution/ Another try with MIP start
AnsweredHello all. I'm currently working on a warm start using MIP start. One problem I am having now is that I often get the following message: "User MIP start did not produce a new incumbent solution", "Another try with MIP start".
I also checked questions asked by others and there are two main reasons why I am facing these messages: infeasible initial solution, or the solver having the better solution.
So, I have not got the message like "MIP start violates constraint <name> by <amount>", so I am thinking that my problem is due to the 2nd reason (i.e., the solver already found the better solution).
The thing is, let's say that I give the very very nearoptimal solution to the MIP start. However, I got the message "User MIP start did not produce a new incumbent solution" although my initial guess has a better value of my objective function. The only time I don't get the message is that I give the optimal solution to the solver. So,
1. Why cannot I give a feasible solution with better objective function value?
2. Could you tell me somehow I can force the solver to start optimization from my initial guess?
For your information, I partially give initial guess to continuous variables. I also attached my log file.

Gurobi 9.0.2 (linux64) logging started Sat Sep 12 01:42:41 2020
Changed value of parameter LogFile to test.log
Prev: Default:
Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (linux64)
Optimize a model with 8202 rows, 6000 columns and 22398 nonzeros
Model fingerprint: 0x2f44342a
Model has 57 quadratic objective terms
Model has 23 quadratic constraints
Variable types: 4884 continuous, 1116 integer (1116 binary)
Coefficient statistics:
Matrix range [3e01, 1e+04]
QMatrix range [2e02, 2e+00]
QLMatrix range [1e02, 3e+00]
Objective range [6e+03, 4e+06]
QObjective range [2e+04, 2e+06]
Bounds range [1e+00, 5e+01]
RHS range [6e03, 1e+02]
QRHS range [1e02, 5e+00]
Warning: Completing partial solution with 1116 unfixed noncontinuous variables out of 1116
User MIP start did not produce a new incumbent solution
Presolve removed 5987 rows and 4795 columns
Presolve time: 0.14s
Presolved: 2215 rows, 1205 columns, 7213 nonzeros
Presolved model has 27 quadratic objective terms
Presolved model has 6 quadratic constraint(s)
Variable types: 1005 continuous, 200 integer (200 binary)
Root relaxation: objective 1.855733e08, 2717 iterations, 0.04 seconds
Another try with MIP start
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
0 0 0.00000 0 193  0.00000   0s
0 0 109.65755 0 188  109.65755   0s
0 0 109.65755 0 185  109.65755   0s
0 0 243.11636 0 187  243.11636   0s
0 0 243.11636 0 185  243.11636   0s
0 0 321.78786 0 183  321.78786   0s
0 0 321.78786 0 183  321.78786   0s
0 0 352.97675 0 179  352.97675   0s
0 0 352.97675 0 178  352.97675   0s
0 0 358.66421 0 176  358.66421   0s
0 0 358.66421 0 176  358.66421   0s
0 0 358.66421 0 177  358.66421   0s
0 0 358.66421 0 179  358.66421   0s
0 0 358.66421 0 178  358.66421   0s
0 2 358.66421 0 178  358.66421   0s
H 1625 1351 358.8562886 358.66421 0.05% 30.3 2s
Cutting planes:
Learned: 1
Cover: 8
Implied bound: 24
Projected implied bound: 10
Clique: 14
MIR: 23
Flow cover: 86
RLT: 9
Relaxandlift: 17
Explored 1625 nodes (57137 simplex iterations) in 2.24 seconds
Thread count was 32 (of 32 available processors)
Solution count 1: 358.856
Optimal solution found (tolerance 1.00e01)
Best objective 3.588562886044e+02, best bound 3.586642071950e+02, gap 0.0535%

I look forward to hearing from you
Best

Hi,
The line
User MIP start did not produce a new incumbent solution
means that Gurobi used your initial point, this point is infeasible within the current feasibility tolerance (and integer tolerance) and Gurobi was not able to use it in order to generate a feasible point. In your LOG file, you see that no incumbent is found until the 2 seconds mark, meaning that Gurobi did not have a feasible point up to this point of time. Note that in some cases, even if the initial point you provide is close to the optimal solution point, the solver may "miss" the optimal solution due to heuristic decisions.
If you believe that the initial point you are giving to Gurobi is feasible, you could fix all variable bounds to the value of the starting point and see that Gurobi declares the problem as infeasible. You can then construct a feasibility relaxation of your problem and solve it to see which constraint is not satisfied by the solution you provide.
Best regards,
Jaromił1 
Hi,
I am experiencing a similar problem. I am trying to give the MIP solver an initial incumbent solution using the Start attribute for every binary and integer variable of the model. However, I get the message “User MIP start did not produce a new incumbent solution”. From the documentation I understand one possible explanation is that Gurobi’s primal heuristics find a better primal solution, but in this case the solver hasn’t found any incumbent solution when starting to branch (or even after several minutes of branching).
The second option is that the provided solution is infeasible. To verify that the solution in fact is feasible I fixed all binary and integer variables via the LB and UB variable attributes. Then it is solved to optimality in the root node verifying that the solution is in fact feasible. Since it is solved in the root node I don’t think the issue comes from the default value of StartNodeLimit of 500 to be too low either. I tried setting this to 1 000 000, but still having the same problem. I also tried to set the bounds LB and UB back to their original values and reoptimize the model. Then I get the following message: “MIP start from previous solve did not produce a new incumbent solution” . Also for this run the Gurobi heuristics do not provide any incumbent solution.
Finally, I suspected there might be some numerical issues as I have other instances where I successfully manage to set a starting incumbent (either by getting the exact solution I provide, or an improved solution found by the Gurobi heuristics). I have tried to set both the IntFeasTol and the FeasibilityTol parameters to their maximum values, i.e. 0.1 and 0.01, respectively. Even with very loose tolerances regarding feasibility and integer requirements I get the same messages. Both when setting the Start attribute, and when fixing the solution with the LB and UB attributes solving the MIP, setting the bounds back to original values and reoptimizing.
Does anyone have any idea of what I am doing wrong? Any help would be highly appreciated.
Best regards,
Jørgen
0 
Hi Jørgen,
To verify that the solution in fact is feasible I fixed all binary and integer variables via the LB and UB variable attributes. Then it is solved to optimality in the root node verifying that the solution is in fact feasible. Since it is solved in the root node I don’t think the issue comes from the default value of StartNodeLimit of 500 to be too low either. I tried setting this to 1 000 000, but still having the same problem. I also tried to set the bounds LB and UB back to their original values and reoptimize the model. Then I get the following message: “MIP start from previous solve did not produce a new incumbent solution” . Also for this run the Gurobi heuristics do not provide any incumbent solution.
Please note that by fixing the integer and binary variable to some value, Gurobi has a completely different problem at hand since the presolving reductions may result in a way smaller and easier problem. This is not the case when you provide the MIPstart solution to the nonfixed model, because many presolve reduction may not be possible due to the missing fixings. Did you try solving the fixed model and providing this solution as MIPstart solution? In the case that it is not accepted, could you provide a log file and a model file to make the issue reproducible? Please refer to Posting to the Community Forum for information on providing files in the Forum.
Finally, I suspected there might be some numerical issues as I have other instances where I successfully manage to set a starting incumbent (either by getting the exact solution I provide, or an improved solution found by the Gurobi heuristics).
Does any of the cases in Does my model have numerical issues? apply to your problem? Please post a log file for better investigation.
Best regards,
Jaromił0 
Hi Jaromił,
Thank you for the quick reply.Please note that by fixing the integer and binary variable to some value, Gurobi has a completely different problem at hand since the presolving reductions may result in a way smaller and easier problem. This is not the case when you provide the MIPstart solution to the nonfixed model, because many presolve reduction may not be possible due to the missing fixings.
It might be something here I have misunderstood, but I assumed that when providing the full integer/binary vector, Gurobi only needs to solve a LP to find the feasible solution. I have not tried to fix all the continuous variables as well, because doing so I expect the chances of running into numerical issues to be greater.
Did you try solving the fixed model and providing this solution as MIPstart solution? In the case that it is not accepted, could you provide a log file and a model file to make the issue reproducible?
Yes, I tried this now, with the same results. See the mps. files and log files in the following link: https://drive.google.com/drive/folders/1odDL0XLtBHytA3R_zDU1rAAdrcVJXdwe?usp=sharing
First I run the fixed model ('fixedModel'), where all integer and binary variables are fixed via the UB and LB variable attributes. Then the variable bounds are set back to their original values, and in one run I simply reoptimized ('unFixedModel') and in another run I set the MIPstart solution before reoptimizing ('unFixedWithStartModel').
Does any of the cases in Does my model have numerical issues? apply to your problem? Please post a log file for better investigation.
I don't think they apply to my problem, as the largest matrix coefficient range is in the magnitude 10^5. See the log files in the link for more details. Please let me know in case you cannot get access to the mentioned files.
Best regards,
Jørgen
0 
Hi Jørgen,
Could you show how you write and read the solution/initial point? I just tried your model with the following commands:
>gurobi_cl ResultFile=solution_fixed.sol fixedModel.mps
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (mac64)
Copyright (c) 2021, Gurobi Optimization, LLC
Read MPS format model from file fixedModel.mps
Reading time = 0.11 seconds
(null): 20417 rows, 6163 columns, 412880 nonzeros
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 20417 rows, 6163 columns and 412880 nonzeros
Model fingerprint: 0xd893ed33
Variable types: 397 continuous, 5766 integer (5760 binary)
Coefficient statistics:
Matrix range [3e03, 6e+02]
Objective range [1e01, 6e+02]
Bounds range [1e+00, 3e+02]
RHS range [1e+00, 5e+03]
Presolve removed 20393 rows and 6124 columns
Presolve time: 0.07s
Presolved: 24 rows, 39 columns, 198 nonzeros
Variable types: 39 continuous, 0 integer (0 binary)
Root relaxation: objective 2.839470e+04, 22 iterations, 0.00 seconds
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time
* 0 0 0 28394.700000 28394.7000 0.00%  0s
Explored 0 nodes (22 simplex iterations) in 0.09 seconds
Thread count was 8 (of 8 available processors)
Solution count 1: 28394.7
Optimal solution found (tolerance 1.00e04)
Best objective 2.839470000000e+04, best bound 2.839470000000e+04, gap 0.0000%
Wrote result file 'solution_fixed.sol'I then provided the written solution file as initial point to the solver via
gurobi_cl InputFile=solution_fixed.sol unFixedModel.mps
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (mac64)
Copyright (c) 2021, Gurobi Optimization, LLC
Read MPS format model from file unFixedModel.mps
Reading time = 0.11 seconds
(null): 20417 rows, 6163 columns, 412880 nonzeros
Read input file 'solution_fixed.sol'
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 20417 rows, 6163 columns and 412880 nonzeros
Model fingerprint: 0x895f3eb0
Variable types: 397 continuous, 5766 integer (5760 binary)
Coefficient statistics:
Matrix range [3e03, 6e+02]
Objective range [1e01, 6e+02]
Bounds range [1e+00, 3e+02]
RHS range [1e+00, 5e+03]
Loaded user MIP start with objective 28394.7
[...]So, you can see that the MIP start solution is correctly used. Could you try saving the solution values and explicitly setting the variables' Start attribute? It is possible that the model changes you apply somehow affect the solution point stored from a previous run.
Best regards,
Jaromił0 
Hi,
Thank you Jaromił! I did not think to run this from the commandline interface, but when I do I get the same results as you do. This helped me to focus on the right place. The problem seems to arise when I add lazy constraints via my callback routine. It turns out that when I only fixed the binary/integer vector via the Start attribute, Gurobi initially finds a solution that violates some lazy constraints. When I then call my callback routine the added lazy constraints cut off the current solution, and here it looks like the MIP Start procedure somehow gives up and the MIP solver starts branching without an initial incumbent solution. However, if I in addition to the binary/integer vector also gives the vector of continuous variables, Gurobi finds the incumbent solution that does not violate any lazy constraints and successfully sets an initial incumbent.Could you show how you write and read the solution/initial point?
I am reading the solution from my own file format, so I do not think it will make much sense for others to show the whole code, but the general idea is that I set all variables to zero within a block of forloops with the command:
x[tailNode][headNode][t].set(GRB_DoubleAttr_Start, 0.0);
And for every nonzero binary variable I update the Start attribute (the integer and continuous variables are updated with their corresponding value if they are nonzero):
x[tailNode][headNode][t].set(GRB_DoubleAttr_Start, 1.0);
Even though it now works to set a starting incumbent solution via the Start attribute I do not understand why it fails to obtain an incumbent solution when reoptimizing the "fixed model with callbacks" when setting the variable bounds back to their orginial values. Does changing the variable bounds via the LB and UB attributes discard some solution information? If not, I might not have found the correct solution for this problem, as both methods should return an incumbent solution unless some information is discarded when changing the variable bounds.
Thanks again for you help!
Best regards,
Jørgen
0 
Hi Jørgen,
One way of how Gurobi uses the partial MIP start is that it fixes the integer/binary variables to its MIP start values and solves a feasibility problem. When your lazy constraints make the initial integer variables infeasible, then it makes sense that Gurobi does not accept your initial point. This makes Gurobi terminate the MIP start procedure and proceed with the optimization process. If, in contrast, you provide a full initial point, then different MIP start heuristics are active and Gurobi is able to construct a feasible point despite the lazy constraints.
Even though it now works to set a starting incumbent solution via the Start attribute I do not understand why it fails to obtain an incumbent solution when reoptimizing the "fixed model with callbacks" when setting the variable bounds back to their orginial values. Does changing the variable bounds via the LB and UB attributes discard some solution information? If not, I might not have found the correct solution for this problem, as both methods should return an incumbent solution unless some information is discarded when changing the variable bounds.
Just for a better understanding. You solve model A to optimality where you fix some of the variable bounds by settings it LB and UB attributes. You then loosen the LB and UB of these variables to obtain model B and reoptimize. This then does not use the previous solution point as a feasible MIP start and provides a different optimal solution? Does model A or B have lazy constraints? If model B has lazy constraints and model A doesn't then it is fairly possible that some of the lazy constraints in B may cut of the solution of A. In general, just changing variable bounds should not discard any optimization information.
Best regards,
Jaromił0 
Hi Jaromił,
I see my description could have been better. To clarify:
When your lazy constraints make the initial integer variables infeasible, then it makes sense that Gurobi does not accept your initial point.
The lazy constraints do not cut off the integer solution, but make the vector of continuous variables infeasible. This is why I thought Gurobi would resolve the feasibility problem with the added lazy constraints as the integer point remains the same, but this does not seem to be the case.
Just for a better understanding. You solve model A to optimality where you fix some of the variable bounds by settings it LB and UB attributes. You then loosen the LB and UB of these variables to obtain model B and reoptimize. This then does not use the previous solution point as a feasible MIP start and provides a different optimal solution? Does model A or B have lazy constraints? If model B has lazy constraints and model A doesn't then it is fairly possible that some of the lazy constraints in B may cut of the solution of A. In general, just changing variable bounds should not discard any optimization information.
Your description is mostly correct except for a few details. I solve model A to optimality where all binary and integer variables are fixed by setting the LB and UB attributes to be equal for the same variable (the continuous variables are left with their origninal bounds, i.e. LB < UB). Both A and B have the same set of lazy constraints. The solution of A is the exact same solution I originially wanted to intitialize B with, so so far it works as expected. However, when I relax the variable bounds LB and UB back to their original values obtaining the model B and reoptimize, I get the message: "MIP start from previous solve did not produce a new incumbent solution". Here I would expect Gurobi to be able to use the solution from model A, as the only change is setting the variable bounds back to their original values.
As far as I understand, either providing a solution C by using the Start attribute, or first solving a fixed model (in this case model A) to obtain the same solution C, should both provide model B with an initial incumbent solution. After some more debugging I discovered that the five lazy constraints added to model A seems to be discarded before reoptimizing model B, as the exact same five constraints are added once more for model B. After these five lazy constraints are added Gurobi prints the message "MIP start from previous solve did not produce a new incumbent solution". Is it possible that the MIP Start procedure in model B only includes the integer point, solves the feasibility problem and finds a solution violated by the lazy constraints? Since the lazy constraints added to model A seems to be discarded, they are added once more in model B making the suggested solution from the feasibility problem infeasible and the MIP Start procedure then terminates?
Best regards,
Jørgen
0 
This issue has been discussed in an internal ticket.
We assume that if a lazy constraint is added through the callback when the MIP start is passed to the optimizer, it is because the MIP start violates some of the lazy constraints. If you want the MIP start to be accepted, you'll need to avoid adding lazy constraints that don't cut it off. This results in the MIP start not being accepted even thou it does not violate any of the lazy constraints. (For now,) we recommend to only add lazy constraints if they actually cut off the MIP start solution.
This case is on our future roadmap and will be improved in a future release.
A possible workaround would be to use variable hints.
0 
Hello all! I have the same question. I prepared an MIP Start Solution using a heuristic approach. In shorter instances, the MIP Start works well and I get a feasible solution. However, in bigger instances, I receive the message "User MIP start did not produce a new incumbent solution". I tried to change the StartNodeLimit (I use 200000), but the model didn't produce a feasible solution at all. Is there any suggestion to help me to solve this?
0 
Hi Lucia,
Could you post short LOG snippets presenting your issue? Are you using lazy constraints? Are you reoptimizing a model or are you reading the initial point from a file?
Best regards,
Jaromił0 
Dear Jaromił,
First, I prepared a partial MIP Start using a constructive heuristic.Then, I used the .mst on the model. It took a long time.
The model accepted the MIP Start and found a feasible solution in small instances tested.In the higher instances tested, the result was:
Running...
Time: 1621258852.794981
Changed value of parameter mipGap to 0.01
Prev: 0.0001 Min: 0.0 Max: inf Default: 0.0001
Changed value of parameter TIME_LIMIT to 5000.0
Prev: inf Min: 0.0 Max: inf Default: inf
Changed value of parameter LogFile to m_15_174.log
Prev: Default:
Changed value of parameter StartNodeLimit to 200000
Prev: 1 Min: 2 Max: 2000000000 Default: 1
Li o modelo, vou chamar a heurística 1621260795.445624
Read MIP start from file arq_15_174_1_2000.mst
Heurística rodou em 0.05671286582946777 segundos
Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (mac64)
Optimize a model with 1072208 rows, 97077 columns and 5777634 nonzeros
Model fingerprint: 0x2ac185e7
Variable types: 271 continuous, 96806 integer (96806 binary)
Coefficient statistics:
Matrix range [1e02, 1e+06]
Objective range [4e+04, 2e+05]
Bounds range [1e+00, 2e+03]
RHS range [1e+00, 1e+04]Warning: Completing partial solution with 96632 unfixed noncontinuous variables out of 96806
User MIP start did not produce a new incumbent solution
Processed MIP start in 5000.28 secondsPresolve time: 0.48s
Explored 0 nodes (0 simplex iterations) in 5002.26 seconds
Thread count was 1 (of 4 available processors)Solution count 0
Time limit reached
Best objective , best bound , gap Usercallback calls 264100, time in usercallback 7.89 sec
I also used the following callback routine in an attempt to help the model:
def callback(model, where):
if where == GRB.Callback.MIPSOL:
if model.cbGet(GRB.Callback.MIPSOL_SOLCNT) == 0:
# creates new model attribute '_startobjval'
model._startobjval = model.cbGet(GRB.Callback.MIPSOL_OBJ)Best regards,
Lucia
0 
Dear Lucia,
The MIP start procedure did not finish because it hit the time limit of 5000 seconds. It seems like the MIP start model is still very hard to solve despite the initial values you provided. It looks like you provided an initial value only for a small part of the optimization variable as >96k variables are still unfixed.
If it is acceptable for you to spend that much time in trying to generate a feasible solution out of the partial initial point you provide, it might be best to solve a separate optimization problem where you fix the variables to the initial point values you computed with your heuristic. You can then either write the computed solution to a file or directly proceed with it though API calls.
Did you try solving the problem without providing an initial solution? Did you try the no relaxation heuristic?
You should also upgrade to the latest Gurobi version.
Best regards,
Jaromił0 
Hello Jaromił,
I'm encountering the same issue of getting the message "User MIP start did not produce a new incumbent solution". Could you suggest to me where I look at to debug?
I have set the lower and upper bound of binary variables so that these binary variables should be fixed to 0 and 1. Still, I'm getting the "not producing a new incumbent solution message". Below is the output of a log file:
Gurobi Optimizer version 9.1.2 build v9.1.2rc0 (linux64)
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 163 rows, 162 columns and 402 nonzeros
Model fingerprint: 0x5bf13ba8
Variable types: 82 continuous, 80 integer (80 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+02]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 7e+03]
RHS range [1e+01, 2e+01]User MIP start did not produce a new incumbent solution
Presolve removed 163 rows and 145 columns
Presolve time: 0.00s
Presolved: 0 rows, 17 columns, 0 nonzeros
Variable types: 17 continuous, 0 integer (0 binary)Root relaxation: objective 0.000000e+00, 0 iterations, 0.00 seconds
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time* 0 0 0 6220.0304365 6220.03044 0.00%  0s
Cutting planes:
Lazy constraints: 1Explored 0 nodes (1 simplex iterations) in 0.95 seconds
Thread count was 12 (of 12 available processors)Solution count 1: 6220.03
Optimal solution found (tolerance 1.00e02)
Best objective 6.220030436453e+03, best bound 6.220030436453e+03, gap 0.0000%Usercallback calls 59, time in usercallback 0.98 sec
0 
Hi,
Could you try adding the lazy constraints as normal constraints (if they are not too many)?
As mentioned above, lazy constraints and MIP starts are a bit tricky
We assume that if a lazy constraint is added through the callback when the MIP start is passed to the optimizer, it is because the MIP start violates some of the lazy constraints. If you want the MIP start to be accepted, you'll need to avoid adding lazy constraints that don't cut it off. This results in the MIP start not being accepted even thou it does not violate any of the lazy constraints. (For now,) we recommend to only add lazy constraints if they actually cut off the MIP start solution.
Best regards,
Jaromił0 
Dear all,
was the abovementioned issue with MIPs starts and lazy constraints solved in Gurobi 9.5?
Best regards
Mike
0 
Hi Mike,
The behavior discussed in this thread did not change for v9.5.
Best regards,
Jaromił0 
Hi Jaromil,
ok, thank you for the swift reply.
Best regards
Mike
0
Please sign in to leave a comment.
Comments
18 comments