[SCIP] Cover Inequalities for Knapsack

[Marc Pfetsch]

Hi Matheus,

turning off separation also turns off the separation of knapsack cuts.

You can enable them by setting

constraints/knapsack/sepafreq     and
constraints/knapsack/sepacardfreq

to a nonnegative number.

Best

Marc


On 19/04/2020 21:19, Matheus Ota wrote:
> Hi,
> 
> Thanks for pointing this out! I have another question, currently I'm
> adding constraints using SCIPcreateConsLinear. Does SCIP automatically
> detect knapsack-like constraints and apply the cover inequalities? Or
> should I replace SCIPcreateConsLinear by SCIPcreateConsKnapsack? Also,
> in my code I have this line: SCIP_CALL(SCIPsetSeparating(scip,
> SCIP_PARAMSETTING_OFF, TRUE)). Would I need to enable separating for
> cover inequalities to work properly? (If I remember correctly, I added
> this line because my custom constraint handler was not working properly
> without it. I'm implementing a Branch-and-Cut algorithm).
> 
> Thanks,
> Matheus
> 
> Em sáb., 18 de abr. de 2020 às 13:37, Marc Pfetsch
> <pfetsch at mathematik.tu-darmstadt.de
> <mailto:pfetsch at mathematik.tu-darmstadt.de>> escreveu:
> 
> 
> 
>     Dear Matheus,
> 
>     cover inequalities are separated automatically. But since the separation
>     problem is NP-hard in general, one needs to be careful about the
>     separation algorithms.
> 
>     An overview on most of the cutting planes is given in Chapter 8 of the
>     PhD thesis of Tobias Achterberg, available through the SCIP web page.
>     Details on knapsack inequalities are given in the diploma thesis of Kati
>     Wolter (http://www.zib.de/groetschel/students/Diplom-Wolter-2006.pdf).
> 
>     Note that the development of SCIP has evolved since then (i.e. since
>     2007 and 2006), so the performance of SCIP 7 will be different.
> 
>     Best
> 
>     Marc
> 
> 
> 
>     On 17/04/2020 20:22, Matheus Ota wrote:
>     > Hi,
>     >
>     > If I add a knapsack inequality in my model (\sum w_i x_i <= B), does
>     > SCIP automatically adds cover inequalities to strengthen my model? Or
>     > should I add then manually?
>     >
>     > I saw here (https://scip.zib.de/doc/html/cons__knapsack_8c.php) that
>     > SCIP have functions for Cover inequalities, but should I manually call
>     > these or are they automatically called? I ask this because I believe
>     > than in Gurobi the solver automatically adds cover inequalities
>     for the
>     > knapsack-like constraints. Also, is there some "easy to follow"
>     > documentation on the inequalities already built-in in SCIP? I want to
>     > avoid "reinventing the wheel" the maximum I can.
>     >
>     > Thanks,
>     > Matheus
>     >
>     > _______________________________________________
>     > Scip mailing list
>     > Scip at zib.de <mailto:Scip at zib.de>
>     > https://listserv.zib.de/mailman/listinfo/scip
>     >
>     _______________________________________________
>     Scip mailing list
>     Scip at zib.de <mailto:Scip at zib.de>
>     https://listserv.zib.de/mailman/listinfo/scip
>