[Symphony] user_is_feasible()

[Ted Ralphs]

On Tue, Jun 21, 2011 at 5:26 PM, Michael Hennebry
<hennebry at web.cs.ndsu.nodak.edu> wrote:
> 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.

I suppose this would be possible, but I don't see how you could very
sensibly choose the branching disjunction. Without adding a cut, you
would need to produce at least one subproblem for which the current
(infeasible) relaxed solution would still be feasible to the
relaxation and this could potentially cause the search tree to grow
very quickly, especially if some of the variables didn't have bounds.
All in all, it doesn't seem like this would be a very realistic
solution. If the user does not know how to cut off a given
integer-but-infeasible solution with either a cut or a custom
branching disjunction, then it seems unlikely the solver will be very
effective on its own. I suppose it could be supported, though.
Actually, it could be implemented in SYMPHONY with a custom branching
method as it is.

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

But in this case, the problem would not be (discretely) convex and
there would be no valid MILP formulation to begin with. Technically,
you would need some sort of constraint programming solver to handle
this case, though it is possible you could somehow force an MILP
solver to handle it through branching (as above). In any case, all
MILP solvers (with the possible of SCIP) would assume this is not
possible, as far as I know.

Cheers,

Ted
-- 
Dr. Ted Ralphs
Associate Professor, Lehigh University
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted