[Symphony] user_is_feasible()

[Ted Ralphs]

Hi Terry,

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
essential challenge to be overcome in enumerating alternative optimal
solutions to a MIP. It is relatively easy to do in the case of a
binary MIP (you add a so-called "no-good cut"), but more difficult in
other cases. Adding no-good cuts is the strategy taken by SYMPHONY in
solving bicriteria binary MIPs, in which one must enumerate
alternative solutions with respect to single objectives in order to
identify Pareto outcomes. There was a recent discussion about this
same topic on the Cbc mailing list, but I think it was started by you,
so you must have seen it :). There have been a number of papers in the
literature on enumerating alternative optimal solutions that you might
take a look at.

Cheers,

Ted

On Tue, Jun 21, 2011 at 12:44 PM, Michael Hennebry
<hennebry at web.cs.ndsu.nodak.edu> wrote:
> On Tue, 21 Jun 2011, Terry wrote:
>
>> int user_is_feasible(void *user, double lpetol, int varnum, int *indices,
>>                     double *values, int *feasible, double *objval,
>>                     char branching, double *heur_solution)
>> {
>>    if (*objval <= 5.0 ) {
>>            *feasible = IP_INFEASIBLE;
>>            return(USER_SUCCESS);
>>    }
>>    return(USER_DEFAULT);
>> }
>>
>>
>> Obviously this could be accomplished more efficiently by adding a constraint. This is just a test to see if I can make SYMPHONY skip a solution by telling it some solutions are infeasible.
>>
>> This appears to put SYMPHONY in an infinite loop, calling it for objval = 4. I think it finds a solution candidate and just keeps trying to use that. It never calls the function with any other values.
>
> I ran into precisely this problem.
> If you tell SYMPHONY that an all-integer solution
> is infeasible you need to add a constraint.
> It's been a while.
> There might be some trickiness in adding the constraint.
>
> --
> 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."
>
> _______________________________________________
> Symphony mailing list
> Symphony at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/symphony
>



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