Re: [Help-glpk] Almost infeasible solution, not sure what to do next

[Michael Hennebry]

On Mon, 12 Oct 2009, Sam Seaver wrote:

> It seems to me, that any time it declares that it is infeasible, I
> could iterate through all of the columns, and find the one column for
> which the bounds are the 'most' violated, and output the column and
> its details.  In this way, I could, in a semi-automated manner, find
> the problems that are either optimal, or almost infeasible.

Determining whether a [nearly] degenerate basis
corresponds to a fesible solution can be tricky.
Determining whether there is a feasible solution nearby might be easier:
Make all the tight constraints slightly stronger and resolve.
If the original feasible space was full-dimensional and the strengthened
constraints are not too strong you should still get a solution.
With interval arithmetic or something similar,
it should be possible to prove the solution feasible.

If the original problem was not feasible,
you might have to resort to exact arithmetic to prove it.
If you do so, start with the "optimal" solution found by GLPK.

-- 
Michael   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."