Skip to main content

Order of constraints affects solution optimality; Code returns suboptimal solution

Ongoing
Tamal Das
Gurobi-versary
First Comment
First Question

Hi,

I'm facing two problems with my gurobi code in Python (in Eclipse).

1. The order of constraints affects the solution. If I change the order in which I define my constraints, the solver returns different (suboptimal) solutions.

2. Code returns sub-optimal solution, even though the optimal solution is feasible (I verified this by setting the optimal solution while defining the variables).

Please advise.

Thanks,
Tamal.

1

Comments

13 comments

Date Votes
  • Official comment
    Simranjit Kaur
    Gurobi Staff Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Silke Horn
    Gurobi Staff Gurobi Staff

    The order of the constraints or variables may affect the solver path and hence the solution that is returned by the solver. So this is expected behavior. The solutions that are returned should, however, be optimal (within tolerances) unless you set a termination criterion (such as a time limit). Do you use such a termination criterion?

    What do you mean by "setting the optimal solution while defining the variables"? Are you setting a MIP start?

    Best regards,
    Silke

    0
  • Tamal Das
    Gurobi-versary
    First Comment
    First Question

    Thanks Silke for your prompt response.

    Yes, I understand that the order of constraints may affect the performance, but should not affect the optimality in any case. I'm not using any termination condition, and didn't change default values for tolerances.

    For one particular choice of input parameters, I was getting a sub-optimal solution. Hence, to verify whether the optimal solution lies within the feasible region of my model, I set the decision variable values as corresponding to the optimal solution, and executed the code. Had the outcome been infeasible, it would have meant that the optimal solution is somehow not part of the feasible region due to some modeling errors. But that's not the case either. The code executes fine with the optimal solution as input, and returns the same manually input optimal solution. Hence, all the more surprising - how come Gurobi doesn't return the optimal solution, despite it being in the feasible region!!

    0
  • Silke Horn
    Gurobi Staff Gurobi Staff

    So you are saying that you know (by some independent way) a solution to your model that is better than the solutions that Gurobi finds (and outputs as optimal)?

    I still don't fully understand how you set the values of the variables. Did you set the upper and lower bounds to equal the values in your known solution? How did you obtain your known optimal solution?

    0
  • Greg Glockner
    Gurobi Staff Gurobi Staff

    Can you post the first and last ~30 lines of the logs from both versions?

    0
  • Tamal Das
    • Edited
    Gurobi-versary
    First Comment
    First Question

    Hi Silke,

    Yes, I know the optimal solution by manually working it out for a simple case. And as you guessed it, I set the upper and lower bounds of the decision variables equal to the values in my known (optimal) solution for test purpose.

    You can view my code here: https://www.dropbox.com/s/45kdam5gc1enl9n/for%20support%20purpose.py?dl=0

    Hi Greg,

    Here are the logs from both runs.

    ===============LOG WITH USUAL RUN===============

    Optimize a model with 1892 rows, 991 columns and 6165 nonzeros
    Variable types: 0 continuous, 991 integer (991 binary)
    Coefficient statistics:
    Matrix range [5e-01, 6e+02]
    Objective range [1e-07, 1e-06]
    Bounds range [1e+00, 1e+00]
    RHS range [1e+00, 1e+03]
    Presolve removed 510 rows and 43 columns
    Presolve time: 0.03s
    Presolved: 1382 rows, 948 columns, 4718 nonzeros
    Variable types: 0 continuous, 948 integer (948 binary)

    Root relaxation: objective 3.484169e-07, 276 iterations, 0.00 seconds

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

    0 0 0.00000 0 95 - 0.00000 - - 0s
    0 0 0.00000 0 79 - 0.00000 - - 0s
    H 0 0 0.0000058 0.00000 85.7% - 0s
    H 0 0 0.0000020 0.00000 58.9% - 0s
    0 0 0.00000 0 58 0.00000 0.00000 44.2% - 0s

    Cutting planes:
    Gomory: 3
    Cover: 16
    Implied bound: 2
    Clique: 22
    Zero half: 2

    Explored 1 nodes (457 simplex iterations) in 0.14 seconds
    Thread count was 12 (of 12 available processors)

    Solution count 2: 1.999e-06 5.75969e-06

    Optimal solution found (tolerance 1.00e-04)
    Best objective 1.998998410569e-06, best bound 1.998998410569e-06, gap 0.0000%

    ===============LOG WITH DECISION VARIABLES SET TO OPTIMAL SOLUTION===============

    Optimize a model with 1892 rows, 991 columns and 6165 nonzeros
    Variable types: 0 continuous, 991 integer (991 binary)
    Coefficient statistics:
    Matrix range [5e-01, 6e+02]
    Objective range [1e-07, 1e-06]
    Bounds range [1e+00, 1e+00]
    RHS range [1e+00, 1e+03]
    Presolve removed 1871 rows and 946 columns
    Presolve time: 0.00s
    Presolved: 21 rows, 45 columns, 135 nonzeros
    Variable types: 0 continuous, 45 integer (45 binary)

    Root relaxation: objective 2.861364e-07, 18 iterations, 0.00 seconds

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

    0 0 0.00000 0 4 - 0.00000 - - 0s
    0 0 0.00000 0 8 - 0.00000 - - 0s
    0 0 0.00000 0 6 - 0.00000 - - 0s
    H 0 0 0.0000003 0.00000 0.00% - 0s
    0 0 0.00000 0 6 0.00000 0.00000 0.00% - 0s

    Cutting planes:
    Cover: 3
    MIR: 2
    StrongCG: 1

    Explored 1 nodes (49 simplex iterations) in 0.02 seconds
    Thread count was 12 (of 12 available processors)

    Solution count 1: 2.86136e-07

    Optimal solution found (tolerance 1.00e-04)
    Best objective 2.861364498984e-07, best bound 2.861364498984e-07, gap 0.0000%

    Thanks,
    Tamal.

    0
  • Silke Horn
    Gurobi Staff Gurobi Staff

    Hi Tamal,

    Thanks for the information and for sharing your logs.

    It seems that all of your objective coefficients are very small (between 1e-7 and 1e-6) and as you can see from the logs both best objectives are way smaller than the tolerance.

    Could you try scaling up your objective function (say by a factor of 1e6)?

    I also looked at your code, but I cannot test it since I am missing the imports.

    Thanks,

    Silke

    1
  • Tamal Das
    Gurobi-versary
    First Comment
    First Question

    Dear Silke,

    Your feedback was spot on! The low coefficient values were indeed the problem. Upscaling the objective function resolved this. Can you please point me to the relevant Gurobi documentation about numerical tolerance limit, etc.?

    Thank you so much!

    Regards,
    Tamal.

    0
  • Silke Horn
    Gurobi Staff Gurobi Staff

    Dear Tamal,

    I am glad this helped.

    You can find some more information about numerics and tolerances here: https://www.gurobi.com/documentation/8.1/refman/numerics_gurobi_guidelines.html

    Regards,

    Silke

    0
  • Tamal Das
    Gurobi-versary
    First Comment
    First Question

    Thanks a lot!

    0
  • Kai WANG
    Gurobi-versary
    First Comment

    The issue still exists!

    Check the code at

    https://github.com/kevinkitty7/gurobi_bug

     

    Gurobi fails to give optimal, order of constraints affects solution optimality. Tested for Gurobi 8.1.1, Gurobi 9.1.2.

    bug 1. with different order of constraints, gurobi gives solutions of different objective value.

    bug 2. with more constraints, we expect worse solution, but gurobi gives better solution.

    0
  • Simon Bowly
    Gurobi Staff Gurobi Staff
    • Edited

    Hi Kai,

    Thanks for sharing this code.  I've tried running this for version 8.1.1 and can see the different objective function values with the different constraint ordering, however I can't reproduce the same result in version 9.1.2.  Could you please share the Gurobi logs from one of your runs which gives the incorrect result in version 9.1.2?  Note that you will need to un-set the OutputFlag parameter in your code which currently hides the logs.

    Thanks,
    Simon

    0
  • Kai WANG
    Gurobi-versary
    First Comment

    I have checked the setting of version 9.1.2 on my PC, it seems that for previous tests (both version 8.1.2, 9.1.2), the python command uses the same gurobi distribution in my PC.

    Now, I have reconfigured the version 9.1.2, and the bug does not appear for 9.1.2.

    Best,
    Kai

    0

Post is closed for comments.

Didn't find what you were looking for?

New post