Re: [Help-glpk] Question about Simplex implementation

[Michael Hennebry]

On Mon, 21 Jan 2008, Marc Lanctot wrote:

> Suppose I use GLPK's implementation of the Simplex algorithm to solve a
> linear program built from two-player equilibria equations for a
> particular matrix game, and get back a mixed strategy (a probability
> dist. which does not only have 1 and 0 entries). Does this mean that
> mixing is necessary to achieve the optimal value? In other words, is it
> true that there exists no deterministic strategy that achieves the same
> value? (eg. the impl. of Simplex will return a det. strategy if one exists?)

It does if the solution is unique,
which would be the case if the reduced costs were all nonzero.

If the solution is not unique,
one can lock all the constraints with nonzero
reduced costs and invoke branch and bound.
Distinguishing nonzero from small is left as an exercise for the reader.

-- 
Michael   address@hidden
"Those parts of the system that you can hit with a hammer (not advised)
are called Hardware;  those program instructions that you can only
curse at are called Software."