Linear programming: find all the optimal vertices

Question

I was wondering if there is a good way (preferably using JuMP) to get all the optimal solutions of a linear program (if there are several optimal solutions).

Example

minimize the statistical distance (Kolmogorov distance) between the two probability distributions.

min sum_{i=1}^{4} |P[i] - Q[i]| over free variable Q P = [0.25,0.25,0.25,0.25] sum_i P[i] = 1 Q[1] + Q[4] = 1 sum_i Q[i] = 1 -> Q[2],Q[3] = 0 

Please note that we can formulate optimization as a linear program, the goal becomes

 min S >= sum_i S[i] S[i] >= P[i]-Q[i] S[i] >= Q[i]-P[i] 

There is no single solution to this problem; instead, the subspace of the optimal solution is spanned by

 Q1 = [0.75,0,0,0.25] Q2 = [0.25,0,0,0.75] 

Both have a minimum distance of 0.5, any convex combination of these two solutions is optimal.

I was wondering if there is a good way to find all these optimal extremal points (points that span the optimal subspace)?

Why am I interested in this? the points that give the maximum coefficient bhattacharyya (concave function) lie somewhere in the middle of the optimal subspace of the static distance.

So far I have tried to find the optimal pairs P, Q (referring to the example I gave), forcing the algorithm to approve the minimization of the distance between P [i], Q [i], adding to this weight a 1.001 term in total. This seems to work to some extent, although I can hardly know for sure.

Answer 1

There is an interesting way to list all possible optimal LP solutions (or, rather, all optimal LP bases) using a standard MIP solver. Basically the algorithm:

 step 1. solve LP/MIP step 2. if infeasible or if objective starts to deteriorate: stop step 3. add cuts (constraints) to the model to forbid current optimal solution step 4. goto step 1 

For an example see here .

Answer 2

LP solvers are not intended to enumerate all optimal solutions. Once you know the optimal target value, you can define a polyhedron containing all the optimal solutions, and then use the vertex enumeration algorithm to collect, possibly, a very large set of extreme points of this polyhedron. All optimal solutions are convex combinations of these extreme points. From Julia you can use a wrapper for cdd .

Answer 3

I do not know about julia, but there is a tool called PPL that you can use to determine all the vertices of the polyhedron solution after you have solved the linear program.

See my answer here to a similar question: Find all alternative basic solutions using an existing linear programming tool .