Order of constraints affects solution optimality; Code returns suboptimal solution
OngoingHi,
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 suboptimal solution, even though the optimal solution is feasible (I verified this by setting the optimal solution while defining the variables).
Please advise.
Thanks,
Tamal.

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,
Silke0 
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 suboptimal 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 
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 
Can you post the first and last ~30 lines of the logs from both versions?
0 
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 [5e01, 6e+02]
Objective range [1e07, 1e06]
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.484169e07, 276 iterations, 0.00 seconds
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time0 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%  0sCutting planes:
Gomory: 3
Cover: 16
Implied bound: 2
Clique: 22
Zero half: 2Explored 1 nodes (457 simplex iterations) in 0.14 seconds
Thread count was 12 (of 12 available processors)Solution count 2: 1.999e06 5.75969e06
Optimal solution found (tolerance 1.00e04)
Best objective 1.998998410569e06, best bound 1.998998410569e06, 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 [5e01, 6e+02]
Objective range [1e07, 1e06]
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.861364e07, 18 iterations, 0.00 seconds
Nodes  Current Node  Objective Bounds  Work
Expl Unexpl  Obj Depth IntInf  Incumbent BestBd Gap  It/Node Time0 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%  0sCutting planes:
Cover: 3
MIR: 2
StrongCG: 1Explored 1 nodes (49 simplex iterations) in 0.02 seconds
Thread count was 12 (of 12 available processors)Solution count 1: 2.86136e07
Optimal solution found (tolerance 1.00e04)
Best objective 2.861364498984e07, best bound 2.861364498984e07, gap 0.0000%Thanks,
Tamal.0 
Hi Tamal,
Thanks for the information and for sharing your logs.
It seems that all of your objective coefficients are very small (between 1e7 and 1e6) 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 
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 
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 
Thanks a lot!
0 
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 
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 unset the OutputFlag parameter in your code which currently hides the logs.
Thanks,
Simon0 
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,
Kai0
Please sign in to leave a comment.
Comments
12 comments