[Help-glpk] Re: Characterizing multiple solutions

[Andrew Makhorin]

>So here's the problem: I'd basically like to answer the (vaguely stated)
>question: what point (set of values for all the variables) is at the "center"
>of the space of optimal solutions to this problem?  I understand there will
>probably be different definitions possible for the word "center" there, and
>I'd like to hear what definitions of "center" will be possible to discover.

The set of optimal solutions is a convex polyhedron whose vertices are
basic optimal solutions. So if you have several basic optimal solutions,
you can construct "interior" optimal solutions as convex combinations:

   x = lambda_1 * x_1 + lambda_2 * x_2 + ... + lambda_k * x_k,

   lambda_1 + ... + lambda_k = 1

   lambda_1, ..., lambda_k >= 0

where x_1, ..., x_k are basic optimal points (each x_j is a n-vector),
lambda_1, ..., lambda_k are arbitrary scalar coefficients.

Let d be dimension of the polyhedron (as a rule d is the number of
non-basic variables with zero reduced cost in optimal solution). Then
to construct a "true" interior optimal point (i.e. which is placed
strictly within the polyhedron rather than on some of its faces), you
need to have at least k = d+1 linearly independent optimal points. If
all lambdae are non-zero, say, 1 / (d+1), x is a "true" interior optimal
point and can be considered as some "center". However, the choice of
lambdae depends on what you need to attain.

Another way is to use an interior-point solver, in which case the
optimal solution being analytical center is always placed strictly
within the polyhedron. Though I am not sure that the glpk ip solver is
able to crunch your problem due to its size, try it.

However, most natural way is introducing additional constraints, in
particular, tighter bounds for non-basic variables with zero reduced
costs whose values you do not like.

Andrew Makhorin