[SCIP] presolving clique inequalities

[Rolf van der Hulst]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20210902/d6e33849/attachment.html>