[Symphony] user_is_feasible()

[Michael Hennebry]

On Tue, 21 Jun 2011, Ted Ralphs wrote:

> There has to be some way of making progress, so if you tell SYMPHONY
> that the solution it has found by solving the current LP relaxation is
> infeasible, you have to also add a cut that eliminates that solution
> from the feasible region so that when it solves the next LP
> relaxation, it will generate something different. If not, it will go
> into an infinite loop, as you observed, since it will continue to
> generate the same (infeasible) solution again and again. This is the

Perfectly sensible, but not true of all solvers.
Some solvers, when out of other choices,
will branch on a variable that is already integer.
Eventaully, when all integer variables are fixed
and the solution is still infeasible,
they will prune a leaf.
I don't remember which solvers.

If the variables and the constraints are all-integer,
one can build a constraint out of the nonbasic variables.

At the other extreme, if it is an MIP,
it's possible that your magically infeasible solution could
be within the convex hull of mundanely feasible solutions.
In that case, finding a cut could be tricky.

-- 
Michael   hennebry at web.cs.ndsu.NoDak.edu
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."