[Symphony] user_is_feasible()

[Michael Hennebry]

On Thu, 30 Jun 2011, Ted Ralphs wrote:

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

I didn't claim it was a good idea.
That said, I think the depth can be limited
to twice the number of integer variables.
When performing a branch on a variable with one bound,
make sure that the current solution is on the finite side.

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

min 1.z

s.t.
     z >= 10.3*1 - x
     z >= x - 10.3*1
     L <= x <= U
     x all integer
     x in S
where 1 is a row or column vector of all ones,
"." represents a sum, "10.3*1" is a column vector
and x in S represents the feaibility test.

There is no way to remove 10*1 with a valid cut on x.
There is no way to remove 10*1 with a valid cut on x and z.

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