[Coin-symphony] how to save cut generated by feasibility test?

[tkr2 at lehigh.edu]

Quoting Michael Hennebry <hennebry at web.cs.ndsu.nodak.edu>:

> On Tue, 31 May 2005 tkr2 at lehigh.edu wrote:
> 
> > Quoting Michael Hennebry <hennebry at web.cs.ndsu.nodak.edu>:
> >
> > >
> > >
> > > If user_is_feasible includes a test for violated linear
> > > constraints (e.g. subcycle breaking constraints),
> > > Ascertaining that a solution is infeasible might also
> > > generate a cut.
> > > It would be nice to be able to save that cut and
> > > not have to redo the work when user_find_cuts is called.
> > > How does one do that?
> >
> > Yes, I agree this is something that one might want to do, but I haven't
> gotten
> > around to providing a direct way of doing it. Currently, the most
> > straightforward and safest way to do this is to simply generate the cut in
> > user_is_feasible() and save them in the user data structure. Then in the
> > function user_generate_cuts_in_lp(), just return them. This should actually
> be
> > pretty easy to do I would think.
> 
> How do I make sure that the call to user_generate_cuts_in_lp()
> applies to the same b&b node as the call to user_is_feasible()?
> I suppose the straightforward way would be to test  whether
> the constraint is violated, but depending on implementation
> details of Symphony, it might lack in reliability.

user_generate_cuts() should always be called directly after user_is_feasible() 
if the user reports that the solution is not feasible() and user_is_feasible() 
was not called during strong branching. There is now an argument to 
user_is_feasible() that tells you whether it was called during straong 
branching or not. At any rate, there is no harm in passing an unviolated cut 
to SYMPHONY, since it also tests violation before adding the cut. As long as 
the cuts are globally valid, you can hand them to SYMPHONY anytime and it will 
not cause problems. I guess this contradicts my eariler remark about not 
generating cuts during straong branching, but this really only applied to cuts 
that are not globally valid.

> Also, is there a reason I should use user_generate_cuts_in_lp()
> instead of user_generate_cuts()?

If you want to parallelize your code and therefore have separate user data 
structures for the LP solver and the cut generator, it would not be possible 
to user user_generate_cuts(). That is the only reason.

> -- 
> Mike   hennebry at web.cs.ndsu.NoDak.edu
> "There are three kinds of people,
> those who can count and those who can't."
> 


-------------------------------------------------
This mail sent through IMP: http://horde.org/imp/