[SCIP] presolving clique inequalities

[Rolf van der Hulst]

 Dear Marc,

Thank you for your reply, and sorry for my late reply.

To clarify, I am adding binary variables for each node i in the graph

SCIP_CALL(SCIPcreateVarBasic(scip,&node_variables[i],name,0.0,1.0,1.0,SCIP_VARTYPE_BINARY));
SCIP_CALL(SCIPaddVar(scip,node_variables[i]));

Then, for each edge (i,j) I add an edge constraint:

SCIP_CALL(SCIPcreateConsBasicSetpack(scip,&edge_constraints[current],name,0,
nullptr));
SCIP_CALL(SCIPaddCoefSetppc(scip, edge_constraints[current],
node_variables[i]));
SCIP_CALL(SCIPaddCoefSetppc(scip, edge_constraints[current],
node_variables[j]));
SCIP_CALL(SCIPaddCons(scip, edge_constraints[current]));

I do not use any special/custom plugins. You mention that using set packing
constraints, these set packing constraints should be eliminated
automatically. However, this does not happen in my case; even with cases
where it should; e.g. this is the presolving output for a graph with 250
nodes and a density of 0.9, which is verified to contain many large cliques:

"LP Solver <SoPlex 5.0.2>: barrier convergence tolerance cannot be set --
tolerance of SCIP and LP solver may differ
LP Solver <SoPlex 5.0.2>: fastmip setting not available -- SCIP parameter
has no effect
LP Solver <SoPlex 5.0.2>: number of threads settings not available -- SCIP
parameter has no effect
transformed problem has 250 variables (250 bin, 0 int, 0 impl, 0 cont) and
27897 constraints
  27897 constraints of type <setppc>

original problem has 55794 active (0.8%) nonzeros and 55794 (0.8%) check
nonzeros

feasible solution found by trivial heuristic after 0.0 seconds, objective
value 0.000000e+00
presolving:
   (0.1s) running MILP presolver
   (0.1s) MILP presolver found nothing
   (0.3s) probing: 51/250 (20.4%) - 0 fixings, 0 aggregations, 0
implications, 0 bound changes
   (0.3s) probing aborted: 50/50 successive totally useless probings
   Deactivated symmetry handling methods, since SCIP was built without
symmetry detector (SYM=none).
clique table cleanup detected 0 bound changes

presolved problem has 55794 active (0.8%) nonzeros and 55794 (0.8%) check
nonzeros

presolving (1 rounds: 1 fast, 1 medium, 1 exhaustive):
 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened
bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 27896 cliques
presolved problem has 250 variables (250 bin, 0 int, 0 impl, 0 cont) and
27897 constraints
  27897 constraints of type <setppc>
transformed objective value is always integral (scale: 1)
Presolving Time: 0.39
transformed 1/1 original solutions to the transformed problem space"

Also during solving, SCIP seems to keep all of these constraints and rows
in the formulation, causing a huge slowdown. Other solvers seem to use in
the order of 1-5 * the number of variables cliques (rows) after presolving,
leading to much quicker solution times. SCIP does seem to add new clique
inequalities during the solution process, however the lack of clique
presolving still heavily impacts solution times, particularly for dense
graphs.
If you would know how to configure SCIP to replace these edge constraints
by clique constraints during preprocessing, I would appreciate that very
much.

Best,

Rolf

On Fri, Sep 3, 2021 at 9:46 AM Marc Pfetsch <
pfetsch at mathematik.tu-darmstadt.de> wrote:

>
>
> 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
> >
> _______________________________________________
> 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/20210923/e7ad8268/attachment.html>