[SCIP] presolving clique inequalities

Marc Pfetsch pfetsch at mathematik.tu-darmstadt.de
Thu Sep 23 18:56:37 CEST 2021 


Hi Rolf,

you can try to use

constraints/setppc/cliquelifting

Maybe that helps. It seems, however, that the general handling of these 
cases is currently not very efficiently implemented.

Best

Marc


On 23/09/2021 18.26, Rolf van der Hulst wrote:
> 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 
> <mailto: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 <mailto:Scip at zib.de>
>      > https://listserv.zib.de/mailman/listinfo/scip
>     <https://listserv.zib.de/mailman/listinfo/scip>
>      >
>     _______________________________________________
>     Scip mailing list
>     Scip at zib.de <mailto:Scip at zib.de>
>     https://listserv.zib.de/mailman/listinfo/scip
>     <https://listserv.zib.de/mailman/listinfo/scip>
> 
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>

More information about the Scip mailing list