Linear Programming: Find all optimal vertices

Question

I was wondering if there is a nice way (preferably using JuMP) to get all optimal solutions of a linear program (in case there are multiple optimal solutions).

An example

minimize the statistical distance (Kolmogorov distance) between two probabilities 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

Note we can phrase the optimization as a linear program, the objective becomes

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

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

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

Both have the minimal distance of 0.5, any convex combination of the these two solution is optimal.

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

Why am I interested in this; the points that gives the maximal Bhattacharyya coefficient (concave function), lies somewhere in the middle of the optimal subspace of the statical distance.

So far I`ve tried to find optimal P,Q pairs (refering to example I gave) by making the algorithm favor miniziming the distance between P[i],Q[i], by adding a weight of 1.001 to this term in the sum. It seems to work to some extend, although I can hardly know for sure.

Answer 1

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

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 designed to enumerate all optimal solutions. Once you know the optimal objective value, you can define the polyhedron containing all optimal solutions and then use a vertex enumeration algorithm to collect the possibly very large set of extreme points of this polyhedron. All optimal solutions are convex combinations of these extreme points. From Julia, you could use the wrapper for cdd.

Answer 3

I don't know about julia, but there is a tool called PPL that you can use to determine all the vertices of the solution polyedron after you solved the linear program.

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