Skip to main content

Determine the solution from the optimal facet in LP



1 comment

  • Official comment
    Yuriy Zinchenko
    Gurobi Staff Gurobi Staff

    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.