Skip to main content

Why is Gurobi returning MIP solution with gap of 0 which is not close to the actual optimal solution?

Ongoing

Comments

16 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Steven,

    Could you use the gurobi_write() function to write 2 LP files (one with SET_SOME_VARS=0 and the other with =1) and upload those? This would make helping you easier.

    Best regards,
    Jaromił

    0
  • Steven Shechter
    Gurobi-versary
    Conversationalist
    First Question

    Thank you, Jaromil. I don't see how to upload a file, but here are links to google docs with the .lp outputs.  These are long files, but I ran a "compare" of these in Word and confirmed that the only differences between the files are that the first one explicitly forces the integer variables to take on specific pre-set values (shown in the "differences" doc.

    when setting SET_SOME_VARS <- 1:

    https://docs.google.com/document/d/1mqcMFi2QFqCijP7YY6mSOSGvVhA6hzBH3WZ3U3AmTlw/edit?usp=sharing 

    when setting SET_SOME_VARS <- 0:

    https://docs.google.com/document/d/1hjtd7vec5-Tka0uu10cCcPphxpy8Z2S2ZLBIxP-k5pI/edit?usp=sharing 

    The differences between these two files results in:

    https://docs.google.com/document/d/1hjtd7vec5-Tka0uu10cCcPphxpy8Z2S2ZLBIxP-k5pI/edit 

     

    0
  • 0
  • Eli Towle
    Gurobi Staff Gurobi Staff

    I observed a few cases of incorrect solutions with Gurobi 9.1.0-9.1.2, similar to what you described. However, I couldn't replicate this behavior with Gurobi 9.5.0. Which version of Gurobi are you using? Could you please post the log output printed by Gurobi when \( \texttt{SET_SOME_VARS} \) equals \( 0 \)?

    0
  • Steven Shechter
    Gurobi-versary
    Conversationalist
    First Question

    Thank you, Eli!  That did the trick.  I was using version 9.1.2.  The problem no longer appears after I updated to version 9.5.0.  Was the problem in 9.1.2 related to my model's use of non-convex quadratic constraints?

    thanks again!

     

     

    0
  • Eli Towle
    Gurobi Staff Gurobi Staff

    That's great to hear! Yes, your intuition is correct - the problem in Gurobi 9.1.2 was related to the non-convex quadratic constraints.

    0
  • Steven Shechter
    Gurobi-versary
    Conversationalist
    First Question

    Hi Eli,

    I'm actually running into similar problems again as described above, even for the 9.5.0 version of Gurobi.

    Same situation, where the "optimal" solution returned by Gurobi is worse (by two orders of magnitude) than another feasible solution obtained after fixing several decision variables.  I set MIPGap to 0 in both cases (and the log files show the problems terminating with gap 0.0000%).  These are also again occurring in a non-convex quadratically constrained problem.

    The log files are here:

    Solution without pre-fixing decision vars:

    https://docs.google.com/document/d/1kvomcFwnFLMfersRXSxGOytictNTzAi6yP_KobUh-Fk/edit?usp=sharing

    Objective value (for a minimization problem): 85.7

     

    Solution with pre-fixing several decision vars:

    https://docs.google.com/document/d/1s0y34J8LFw9OtuL2-oPOXKsCFbUX1NAw9uG2Dx5euOc/edit?usp=sharing 

    Objective value: 0.408

     

    thanks in advance for any insights you may have on this!

    best,

    Steven

     

     

     

    0
  • Eli Towle
    Gurobi Staff Gurobi Staff

    Could you post a link to MPS model files for the two models that produce these different results? You can create these model files using the gurobi_write() function, as you did before. Thanks!

    0
  • Steven Shechter
    Gurobi-versary
    Conversationalist
    First Question

    Sure.

    The MPS file for the version that fixes the 48 integer variables at pre-determined values is here: 

    https://drive.google.com/file/d/1DJKiieKbyhwBoda0LBkumJAXZiEQC5su/view?usp=sharing 

    and the MPS file that does not fix the 48 integer variables is here:

    https://drive.google.com/file/d/1sAeDBgz--LawVRphs267yba7pj4izQ3H/view?usp=sharing 

    thanks again for having a look!

    Steven

     

    0
  • Steven Shechter
    Gurobi-versary
    Conversationalist
    First Question

    Hi Eli,

    I just wanted to follow up on this and see if you were able to find out what the issue might be?  

    Thank you!

    Steven

    0
  • Eli Towle
    Gurobi Staff Gurobi Staff

    Sorry, Steven. I completely missed your previous post.

    I could reproduce the issue with Gurobi 9.5.1. I will open a ticket in our support portal so we can investigate this further. Thanks!

    0
  • Chung-Yi Lin
    First Comment

    I have the same issue with Gurobi 10.0.1. 
    The solver shows a gap = 0%, but the solution is not optimal.
    I am sure the solution is not optimal by fixing the following variables 

    f1.irr[0,2,0] 50
    f1.irr[0,2,1] 60

    f1.i_area[0,0,0] 0
    f1.i_area[0,1,0] 0
    f1.i_area[0,2,0] 1
    f1.i_area[0,3,0] 0

    and the model returns a better objective value.

    I provide the corresponding .lp, .mps, and .sol here.
    https://1drv.ms/f/s!AvYlq7fSX1V1oZBXHyrg58LqTyNcVQ?e=Rdxl22
    Example_org is the model that produces a non-optimal solution while claiming gap = 0.
    Example_fix_decision_variables_irr is the one I fixed the above variables and got a better (higher) objective with also gap = 0.

    Please let me know how I can move forward to solve the issue.

     

     

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    When running model Example_fix_decision_variables_irr.lp, you should see that Gurobi prints a warning at the end of the solution process

    Optimal solution found (tolerance 1.00e-04)
    Warning: max constraint violation (1.2500e-01) exceeds tolerance
             (model may be infeasible or unbounded - try turning presolve off)
    Best objective 3.255595416759e-02, best bound 3.255595416759e-02, gap 0.0000%

    When you run model Example_fix_decision_variables_irr.lp with Presolve=0, Gurobi declares the model to be infeasible. From here, you can proceed as described in the Knowledge Base article How do I determine why my model is infeasible?

    0
  • Martina Gherardi
    Conversationalist
    Gurobi-versary
    First Question

    Hi, I am facing a similar issue with Gurobi 10.0.1.

    By considering a minimization problem, I observed the following solutions: 

    • 1) with MIPGap=1%, in 21 seconds I found a solution with gap=0.9898% and objective= 70,390,180.4
    • 2) with MIPGap=0, in 352 seconds I found a solution, with gap=0.0000% and objective = 70,605,324.2

    (Note that in the 2nd case there is no warning about constraint violation).

    How is this possible? Could the use of Heuristics=1 cause this result?

    By removing Heuristics=1,

    • 3) with MIPGap=0 and TimeLimit=353, I found a solution with gap =0.7871% and objective= 70,251,694.8

     

    Here are the logs: 

    https://drive.google.com/drive/folders/1zHyxZCaYJ1DEWSFZCrjejB3V6g5Vb8yR?usp=sharing

     

    Thank you in advance for the help,

    Martina

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Martina,

    How is this possible? Could the use of Heuristics=1 cause this result?

    The Heuristics parameter should not have any effect on the final best bound.

    Just from the logs I cannot tell what is going wrong. This may be a numerical issue and you might want to experiment with the NumericFocus parameter. It looks like you do not provide bounds for your variables. Could you try providing finite (and in best case tight) bounds for all variables participating in bilinear terms? It is possible that the unboundedness of bilinear terms is causing some numerical trouble. However, I am only guessing here.

    Could you please share this particular model so I can have a closer look?

    Best regards, 
    Jaromił

    0
  • Martina Gherardi
    Conversationalist
    Gurobi-versary
    First Question

    Hi Jaromił, 

    thank you for your answer. 

    I set the bounds to the variables participating in bilinear terms by adding additional constraints to the model. Can you suggest a better way to provide these bounds? 

    The only way I can share the code with you is to send it under confidentiality to your private e-mail because it is part of my doctoral work and I have yet to publish it. Is it possible to proceed in this way?

    Best regards, 

    Martina

     

     

    0

Please sign in to leave a comment.