[SCIP] presolving clique inequalities

[Marc Pfetsch]

Hi Rolf,

here are some high level things that might help you:

SCIP builds a clique table in presolving (the magic happens in 
implics.c). During LP-solving clique inequalities are separated in 
sepa_clique, based on this data (the implication/clique graph); here new 
cliques are found, but - as far as I remember - not added to the clique 
table.

The information of the clique table is usually filled via setppc 
constraints in pesolving. Thus, if you want to do something with the 
clique table in presolving, you should do it via setppc constraints. 
Edge inequalities (added as setppc constraints) that are included in 
larger cliques should automatically be eliminated there. (An alternative 
would be to fill the clique table directly in your custom constraint.)

Beyond these general comments, I would need to know more about how you 
implemented the particular features to possibly be of help.

Best

Marc




On 02/09/2021 15:30, Rolf van der Hulst wrote:
> Dear SCIP community,
> 
> I am working on a stable set problem in graphs, where a set packing 
> constraint
> x_u+x_v <= 1
> is added for each edge (u,v) in a graph, with x_v indicating if a node 
> is chosen for a stable set. In many IP solvers such as Gurobi and CPLEX, 
> these are strengthened to the clique inequalities
>   \sum_{v\in C} x_v <= 1 for some clique C in the graph, eliminating 
> many rows from the LP.
> I'd like SCIP to do the same during presolving, but unfortunately I 
> cannot seem to find the right parameters in order to do so. During 
> separation these cliques are found, but for my application I still 
> observe a significant slowdown due to all the original edge inequalities 
> being included in the initial LP.
> 
> I tried changing the following parameters (individually), but could not 
> seem to find successful settings:
> 
> SCIP_CALL(SCIPsetBoolParam(scip,"constraints/setppc/cliquelifting",TRUE));
> SCIP_CALL(SCIPsetBoolParam(scip,"constraints/setppc/cliqueshrinking",FALSE));
> SCIP_CALL(SCIPsetIntParam(scip,"heuristics/clique/priority",1'000'000));
> SCIP_CALL(SCIPsetIntParam(scip,"separating/clique/priority",1'000'000));
> SCIP_CALL(SCIPsetBoolParam(scip,"constraints/setppc/addvariablesascliques",TRUE));
> SCIP_CALL(SCIPsetBoolParam(scip,"propagating/vbounds/usecliques",FALSE));
> SCIP_CALL(SCIPsetRealParam(scip,"presolving/clqtablefac",1000.0));
> SCIP_CALL(SCIPsetRealParam(scip,"separating/clique/cliquetablemem",2'000'000));
> SCIP_CALL(SCIPsetIntParam(scip,"separating/clique/maxsepacuts",1'000));
> SCIP_CALL(SCIPsetIntParam(scip,"separating/clique/maxzeroextensions",-1));
> 
> Additionally, I tried changing initial=FALSE for the edge constraints, 
> but this still didn't make the presolver find maximal cliques. If 
> someone could point me to the correct settings/functions, or knows if 
> such a functionality does not exist and I need to implement it manually, 
> I would be grateful.
> 
> With kind regards,
> 
> Rolf van der Hulst
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>