[SCIP] Cover Inequalities for Knapsack

[Marc Pfetsch]

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
>