[Scip] The Cut Pool in Scip

[Marc Pfetsch]

Hi Victor,

I am not sure whether I understood what you are planning, but it sounds 
as if all this can be handled inside a single constraint handler (or 
separator) keeping track of all the "small" constraints. For SCIP the 
only thing that matters is whether you add cuts or not.

When adding rows to the LP you should check whether they are violated by 
the current LP-solution. If not, they will be discarded anyway. The 
remaining cuts are filtered by the interal routines and only the most 
promising will be added to the LP. This is described in the PhD thesis 
of Tobias Achterberg (see http://scip.zib.de/further.shtml) in Section 
3.3.8.

If it was expensive to generate rows (and there is a limited number of 
them), you can add them to the cutpool. Cuts that are easy to generate 
should not be added, since it might be faster to separate them on the 
fly instead of running through all of them in the cutpool.

In order to keep control over a large number of cuts it often makes 
sense to stop the separation if enough cuts have been generated and 
continue at this place (without reiterating through the already 
separated cuts) in the next round.

I hope that this helps somewhat ...

Best

Marc


On 21.06.2013 16:58, Victor Miller wrote:
> I'm in the process of writing a constraint handler.  In this constraint
> (which I'll call the *big* constraint), it will keep an auxilliary list
> of quantities (which are lists of other data).  Each of these quantities
> can themselves be thought of as another, simpler, kind of constraint.
> For each of the simpler constraints there's an efficient separation
> procedure.  If all such separators are generated, but I've determined
> that the original (big) constraint isn't satisfied, then there's a
> method of generating one or more of the simpler constraints which must
> be satisfied.  So the strategy is to keep iterating this.  However, in
> running this the number of separators generated can get quite large.
> The question that I have is whether or not I should just add them to the
> cut pool, and allow it to use whatever heuristics it has (is there a
> good explanation of this?) to determine which ones to use.  Can you give
> me some guidance on this?
>
>
> Victor
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>