Skip to main content

User MIP start did not produce a new incumbent solution/ Another try with MIP start

Answered

Comments

21 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
  • Jørgen Skålnes
    Gurobi-versary
    First Question
    Conversationalist

    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 re-optimize 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 re-optimizing.

    Does anyone have any idea of what I am doing wrong? Any help would be highly appreciated.

    Best regards,

    Jørgen

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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 re-optimize 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 non-fixed 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
  • Jørgen Skålnes
    Gurobi-versary
    First Question
    Conversationalist

    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 non-fixed 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 re-optimized ('unFixedModel') and in another run I set the MIPstart solution before re-optimizing ('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
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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 [3e-03, 6e+02]
    Objective range [1e-01, 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.00e-04)
    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 [3e-03, 6e+02]
    Objective range [1e-01, 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
  • Jørgen Skålnes
    Gurobi-versary
    First Question
    Conversationalist

    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 for-loops with the command:

    x[tailNode][headNode][t].set(GRB_DoubleAttr_Start, 0.0);

    And for every non-zero binary variable I update the Start attribute (the integer and continuous variables are updated with their corresponding value if they are non-zero):

    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 re-optimizing 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
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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 re-optimizing 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 re-optimize. 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
  • Jørgen Skålnes
    Gurobi-versary
    First Question
    Conversationalist

    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 re-optimize. 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 re-optimize, 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 re-optimizing 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
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
  • Lucia Logsdon
    Gurobi-versary
    First Question
    First Comment

    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
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Lucia,

    Could you post short LOG snippets presenting your issue? Are you using lazy constraints? Are you re-optimizing a model or are you reading the initial point from a file?

    Best regards,
    Jaromił

    0
  • Lucia Logsdon
    Gurobi-versary
    First Question
    First Comment

    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 [1e-02, 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 non-continuous variables out of 96806
    User MIP start did not produce a new incumbent solution
    Processed MIP start in 5000.28 seconds

    Presolve 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 -

    User-callback calls 264100, time in user-callback 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
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
  • Jiachang Liu
    Gurobi-versary
    First Comment

    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: 1

    Explored 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.00e-02)
    Best objective 6.220030436453e+03, best bound 6.220030436453e+03, gap 0.0000%

    User-callback calls 59, time in user-callback 0.98 sec

     

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
  • Mike Lang
    Gurobi-versary
    Conversationalist
    First Question

    Dear all, 

    was the above-mentioned issue with MIPs starts and lazy constraints solved in Gurobi 9.5?

    Best regards

    Mike

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Mike,

    The behavior discussed in this thread did not change for v9.5.

    Best regards,
    Jaromił

    0
  • Mike Lang
    Gurobi-versary
    Conversationalist
    First Question

    Hi Jaromil, 

    ok, thank you for the swift reply. 

    Best regards

    Mike

    0
  • Madhushini Narayana Prasad
    Gurobi-versary
    Conversationalist
    First Question

    Hi Team,

    I have a related question about Start solution. Are there attributes to extract the information on whether the MIP start were able to produce an incumbent solution or not? I am thinking of displaying it in my output console rather checking the log manually every time.

    0
  • Riley Clement
    Gurobi Staff Gurobi Staff

    Hi Madhushini,

    I don't believe there are such attributes however you could use callbacks to filter the relevant messages.

    For example in Python:

    m = gp.Model()

    # build model

    def callback(model, where):
        if where == gp.GRB.Callback.MESSAGE:
            msg = model.cbGet(gp.GRB.Callback.MSG_STRING)
            if "MIP start" in msg:
                print(msg)

    m.params.OutputFlag=0

    m.optimize(callback)

    For other APIs see the callback examples at the bottom of the following page:
    A list of the Gurobi examples 

    - Riley

    0
  • Madhushini Narayana Prasad
    Gurobi-versary
    Conversationalist
    First Question

    Thank you so much for your prompt response Riley.

    0

Please sign in to leave a comment.