Determine the solution from the optimal facet in LP
Answered
Hi, I have a model which has multiple optimal solutions.
But after model.optimize(), Gurobi Solver provides a single optimal solution.
So, I wonder how Gurobi solver determines a single optimal solution from the multiple solution set.
And I found the below link.
Is it possible to get the value of the Interior Solution ? – Gurobi Support Portal
By the answer of that link, the answerer said Gurobi provide an "analytic center of the optimal facet".
So (1) I want to know how this analytic center is calculated.
Because Some Linear programming models guarantee multiple optimal solutions, the solution`s robustness can be determined by what solution is chosen.
For example, we calculate the analytic center by maximizing the total distance from the interior points in the feasible region in LP.
(2)Also I want to know the "analytic center" is working on the 3-dimensional optimal facet.(i.e. the decision variable is more than 3)
At last, (3) Is analytic center working with model.optimize()? or should I manually change the setting? Like,
m.Params.Method = 2 # barrier
m.Params.Crossover = 0 # no crossover
Thx.
-
Official comment
Hello Taejoon,
1) for a polytope {x: Ax <= b} the analytic centre x* is computed as a minimizer of the log-barrier,
x* = arg min { -\sum_i (b - Ax)_i : Ax <= b }
Now, if LP has multiple solutions, i.e., a non-trivial optimal face, then if you use the barrier you will get to the analytic centre of that face (think, face, in turn, is also a polytope, that now describes all the optimal solutions).
If you want to think about it visually, one analogy here is the barycentre, that is, if you have more than one optimal solution which is a vertex, the analytic centre will be somewhere (strictly) between those. For example, if you have a very simple LP in 2 variables,
min y
s.t. 0 <= x <= 1,
0 <= y <= 1
the optimal solutions occupy a line segment on the x axis with y = 0 and x \in [0,1]; the analytic centre of the latter optimal face is right in the middle of that face, y* = 0, x* = 1/2.
A sometimes useful property of the analytic centre of the optimal face is that you will get what is called a maximal cardinality solution: in case of LP, the solution you get will have as many non-zero x's as possible.
2) I am not sure I understood this part of the Q, but if I were to guess what you are asking, then yes, see 1) above:)
3) By default Gurobi will try to give you a vertex solution, while the analytic centre of the optimal face is a point of convergence for the barrier algorithm only. When solving LP with the barrier, our default sequence is to (a) run the barrier method, followed by (b) the crossover algorithm, that will get you from the analytic centre of the optimal face to the optimal vertex. So you are absolutely correct, if you want to see the optimal analytic centre, you want to select the barrier but switch the crossover off, i.e., use
Method = 2
Crossover = 0
Hope this helps.
Please sign in to leave a comment.
Comments
1 comment