Re: [Help-glpk] Characterizing multiple solutions

[Michael Hennebry]

On Tue, 25 Nov 2003, Chris Smith wrote:

> 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.

Your question is basically "How should I define and find the center
of a polyhedron defined as the intersection of half-spaces?"

The answer depends on what you want it for.
To help you decide, consider where the center
should be for the following shapes, and why:
                  _____________________
A long thin box, |_____________________|
Probably you want the average of the four corners.
Minimizing the distance from the boundary won't necessarily give you that.
I'll give you a point on a line segment.
Summing the distances from the half-space boundaries won't do you any better.
The sum is a constant.

A long thin triangle, e.g. one with 1, 10, and 10 units on a side.
Minimizing the distance from the boundary would put
the center within a half unit from the short side.
The average of the corners is about 3.3 units from the short side.
Minimizing the sum of the distances from the sides would
put the center at the corner opposite the short side.
                                       _____________
A long thin box with one round side,  (_____________|
The round side isn't actually round, but it's defined
by most of the half-spaces defining the polyhedron.
Averaging corners would put the center near the round end.
Minmizing the distance from the boundary would
put the center anywhere along a line segment.
Minimizine the sum of the distances from the half-space boundaries
would put the center on the side opposite the round side.


Minimizing the distance from the boundary might be what you
want, but it doesn't necessarily define the center and at
most d+1 boundaries are involved in determining the center,
where d is the dimension of the polyhedron.

Maximizing the sum of the distances from the
half-space boundaries won't work at all.
The sum is a linear function.
It has a maximum on an extreme point.


I suggest the following:

       m
max   SUM w[j]*sqrt(d[j])
      j=0

      d[j] = distance of x from boundary j (linear)  for j in 1..m

      d[0] <= d[j]   for j in 1..m

      d[0] >= 0

      x in Polyhedron  (the original constraints)


where w is a set of non-negative weights.

If w[0] is positive, d[0] will be the distance from x to the boundary.

With this formulation, getting away from a boundary
is more important the closer one is to it.


To facilitate solving this with an LP solver,
the following inequality will help:

sqrt(d[j]) <= sqrt(p) + (d[j]-p)/(2*sqrt(p))    for d[j]>=0, p> 0

p can be a d[j] from a previous solution.


Selecting good weights is left as an exercise for the reader.
With all-positive weights, I expect that the solution would be unique.

Whatever you decide, I recommend against enumerating the vertices.

-- 
Mike   address@hidden
"History is written by the winners."  --  the losers