[SCIP] Cover Inequalities for Knapsack

[Matheus Ota]

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> 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
> > https://listserv.zib.de/mailman/listinfo/scip
> >
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20200419/910b9a6d/attachment.html>