How to get Unique Solutions to Linear Programs in different execution

Answered

Yamin Wang

• June 03, 2019 22:00

In my different runs of Gurobi solving, the orders of constraints or variables we sent to Gurobi are different because I use multi-threading 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!

1

• 

  Daniel Espinoza

  • June 04, 2019 13:50

  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
• 

  Divyam Aggarwal

  • January 24, 2020 11:39

  

  

  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 CG-iteration, the LP-cost obtained using the Gurobi's barrier method is changing at 2nd or 3rd decimal place, leading to a different LP-solution which in turn leads to a different set of variables being produced in the pricing subproblem of that CG-iteration. From this point, the framework starts deviating from the results of previous runs. This is happening with each different-run.

  After searching about this, I found that the LP-solver can return an alternate-optimal solution. However, I got confused as to how a computer can decide to give different LP-solutions (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 multi-threading package that I am using for generating new columns. With different CPU-states, a multi-threaded module can return a differently-ordered set of same columns, and as you stated above that the order of variable can change the output of the LP-solver. Please correct me if I have wrongly concluded. Also, is there anything else I can do to produce the same results other than switching-off the Presolve., given that I am using the Barrier method already.

  Thanks,

  Divyam

  0

Please sign in to leave a comment.