How to get Unique Solutions to Linear Programs in different execution
AnsweredIn my different runs of Gurobi solving, the orders of constraints or variables we sent to Gurobi are different because I use multithreading techniques. So in each execution, I got a different solution since a LP problem could have multiple optimal solution.
Is there any ways or options to make sure I can get unique solutions in different run?
Thanks a lot!

Hi Yamin,
There are different things in the solver that are sensitive to the ordering of variables and constraints within the model, one of them is presolve, and also, starting point for some algorithms.
In general, you do not want to disable presolve, as it is one of the key components (for performance) in any solver, still, if for you is more important to always have the same solution, then it might be worth trying to disable it.
From the algorithmic point of view, barrier will return a unique solution (within tolerances), but that is only aplicable if your problem is truly a linear program, without any integrality condition.
From a modeling point of view, you can always add a hierarchy of objectives (e.g. a lexicographic objective on all variables) such that the problem does indeed have a unique solution... Although in theory you need to specify n objectives to ensure uniqueness, in practice, specifying a few lexicographic/hierarchical objectives is enough to have a unique solution.
Hope this helps,
Daniel
0 
Hi Yamin & Daniel,
I am using Gurobi's barrier method for solving a restricted master problem in each iteration of a Column Generation (CG)based Optimization Framework. However, running the same code of the framework multiple times is leading to a very different solution. I have even fixed the seeds of all random numbers from all packages involved in the framework (Random, Numpy, Gurobi) for the reproducibility fo the results. On analyzing the logs, I found that at 2nd CGiteration, the LPcost obtained using the Gurobi's barrier method is changing at 2nd or 3rd decimal place, leading to a different LPsolution which in turn leads to a different set of variables being produced in the pricing subproblem of that CGiteration. From this point, the framework starts deviating from the results of previous runs. This is happening with each differentrun.
After searching about this, I found that the LPsolver can return an alternateoptimal solution. However, I got confused as to how a computer can decide to give different LPsolutions (similar but not equal) even if all the random seeds are fixed. Then, I came across this thread and is thinking that the culprit is the multithreading package that I am using for generating new columns. With different CPUstates, a multithreaded module can return a differentlyordered set of same columns, and as you stated above that the order of variable can change the output of the LPsolver. Please correct me if I have wrongly concluded. Also, is there anything else I can do to produce the same results other than switchingoff the Presolve., given that I am using the Barrier method already.
Thanks,
Divyam
0
Please sign in to leave a comment.
Comments
2 comments