Scippy

SCIP

Solving Constraint Integer Programs

sepa_clique.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file sepa_clique.c
26 * @ingroup DEFPLUGINS_SEPA
27 * @brief clique separator
28 * @author Kati Wolter
29 * @author Tobias Achterberg
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
35#include "scip/pub_implics.h"
36#include "scip/pub_lp.h"
37#include "scip/pub_message.h"
38#include "scip/pub_misc.h"
39#include "scip/pub_sepa.h"
40#include "scip/pub_var.h"
41#include "scip/scip_branch.h"
42#include "scip/scip_cut.h"
43#include "scip/scip_general.h"
44#include "scip/scip_lp.h"
45#include "scip/scip_mem.h"
46#include "scip/scip_message.h"
47#include "scip/scip_numerics.h"
48#include "scip/scip_param.h"
49#include "scip/scip_prob.h"
50#include "scip/scip_sepa.h"
51#include "scip/scip_sol.h"
52#include "scip/scip_var.h"
53#include "scip/sepa_clique.h"
54#include "tclique/tclique.h"
55#include <string.h>
56#if defined(_WIN32) || defined(_WIN64)
57#else
58#include <strings.h> /*lint --e{766}*/
59#endif
60
61
62#define SEPA_NAME "clique"
63#define SEPA_DESC "clique separator of stable set relaxation"
64#define SEPA_PRIORITY -5000
65#define SEPA_FREQ 0
66#define SEPA_MAXBOUNDDIST 0.0
67#define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
68#define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
69
70#define DEFAULT_SCALEVAL 1000.0 /**< factor for scaling weights */
71#define DEFAULT_MAXTREENODES 10000 /**< maximal number of nodes in branch and bound tree (-1: no limit) */
72#define DEFAULT_BACKTRACKFREQ 1000 /**< frequency for premature backtracking up to tree level 1 (0: no backtracking) */
73#define DEFAULT_MAXSEPACUTS 10 /**< maximal number of clique cuts separated per separation round (-1: no limit) */
74#define DEFAULT_MAXZEROEXTENSIONS 1000 /**< maximal number of zero-valued variables extending the clique (-1: no limit) */
75#define DEFAULT_CLIQUETABLEMEM 20000.0 /**< maximal memory size of dense clique table (in kb) */
76#define DEFAULT_CLIQUEDENSITY 0.00 /**< minimal density of cliques to use a dense clique table */
77
78
79/*
80 * Data structures
81 */
82
83/** separator data */
84struct SCIP_SepaData
85{
86 TCLIQUE_GRAPH* tcliquegraph; /**< tclique graph data structure */
87 SCIP* scip; /**< SCIP data structure */
88 SCIP_SEPA* sepa; /**< separator */
89 SCIP_SOL* sol; /**< primal solution that is currently separated */
90 SCIP_Real* varsolvals; /**< LP solution of binary variables (contained in a 3-clique in implgraph) */
91 SCIP_Real scaleval; /**< factor for scaling weights */
92 SCIP_Longint ncalls; /**< number of calls to the clique separator */
93 int maxtreenodes; /**< maximal number of nodes in branch and bound tree (-1: no limit) */
94 int backtrackfreq; /**< frequency for premature backtracking up to tree level 1 (0: no backtracking) */
95 int maxsepacuts; /**< maximal number of clique cuts separated per separation round (-1: no limit) */
96 int maxzeroextensions; /**< maximal number of zero-valued variables extending the clique (-1: no limit) */
97 SCIP_Real cliquetablemem; /**< maximal memory size of dense clique table (in kb) */
98 SCIP_Real cliquedensity; /**< minimal density of cliques to use a dense clique table */
99 int ncuts; /**< number of cuts found */
100 SCIP_Bool tcliquegraphloaded; /**< TRUE if tcliquegraph is already loaded (tcliquegraph can be NULL),
101 * FALSE otherwise */
102 SCIP_Bool cutoff; /**< whether the clique algorithm detected a cutoff */
103 SCIP_RETCODE retcode; /**< error code which might occur during the maximal clique algorithm */
104};
105
106/** tclique graph data */
107struct TCLIQUE_Graph
108{
109 SCIP_VAR** vars; /**< active problem variables (or negated variables) the nodes belong to */
110 TCLIQUE_WEIGHT* weights; /**< weight of nodes */
111 int* adjnodesidxs; /**< indices in adjnodes array of first adjacent nodes for each node */
112 int* cliqueidsidxs; /**< indices in cliqueids array of first clique the node is contained in */
113 int* adjnodes; /**< adjacent nodes of edges */
114 unsigned int* cliqueids; /**< unique ids of cliques */
115 unsigned int* cliquetable; /**< dense bitvector clique table (array stored as a vector) */
116 int adjnodessize; /**< size of adjnodes array */
117 int cliqueidssize; /**< size of cliqueids array */
118 int nnodes; /**< number of nodes in graph */
119 int tablewidth; /**< number of unsigned ints per row in the table */
120
121 int maxnnodes; /**< allocated memory for some arrays */
122};
123
124
125/*
126 * Methods for tclique graph
127 */
128
129/** creates an empty tclique graph data structure */
130static
132 SCIP* scip, /**< SCIP data structure */
133 TCLIQUE_GRAPH** tcliquegraph /**< pointer to tclique graph data */
134 )
135{
136 int maxnnodes;
137
138 assert(tcliquegraph != NULL);
139
140 SCIP_CALL( SCIPallocBlockMemory(scip, tcliquegraph) );
141
142 /* there are at most 2*nbinvars nodes in the graph */
143 maxnnodes = 2*SCIPgetNBinVars(scip);
144 assert(maxnnodes > 0);
145
146 /* allocate memory for tclique graph arrays */
147 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*tcliquegraph)->vars, maxnnodes) );
148 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*tcliquegraph)->weights, maxnnodes) );
149 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*tcliquegraph)->adjnodesidxs, maxnnodes+1) );
150 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*tcliquegraph)->cliqueidsidxs, maxnnodes+1) );
151 (*tcliquegraph)->adjnodesidxs[0] = 0; /* the last slot defines the end of the last node */
152 (*tcliquegraph)->cliqueidsidxs[0] = 0; /* the last slot defines the end of the last node */
153 (*tcliquegraph)->adjnodes = NULL;
154 (*tcliquegraph)->cliqueids = NULL;
155 (*tcliquegraph)->cliquetable = NULL;
156 (*tcliquegraph)->adjnodessize = 0;
157 (*tcliquegraph)->cliqueidssize = 0;
158 (*tcliquegraph)->nnodes = 0;
159 (*tcliquegraph)->tablewidth = 0;
160 (*tcliquegraph)->maxnnodes = maxnnodes; /* remember allocated memory */
161
162 return SCIP_OKAY;
163}
164
165/** frees the tclique graph data structure and releases all captured variables */
166static
168 SCIP* scip, /**< SCIP data structure */
169 TCLIQUE_GRAPH** tcliquegraph /**< pointer to tclique graph data */
170 )
171{
172 int v;
173
174 assert(tcliquegraph != NULL);
175 assert(*tcliquegraph != NULL);
176
177 /* release variables */
178 for( v = 0; v < (*tcliquegraph)->nnodes; ++v )
179 {
180 SCIP_CALL( SCIPreleaseVar(scip, &(*tcliquegraph)->vars[v]) );
181 }
182
183 /* free memory */
184 SCIPfreeBlockMemoryArray(scip, &(*tcliquegraph)->vars, (*tcliquegraph)->maxnnodes);
185 SCIPfreeBlockMemoryArray(scip, &(*tcliquegraph)->weights, (*tcliquegraph)->maxnnodes);
186 SCIPfreeBlockMemoryArray(scip, &(*tcliquegraph)->adjnodesidxs, (*tcliquegraph)->maxnnodes + 1);
187 SCIPfreeBlockMemoryArray(scip, &(*tcliquegraph)->cliqueidsidxs, (*tcliquegraph)->maxnnodes + 1);
188 SCIPfreeMemoryArrayNull(scip, &(*tcliquegraph)->adjnodes);
189 SCIPfreeMemoryArrayNull(scip, &(*tcliquegraph)->cliqueids);
190 SCIPfreeMemoryArrayNull(scip, &(*tcliquegraph)->cliquetable);
191 SCIPfreeBlockMemory(scip, tcliquegraph);
192
193 return SCIP_OKAY;
194}
195
196
197/** ensures that the cliqueids array can store at least num entries */
198static
200 SCIP* scip, /**< SCIP data structure */
201 TCLIQUE_GRAPH* tcliquegraph, /**< tclique graph data */
202 int num /**< minimal number of adjacent nodes to be able to store in the array */
203 )
204{
205 assert(tcliquegraph != NULL);
206
207 if( num > tcliquegraph->cliqueidssize )
208 {
209 tcliquegraph->cliqueidssize = SCIPcalcMemGrowSize(scip, num);
210 SCIP_CALL( SCIPreallocMemoryArray(scip, &tcliquegraph->cliqueids, tcliquegraph->cliqueidssize) );
211 }
212 assert(num <= tcliquegraph->cliqueidssize);
213
214 return SCIP_OKAY;
215}
216
217/** adds a node to the tclique graph defined as a variable-value pair; adds all cliques to the cliqueids array the
218 * variable is contained in with the given value
219 */
220static
222 SCIP* scip, /**< SCIP data structure */
223 TCLIQUE_GRAPH** tcliquegraph, /**< pointer to tclique graph data */
224 SCIP_VAR* var, /**< active binary problem variable */
225 SCIP_Bool value, /**< value of the variable in the node */
226 int* nodeidx /**< pointer to store the index of the new node */
227 )
228{
229 SCIP_VAR* nodevar;
230 unsigned int* cliqueids;
231 SCIP_CLIQUE** cliques;
232 int ncliques;
233 int nadjnodes;
234 int ncliqueids;
235 int i;
236
237 assert(tcliquegraph != NULL);
238 assert(SCIPvarGetType(var) == SCIP_VARTYPE_BINARY);
239 assert(SCIPvarIsActive(var));
240 assert(nodeidx != NULL);
241
242 /* create tclique graph data if not yet existing */
243 if( *tcliquegraph == NULL )
244 {
245 SCIP_CALL( tcliquegraphCreate(scip, tcliquegraph) );
246 }
247 assert(*tcliquegraph != NULL);
248 assert((*tcliquegraph)->nnodes < 2*SCIPgetNBinVars(scip));
249
250 /* if the value is FALSE, use the negated variable for the node */
251 if( !value )
252 {
253 SCIP_CALL( SCIPgetNegatedVar(scip, var, &nodevar) );
254 }
255 else
256 nodevar = var;
257
258 /* get the current number of used entries in adjnodes and cliqueids arrays */
259 nadjnodes = (*tcliquegraph)->adjnodesidxs[(*tcliquegraph)->nnodes];
260 ncliqueids = (*tcliquegraph)->cliqueidsidxs[(*tcliquegraph)->nnodes];
261
262 /* insert the variable into the tclique graph */
263 *nodeidx = (*tcliquegraph)->nnodes;
264 SCIP_CALL( SCIPcaptureVar(scip, nodevar) );
265 (*tcliquegraph)->vars[*nodeidx] = nodevar;
266 (*tcliquegraph)->weights[*nodeidx] = 0;
267 (*tcliquegraph)->nnodes++;
268
269 /* store the ids of the variable's cliques in the cliqueids array */
270 ncliques = SCIPvarGetNCliques(var, value);
271 cliques = SCIPvarGetCliques(var, value);
272 SCIP_CALL( tcliquegraphEnsureCliqueidsSize(scip, *tcliquegraph, ncliqueids + ncliques) );
273 cliqueids = (*tcliquegraph)->cliqueids;
274 for( i = 0; i < ncliques; ++i )
275 {
276 assert(ncliqueids < (*tcliquegraph)->cliqueidssize);
277 cliqueids[ncliqueids] = SCIPcliqueGetId(cliques[i]);
278 assert(i == 0 || cliqueids[ncliqueids-1] <= cliqueids[ncliqueids]);
279 ncliqueids++;
280 }
281
282 /* store the new number of used entries in adjnodes and cliqueids arrays */
283 (*tcliquegraph)->adjnodesidxs[(*tcliquegraph)->nnodes] = nadjnodes;
284 (*tcliquegraph)->cliqueidsidxs[(*tcliquegraph)->nnodes] = ncliqueids;
285
286 return SCIP_OKAY;
287}
288
289/** adds all variable/value pairs to the tclique graph that are contained in an existing 3-clique */
290static
292 SCIP* scip, /**< SCIP data structure */
293 TCLIQUE_GRAPH** tcliquegraph, /**< pointer to tclique graph data */
294 int** cliquegraphidx /**< array to store tclique graph node index of variable/value pairs */
295 )
296{
297 SCIP_VAR** vars;
298 int nvars;
299 int i;
300
301 assert(tcliquegraph != NULL);
302 assert(cliquegraphidx != NULL);
303 assert(cliquegraphidx[0] != NULL);
304 assert(cliquegraphidx[1] != NULL);
305
306 /* get binary problem variables */
307 vars = SCIPgetVars(scip);
308 nvars = SCIPgetNBinVars(scip);
309
310 for( i = 0; i < nvars; ++i )
311 {
312 SCIP_VAR* var;
313 int value;
314
315 var = vars[i];
316
317 for( value = 0; value < 2; ++value )
318 {
319 assert(cliquegraphidx[value][i] == -1);
320
321 if( SCIPvarGetNCliques(var, (SCIP_Bool)value) >= 1 )
322 {
323 /* all cliques stored in the clique table are at least 3-cliques */
324 SCIP_CALL( tcliquegraphAddNode(scip, tcliquegraph, var, (SCIP_Bool)value, &cliquegraphidx[value][i]) );
325 }
326 }
327 }
328
329 return SCIP_OKAY;
330}
331
332/** constructs dense clique incidence matrix
333 *
334 * @todo add implicit and integer variables appearing in cliques also to the clique table
335 */
336static
338 SCIP* scip, /**< SCIP data structure */
339 TCLIQUE_GRAPH* tcliquegraph, /**< tclique graph data */
340 SCIP_Real cliquetablemem, /**< maximal memory size of dense clique table (in kb) */
341 SCIP_Real cliquedensity /**< minimal density of cliques to store as dense table */
342 )
343{
344 SCIP_CLIQUE** cliques;
345 int* varids;
346 unsigned int* cliquetable;
348 int nbits;
349 int tablesize;
350 int tablewidth;
351 int ncliques;
352 int nelems;
353 int i;
354
355 cliques = SCIPgetCliques(scip);
356 ncliques = SCIPgetNCliques(scip);
357 if( ncliques == 0 )
358 return SCIP_OKAY;
359
360 assert(tcliquegraph != NULL);
361
362 /* calculate size of dense clique table */
363 nbits = 8*sizeof(unsigned int);
364 tcliquegraph->tablewidth = (tcliquegraph->nnodes + nbits-1) / nbits; /* number of ints needed */
365
366 /* check if dense clique table is too large (calculate as Reals to avoid overflow) */
367 if( (SCIP_Real)tcliquegraph->nnodes * (SCIP_Real)tcliquegraph->tablewidth/1024.0 > cliquetablemem )
368 return SCIP_OKAY;
369
370 /* calculate clique entry density */
371 nelems = 0;
372 for( i = 0; i < ncliques; ++i )
373 nelems += SCIPcliqueGetNVars(cliques[i]);
374 density = (SCIP_Real)nelems / ((SCIP_Real)ncliques * (SCIP_Real)tcliquegraph->nnodes);
375 if( density < cliquedensity )
376 return SCIP_OKAY;
377
378 /* allocate memory */
379 tablesize = tcliquegraph->nnodes * tcliquegraph->tablewidth;
380 SCIPdebugMsg(scip, "clique separator: constructing dense clique table (%d kb, %d cliques, %d nodes, density: %.2f)\n",
381 tablesize/1024, SCIPgetNCliques(scip), tcliquegraph->nnodes, density);
382
383 SCIP_CALL( SCIPallocMemoryArray(scip, &tcliquegraph->cliquetable, tablesize) );
384 BMSclearMemoryArray(tcliquegraph->cliquetable, tablesize);
385
386 /* insert the cliques as complete graphs to the incidence matrix */
387 SCIP_CALL( SCIPallocBufferArray(scip, &varids, tcliquegraph->nnodes) );
388 cliquetable = tcliquegraph->cliquetable;
389 tablewidth = tcliquegraph->tablewidth;
390 for( i = 0; i < ncliques && !SCIPisStopped(scip); ++i )
391 {
392 SCIP_VAR** vars;
393 SCIP_Bool* vals;
394 int nvars;
395 int u;
396 int v;
397
398 vars = SCIPcliqueGetVars(cliques[i]);
399 vals = SCIPcliqueGetValues(cliques[i]);
400 nvars = SCIPcliqueGetNVars(cliques[i]);
401
402 /* get the node numbers of the variables */
403 for( u = 0; u < nvars && !SCIPisStopped(scip); ++u )
404 {
405 SCIP_VAR* var;
406
407 /* implicit integer and integer variables are currently not present in the constructed tclique graph */
408 if( SCIPvarGetType(vars[u]) != SCIP_VARTYPE_BINARY )
409 continue;
410
411 var = (vals[u] ? vars[u] : SCIPvarGetNegatedVar(vars[u]));
412 assert(var != NULL); /* var must exist even if negated, since it is stored in the tcliquegraph */
413 for( v = 0; v < tcliquegraph->nnodes && var != tcliquegraph->vars[v]; ++v )
414 {}
415 assert(v < tcliquegraph->nnodes);
416 varids[u] = v;
417 }
418
419 /* flag the edges in the incidence matrix (excluding diagonal entries) */
420 for( u = 0; u < nvars-1 && !SCIPisStopped(scip); ++u )
421 {
422 int nu;
423 int rowstart;
424 int colofs;
425 unsigned int colmask;
426
427 /* implicit integer and integer variables are currently not present in the constructed tclique graph */
428 if( SCIPvarGetType(vars[u]) != SCIP_VARTYPE_BINARY )
429 continue;
430
431 nu = varids[u];
432 rowstart = nu*tablewidth;
433 colofs = nu/nbits;
434 colmask = 1U << (nu % nbits); /*lint !e701*/
435 for( v = u+1; v < nvars; ++v )
436 {
437 int nv;
438 unsigned int mask;
439
440 /* implicit integer and integer variables are currently not present in the constructed tclique graph */
441 if( SCIPvarGetType(vars[v]) != SCIP_VARTYPE_BINARY )
442 continue;
443
444 nv = varids[v];
445 mask = 1U << (nv % nbits); /*lint !e701*/
446 cliquetable[rowstart+nv/nbits] |= mask;
447 cliquetable[nv*tablewidth+colofs] |= colmask;
448 }
449 }
450 }
451 SCIPfreeBufferArray(scip, &varids);
452
453 SCIPdebugMsg(scip, "clique separator: finished constructing dense clique table\n");
454
455 return SCIP_OKAY;
456}
457
458/** creates tclique data structure using the implication graph;
459 * only variables that are contained in a 3-clique are added as nodes to the clique graph
460 */
461static
463 SCIP* scip, /**< SCIP data structure */
464 SCIP_SEPADATA* sepadata /**< separator data */
465 )
466{
467 int* cliquegraphidx[2];
468 int nvars;
469 int i;
470
471 assert(sepadata != NULL);
472 assert(sepadata->tcliquegraph == NULL);
473
474 /* there is nothing to do, if no binary variables are present in the problem */
475 nvars = SCIPgetNBinVars(scip);
476 if( nvars == 0 )
477 return SCIP_OKAY;
478
479 /* get temporary memory for mapping variable/value pairs to clique graph nodes */
480 SCIP_CALL( SCIPallocBufferArray(scip, &cliquegraphidx[0], nvars) );
481 SCIP_CALL( SCIPallocBufferArray(scip, &cliquegraphidx[1], nvars) );
482 for( i = 0; i < nvars; ++i )
483 {
484 cliquegraphidx[0][i] = -1;
485 cliquegraphidx[1][i] = -1;
486 }
487
488 /* insert all variable/value pairs that are contained in an existing 3-clique */
489 SCIP_CALL( tcliquegraphAddCliqueVars(scip, &sepadata->tcliquegraph, cliquegraphidx) );
490
491 /* it occurs that it might be that some cliques were not yet removed from the global clique array, so SCIPgetNClique
492 * can be greater than 0, even if there is no clique with some variables left */
493 /** @todo clean up empty cliques */
494 if( sepadata->tcliquegraph != NULL )
495 {
496 /* construct the dense clique table */
497 SCIP_CALL( tcliquegraphConstructCliqueTable(scip, sepadata->tcliquegraph, sepadata->cliquetablemem, sepadata->cliquedensity) );
498 }
499
500 /* free temporary memory */
501 SCIPfreeBufferArray(scip, &cliquegraphidx[1]);
502 SCIPfreeBufferArray(scip, &cliquegraphidx[0]);
503 if( SCIPisStopped(scip) && sepadata->tcliquegraph != NULL )
504 SCIP_CALL( tcliquegraphFree(scip,&sepadata->tcliquegraph) );
505 return SCIP_OKAY;
506}
507
508/** updates the weights in the tclique graph data structure */
509static
511 SCIP* scip, /**< SCIP data structure */
512 SCIP_SEPADATA* sepadata /**< separator data */
513 )
514{
515 TCLIQUE_GRAPH* tcliquegraph;
516 int i;
517
518 assert(sepadata != NULL);
519 assert(sepadata->varsolvals != NULL);
520
521 tcliquegraph = sepadata->tcliquegraph;
522 assert(tcliquegraph != NULL);
523
524 /* updates weight of all nodes in tclique data structure */
525 for( i = 0; i < tcliquegraph->nnodes; i++ )
526 {
527 int weight;
528
529 weight = (TCLIQUE_WEIGHT)SCIPfeasFloor(scip, sepadata->varsolvals[i] * sepadata->scaleval);
530 tcliquegraph->weights[i] = MAX(weight, 0);
531 }
532}
533
534
535/*
536 * TClique Graph Callbacks
537 */
538
539/** gets number of nodes in the graph */
540static
541TCLIQUE_GETNNODES(tcliqueGetnnodesClique)
542{
543 assert(tcliquegraph != NULL);
544
545 return tcliquegraph->nnodes;
546}
547
548/** gets weight of nodes in the graph */
549static
550TCLIQUE_GETWEIGHTS(tcliqueGetweightsClique)
551{
552 assert(tcliquegraph != NULL);
553
554 return tcliquegraph->weights;
555}
556
557/** returns whether the nodes are member of a common clique */
558static
560 TCLIQUE_GRAPH* tcliquegraph, /**< tclique graph data */
561 int node1, /**< first node */
562 int node2 /**< second node */
563 )
564{
565 assert(tcliquegraph != NULL);
566
567 /* return TRUE for equal nodes */
568 if( node1 == node2 )
569 return TRUE;
570
571 /* check whether the dense clique table was constructed */
572 if( tcliquegraph->cliquetable != NULL )
573 {
574 int nbits;
575 unsigned int mask;
576 int colofs;
577
578 /* check entry in the table */
579 nbits = 8*sizeof(unsigned int);
580 mask = (1U << (node2 % nbits)); /*lint !e701*/
581 colofs = node2 / nbits;
582 assert(((tcliquegraph->cliquetable[node1*tcliquegraph->tablewidth + colofs] & mask) != 0)
583 == ((tcliquegraph->cliquetable[node2*tcliquegraph->tablewidth + node1/nbits] & (1U << (node1 % nbits))) != 0)); /*lint !e701*/
584 return ((tcliquegraph->cliquetable[node1*tcliquegraph->tablewidth + colofs] & mask) != 0);
585 }
586 else
587 {
588 unsigned int* cliqueids;
589 int i1;
590 int i2;
591 int endi1;
592 int endi2;
593
594 cliqueids = tcliquegraph->cliqueids;
595 i1 = tcliquegraph->cliqueidsidxs[node1];
596 endi1 = tcliquegraph->cliqueidsidxs[node1+1];
597 i2 = tcliquegraph->cliqueidsidxs[node2];
598 endi2 = tcliquegraph->cliqueidsidxs[node2+1];
599 while( i1 < endi1 && i2 < endi2 )
600 {
601 while( i1 < endi1 && cliqueids[i1] < cliqueids[i2] )
602 i1++;
603 if( i1 == endi1 )
604 break;
605
606 while( i2 < endi2 && cliqueids[i2] < cliqueids[i1] )
607 i2++;
608 if( i2 == endi2 )
609 break;
610
611 if( cliqueids[i1] == cliqueids[i2] )
612 return TRUE;
613 }
614
615 return FALSE;
616 }
617}
618
619/** returns, whether the edge (node1, node2) is in the graph */
620static
621TCLIQUE_ISEDGE(tcliqueIsedgeClique)
622{
623 int left;
624 int right;
625
626 assert(tcliquegraph != NULL);
627 assert(0 <= node1 && node1 < tcliquegraph->nnodes);
628 assert(0 <= node2 && node2 < tcliquegraph->nnodes);
629
630 /* check if node2 is contained in adjacency list of node1 (list is ordered by adjacent nodes) */
631 left = tcliquegraph->adjnodesidxs[node1];
632 right = tcliquegraph->adjnodesidxs[node1+1]-1;
633 while( left <= right )
634 {
635 int middle;
636 int node;
637
638 middle = (left+right)/2;
639 node = tcliquegraph->adjnodes[middle];
640 if( node < node2 )
641 left = middle+1;
642 else if( node > node2 )
643 right = middle-1;
644 else
645 return TRUE;
646 }
647
648 /* check if the nodes are member of a common clique */
649 return nodesHaveCommonClique(tcliquegraph, node1, node2);
650}
651
652/** selects all nodes from a given set of nodes which are adjacent to a given node
653 * and returns the number of selected nodes
654 */
655static
656TCLIQUE_SELECTADJNODES(tcliqueSelectadjnodesClique)
657{
658 int* graphadjnodes;
659 int nadjnodes;
660 int nodeadjindex;
661 int nodeadjend;
662 int i;
663
664 assert(tcliquegraph != NULL);
665 assert(0 <= node && node < tcliquegraph->nnodes);
666 assert(nnodes == 0 || nodes != NULL);
667 assert(adjnodes != NULL);
668
669 nadjnodes = 0;
670
671 /* check for each node in given nodes set, if it is adjacent to the given node or shares a common clique */
672 graphadjnodes = tcliquegraph->adjnodes;
673 nodeadjindex = tcliquegraph->adjnodesidxs[node];
674 nodeadjend = tcliquegraph->adjnodesidxs[node+1];
675 for( i = 0; i < nnodes; i++ )
676 {
677 /* check if the node is adjacent to the given node (nodes and adjacent nodes are ordered by node index) */
678 assert(0 <= nodes[i] && nodes[i] < tcliquegraph->nnodes);
679 assert(i == 0 || nodes[i-1] < nodes[i]);
680 while( nodeadjindex < nodeadjend && graphadjnodes[nodeadjindex] < nodes[i] )
681 nodeadjindex++;
682 if( nodeadjindex < nodeadjend && graphadjnodes[nodeadjindex] == nodes[i] )
683 {
684 /* current node is adjacent to given node */
685 adjnodes[nadjnodes] = nodes[i];
686 nadjnodes++;
687 }
688 else
689 {
690 /* current node is not adjacent to given node: check if they share a common clique */
691 if( nodesHaveCommonClique(tcliquegraph, node, nodes[i]) )
692 {
693 adjnodes[nadjnodes] = nodes[i];
694 nadjnodes++;
695 }
696 }
697 }
698
699 return nadjnodes;
700}
701
702/** basic code for new cliques (needed because of error handling) */
703static
705 SCIP* scip, /**< SCIP data structure */
706 SCIP_SEPA* sepa, /**< the cut separator itself */
707 SCIP_SEPADATA* sepadata, /**< data of separator */
708 int ncliquenodes, /**< number of nodes in clique */
709 int* cliquenodes /**< nodes in clique */
710 )
711{
712 SCIP_VAR** vars;
713 SCIP_ROW* cut;
714 char cutname[SCIP_MAXSTRLEN];
715 int i;
716
717 vars = sepadata->tcliquegraph->vars;
718 assert(sepadata->tcliquegraph->nnodes > 0);
719 assert(vars != NULL);
720
721 /* create the cut (handle retcode since we do not have a backtrace) */
722 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "clique%" SCIP_LONGINT_FORMAT "_%d", sepadata->ncalls, sepadata->ncuts);
723 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), 1.0, FALSE, FALSE, TRUE) );
724
726
727 assert(ncliquenodes <= sepadata->tcliquegraph->nnodes);
728 /*SCIPdebugMsg(scip, " -> clique in graph:");*/
729 for( i = 0; i < ncliquenodes; ++i )
730 {
731 assert(cliquenodes[i] < sepadata->tcliquegraph->nnodes);
732 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cliquenodes[i]], 1.0) );
733 /*SCIPdebugMsgPrint(scip, " [%d]<%s>", cliquenodes[i], SCIPvarGetName(vars[cliquenodes[i]]));*/
734 }
735 /*SCIPdebugMsgPrint(scip, "\n");*/
737
738 /* set cut rank: for clique cuts we always set to 1 */
739 SCIProwChgRank(cut, 1);
740
741 /*SCIPdebug( SCIP_CALL(SCIPprintRow(scip, cut, NULL)) );*/
742
744
745 /* release the row */
746 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
747
748 return SCIP_OKAY;
749}
750
751/** generates cuts using a clique found by algorithm for maximum weight clique
752 * and decides whether to stop generating cliques with the algorithm for maximum weight clique
753 */
754static
755TCLIQUE_NEWSOL(tcliqueNewsolClique)
756{
757 SCIP_SEPADATA* sepadata;
758 TCLIQUE_WEIGHT minweightinc;
759
760 assert(acceptsol != NULL);
761 assert(stopsolving != NULL);
762
763 sepadata = (SCIP_SEPADATA*)tcliquedata;
764 assert(sepadata != NULL);
765 assert(sepadata->scip != NULL);
766 assert(sepadata->sepa != NULL);
767 assert(sepadata->tcliquegraph != NULL);
768 assert(sepadata->ncuts >= 0);
769
770 /* we don't accept the solution as new incumbent, because we want to find many violated clique inequalities */
771 *acceptsol = FALSE;
772 *stopsolving = FALSE;
773
774 /* slightly increase the minimal weight for additional cliques */
775 minweightinc = (cliqueweight - *minweight)/10;
776 minweightinc = MAX(minweightinc, 1);
777 *minweight += minweightinc;
778
779 /* adds cut if weight of the clique is greater than 1 */
780 if( cliqueweight > sepadata->scaleval )
781 {
782 SCIP* scip;
783 SCIP_SEPA* sepa;
784 SCIP_Real* varsolvals;
785 SCIP_Real unscaledweight;
786 int i;
787
788 scip = sepadata->scip;
789 sepa = sepadata->sepa;
790 varsolvals = sepadata->varsolvals;
791 assert(varsolvals != NULL);
792
793 /* calculate the weight of the clique in unscaled fractional variable space */
794 unscaledweight = 0.0;
795 for( i = 0; i < ncliquenodes; i++ )
796 unscaledweight += varsolvals[cliquenodes[i]];
797
798 if( SCIPisEfficacious(scip, unscaledweight - 1.0) )
799 {
800 SCIP_RETCODE retcode;
801
802 /* explicitly handle return code */
803 retcode = newsolCliqueAddRow(scip, sepa, sepadata, ncliquenodes, cliquenodes);
804 if ( retcode == SCIP_OKAY )
805 {
806 SCIPdebugMsg(scip, " -> found clique cut (act=%g)\n", unscaledweight);
807 sepadata->ncuts++;
808
809 /* if we found more than half the cuts we are allowed to generate, we accept the clique as new incumbent,
810 * such that only more violated cuts are generated afterwards */
811 if( sepadata->maxsepacuts >= 0 )
812 {
813 if( sepadata->ncuts > sepadata->maxsepacuts/2 )
814 *acceptsol = TRUE;
815 if( sepadata->ncuts >= sepadata->maxsepacuts )
816 *stopsolving = TRUE;
817 }
818 }
819 else
820 {
821 /* in case an internal SCIP error occurred we stop the algorithm and store the error code for later
822 * evaluation
823 */
824 sepadata->retcode = retcode;
825 *stopsolving = TRUE;
826 }
827 }
828 }
829}
830
831
832/*
833 * main separation method
834 */
835
836/** searches and adds clique cuts that separate the given primal solution
837 *
838 * @todo Should the existing cliques in the table be separated before starting the tclique algorithm?
839 * Is this done somewhere else?
840 */
841static
843 SCIP* scip, /**< SCIP data structure */
844 SCIP_SEPA* sepa, /**< the cut separator itself */
845 SCIP_SOL* sol, /**< primal solution that should be separated, or NULL for LP solution */
846 SCIP_RESULT* result /**< pointer to store the result of the separation call */
847 )
848{ /*lint --e{715}*/
849 SCIP_SEPADATA* sepadata;
850 TCLIQUE_GRAPH* tcliquegraph;
851 int* cliquenodes;
852 TCLIQUE_WEIGHT cliqueweight;
853 TCLIQUE_STATUS tcliquestatus;
854 int ncliquenodes;
855 int maxtreenodes;
856 int maxzeroextensions;
857 SCIP_Bool infeasible;
858
859 assert(scip != NULL);
860 assert(*result == SCIP_DIDNOTRUN);
861
862 infeasible = FALSE;
863 /* get clique table */
864 SCIP_CALL( SCIPcleanupCliques(scip, &infeasible) );
865 if( infeasible )
866 return SCIP_OKAY;
867
868 /* get separator data */
869 sepadata = SCIPsepaGetData(sepa);
870 assert(sepadata != NULL);
871
872 sepadata->sol = sol;
873 sepadata->ncalls = SCIPsepaGetNCalls(sepa);
874 sepadata->cutoff = FALSE;
875 sepadata->ncuts = 0;
876
877 /* if we already detected that no implications between binary variables exist, nothing has to be done */
878 if( sepadata->tcliquegraph == NULL && sepadata->tcliquegraphloaded )
879 return SCIP_OKAY;
880
881 *result = SCIP_DIDNOTFIND;
882
883 /* load tclique data structure */
884 if( !sepadata->tcliquegraphloaded )
885 {
886 assert(sepadata->tcliquegraph == NULL);
887
888 SCIPdebugMsg(scip, "loading implication and clique graph\n");
889 SCIP_CALL( loadTcliquegraph(scip, sepadata) );
890 sepadata->tcliquegraphloaded = TRUE;
891
892 if( sepadata->tcliquegraph == NULL )
893 {
894 if( SCIPisStopped(scip) )
895 sepadata->tcliquegraphloaded = FALSE;
896 /* we did not find any variables that are contained in a clique with at least 3 variables in the
897 * implication graph or in the clique table -> nothing has to be done
898 */
899 else
900 {
901 SCIPdebugMsg(scip, "no 3-cliques found in implication graph\n");
902 }
903
904 return SCIP_OKAY;
905 }
906 }
907 tcliquegraph = sepadata->tcliquegraph;
908 assert(tcliquegraph != NULL);
909
910 /* store LP-solution in sepadata and update weights in tclique data structure */
911 SCIP_CALL( SCIPallocBufferArray(scip, &sepadata->varsolvals, tcliquegraph->nnodes) );
912 SCIP_CALL( SCIPgetSolVals(scip, sol, tcliquegraph->nnodes, tcliquegraph->vars, sepadata->varsolvals) );
913 updateTcliquegraph(scip, sepadata);
914
915 /* get maximal number of tree nodes and maximal zero-extensions */
916 maxtreenodes = (sepadata->maxtreenodes == -1 ? INT_MAX : sepadata->maxtreenodes);
917 maxzeroextensions = (sepadata->maxzeroextensions == -1 ? INT_MAX : sepadata->maxzeroextensions);
918
919 SCIPdebugMsg(scip, "searching for violated clique cuts\n");
920
921 sepadata->retcode = SCIP_OKAY;
922
923 /* finds maximum weight clique in tclique */
924 SCIP_CALL( SCIPallocBufferArray(scip, &cliquenodes, tcliquegraph->nnodes) );
925 tcliqueMaxClique(tcliqueGetnnodesClique, tcliqueGetweightsClique, tcliqueIsedgeClique, tcliqueSelectadjnodesClique,
926 tcliquegraph, tcliqueNewsolClique, (TCLIQUE_DATA*)sepadata,
927 cliquenodes, &ncliquenodes, &cliqueweight, (int)sepadata->scaleval-1, (int)sepadata->scaleval+1,
928 maxtreenodes, sepadata->backtrackfreq, maxzeroextensions, -1, NULL, &tcliquestatus);
929
930 /* in case an internal error occurred during the maximal clique computation, evaluate that one */
931 SCIP_CALL( sepadata->retcode );
932
933 SCIPdebugMsg(scip, "finished searching clique cuts: found %d cuts\n", sepadata->ncuts);
934
935 /* frees data structures */
936 SCIPfreeBufferArray(scip, &cliquenodes);
937 SCIPfreeBufferArray(scip, &sepadata->varsolvals);
938
939 /* adjust result code */
940 if ( sepadata->cutoff )
941 *result = SCIP_CUTOFF;
942 else if( sepadata->ncuts > 0 )
943 *result = SCIP_SEPARATED;
944
945 /* better reset the sol pointer in sepadata to avoid having an invalid pointer */
946 sepadata->sol = NULL;
947
948 return SCIP_OKAY;
949}
950
951
952/*
953 * Callback methods of separator
954 */
955
956/** copy method for separator plugins (called when SCIP copies plugins) */
957static
958SCIP_DECL_SEPACOPY(sepaCopyClique)
959{ /*lint --e{715}*/
960 assert(scip != NULL);
961 assert(sepa != NULL);
962 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
963
964 /* call inclusion method of constraint handler */
966
967 return SCIP_OKAY;
968}
969
970
971/** destructor of separator to free user data (called when SCIP is exiting) */
972static
973SCIP_DECL_SEPAFREE(sepaFreeClique)
974{ /*lint --e{715}*/
975 SCIP_SEPADATA* sepadata;
976
977 sepadata = SCIPsepaGetData(sepa);
978 assert(sepadata != NULL);
979 assert(sepadata->tcliquegraph == NULL);
980
981 SCIPfreeBlockMemory(scip, &sepadata);
982 SCIPsepaSetData(sepa, NULL);
983
984 return SCIP_OKAY;
985}
986
987
988/** solving process deinitialization method of separator (called before branch and bound process data is freed) */
989static
990SCIP_DECL_SEPAEXITSOL(sepaExitsolClique)
991{ /*lint --e{715}*/
992 SCIP_SEPADATA* sepadata;
993
994 sepadata = SCIPsepaGetData(sepa);
995 assert(sepadata != NULL);
996
997 /* free tclique data */
998 if( sepadata->tcliquegraph != NULL )
999 {
1000 SCIP_CALL( tcliquegraphFree(scip, &sepadata->tcliquegraph) );
1001 }
1002 assert(sepadata->tcliquegraph == NULL);
1003 sepadata->tcliquegraphloaded = FALSE;
1004
1005 return SCIP_OKAY;
1006}
1007
1008
1009/** LP solution separation method of separator */
1010static
1011SCIP_DECL_SEPAEXECLP(sepaExeclpClique)
1012{
1013 /*lint --e{715}*/
1014
1015 *result = SCIP_DIDNOTRUN;
1016
1017 /* only call separator, if we are not close to terminating */
1018 if( SCIPisStopped(scip) )
1019 return SCIP_OKAY;
1020
1021 /* only call separator, if an optimal LP solution is at hand */
1023 return SCIP_OKAY;
1024
1025 /* only call separator, if there are fractional variables */
1026 if( SCIPgetNLPBranchCands(scip) == 0 )
1027 return SCIP_OKAY;
1028
1029 /* separate cuts on the LP solution */
1030 SCIP_CALL( separateCuts(scip, sepa, NULL, result) );
1031
1032 return SCIP_OKAY;
1033}
1034
1035
1036/** arbitrary primal solution separation method of separator */
1037static
1038SCIP_DECL_SEPAEXECSOL(sepaExecsolClique)
1039{
1040 /*lint --e{715}*/
1041
1042 *result = SCIP_DIDNOTRUN;
1043
1044 /* separate cuts on the given primal solution */
1045 SCIP_CALL( separateCuts(scip, sepa, sol, result) );
1046
1047 return SCIP_OKAY;
1048}
1049
1050
1051/*
1052 * separator specific interface methods
1053 */
1054
1055/** creates the clique separator and includes it in SCIP */
1057 SCIP* scip /**< SCIP data structure */
1058 )
1059{
1060 SCIP_SEPADATA* sepadata;
1061 SCIP_SEPA* sepa;
1062
1063 /* create clique separator data */
1064 SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
1065 sepadata->tcliquegraph = NULL;
1066 sepadata->scip = scip;
1067 sepadata->sol = NULL;
1068 sepadata->varsolvals = NULL;
1069 sepadata->ncalls = 0;
1070 sepadata->ncuts = 0;
1071 sepadata->tcliquegraphloaded = FALSE;
1072
1073 /* include separator */
1076 sepaExeclpClique, sepaExecsolClique,
1077 sepadata) );
1078
1079 assert(sepa != NULL);
1080 sepadata->sepa = sepa;
1081
1082 /* set non-NULL pointers to callback methods */
1083 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyClique) );
1084 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeClique) );
1085 SCIP_CALL( SCIPsetSepaExitsol(scip, sepa, sepaExitsolClique) );
1086
1087 /* add clique separator parameters */
1089 "separating/clique/scaleval",
1090 "factor for scaling weights",
1091 &sepadata->scaleval, TRUE, DEFAULT_SCALEVAL, 1.0, SCIP_REAL_MAX, NULL, NULL) );
1093 "separating/clique/maxtreenodes",
1094 "maximal number of nodes in branch and bound tree (-1: no limit)",
1095 &sepadata->maxtreenodes, TRUE, DEFAULT_MAXTREENODES, -1, INT_MAX, NULL, NULL) );
1097 "separating/clique/backtrackfreq",
1098 "frequency for premature backtracking up to tree level 1 (0: no backtracking)",
1099 &sepadata->backtrackfreq, TRUE, DEFAULT_BACKTRACKFREQ, 0, INT_MAX, NULL, NULL) );
1101 "separating/clique/maxsepacuts",
1102 "maximal number of clique cuts separated per separation round (-1: no limit)",
1103 &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, -1, INT_MAX, NULL, NULL) );
1105 "separating/clique/maxzeroextensions",
1106 "maximal number of zero-valued variables extending the clique (-1: no limit)",
1107 &sepadata->maxzeroextensions, TRUE, DEFAULT_MAXZEROEXTENSIONS, -1, INT_MAX, NULL, NULL) );
1109 "separating/clique/cliquetablemem",
1110 "maximal memory size of dense clique table (in kb)",
1111 &sepadata->cliquetablemem, TRUE, DEFAULT_CLIQUETABLEMEM, 0.0, (SCIP_Real)INT_MAX/1024.0, NULL, NULL) );
1113 "separating/clique/cliquedensity",
1114 "minimal density of cliques to use a dense clique table",
1115 &sepadata->cliquedensity, TRUE, DEFAULT_CLIQUEDENSITY, 0.0, 1.0, NULL, NULL) );
1116
1117 return SCIP_OKAY;
1118}
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Longint
Definition: def.h:158
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIP_CALL(x)
Definition: def.h:374
#define nnodes
Definition: gastrans.c:74
static const SCIP_Real density
Definition: gastrans.c:145
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:428
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:361
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:81
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:70
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:64
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1453
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:17534
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: scip_sepa.c:109
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:743
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:167
SCIP_RETCODE SCIPsetSepaExitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAEXITSOL((*sepaexitsol)))
Definition: scip_sepa.c:231
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:633
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:643
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:151
SCIP_Longint SCIPsepaGetNCalls(SCIP_SEPA *sepa)
Definition: sepa.c:860
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1254
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:17894
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17748
SCIP_CLIQUE ** SCIPgetCliques(SCIP *scip)
Definition: scip_var.c:7629
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
Definition: scip_var.c:7532
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1527
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18430
int SCIPgetNCliques(SCIP *scip)
Definition: scip_var.c:7575
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18441
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
SCIP_RETCODE SCIPincludeSepaClique(SCIP *scip)
Definition: sepa_clique.c:1056
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3380
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3370
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3392
unsigned int SCIPcliqueGetId(SCIP_CLIQUE *clique)
Definition: implics.c:3402
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
public methods for implications, variable bounds, and cliques
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
public methods for separators
public methods for problem variables
public methods for branching rule plugins and branching
public methods for cuts and aggregation rows
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for separator plugins
public methods for solutions
public methods for SCIP variables
static SCIP_DECL_SEPAEXITSOL(sepaExitsolClique)
Definition: sepa_clique.c:990
#define SEPA_PRIORITY
Definition: sepa_clique.c:64
#define DEFAULT_SCALEVAL
Definition: sepa_clique.c:70
static SCIP_RETCODE tcliquegraphAddNode(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph, SCIP_VAR *var, SCIP_Bool value, int *nodeidx)
Definition: sepa_clique.c:221
#define DEFAULT_MAXTREENODES
Definition: sepa_clique.c:71
static SCIP_RETCODE tcliquegraphCreate(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph)
Definition: sepa_clique.c:131
#define SEPA_DELAY
Definition: sepa_clique.c:68
#define DEFAULT_CLIQUEDENSITY
Definition: sepa_clique.c:76
static SCIP_RETCODE tcliquegraphAddCliqueVars(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph, int **cliquegraphidx)
Definition: sepa_clique.c:291
static TCLIQUE_ISEDGE(tcliqueIsedgeClique)
Definition: sepa_clique.c:621
static SCIP_RETCODE tcliquegraphConstructCliqueTable(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, SCIP_Real cliquetablemem, SCIP_Real cliquedensity)
Definition: sepa_clique.c:337
#define SEPA_DESC
Definition: sepa_clique.c:63
#define DEFAULT_BACKTRACKFREQ
Definition: sepa_clique.c:72
#define DEFAULT_CLIQUETABLEMEM
Definition: sepa_clique.c:75
#define SEPA_USESSUBSCIP
Definition: sepa_clique.c:67
static SCIP_DECL_SEPAEXECLP(sepaExeclpClique)
Definition: sepa_clique.c:1011
#define DEFAULT_MAXZEROEXTENSIONS
Definition: sepa_clique.c:74
static TCLIQUE_SELECTADJNODES(tcliqueSelectadjnodesClique)
Definition: sepa_clique.c:656
static SCIP_RETCODE tcliquegraphEnsureCliqueidsSize(SCIP *scip, TCLIQUE_GRAPH *tcliquegraph, int num)
Definition: sepa_clique.c:199
static SCIP_RETCODE newsolCliqueAddRow(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, int ncliquenodes, int *cliquenodes)
Definition: sepa_clique.c:704
static SCIP_Bool nodesHaveCommonClique(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
Definition: sepa_clique.c:559
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: sepa_clique.c:842
static TCLIQUE_GETWEIGHTS(tcliqueGetweightsClique)
Definition: sepa_clique.c:550
#define SEPA_MAXBOUNDDIST
Definition: sepa_clique.c:66
#define SEPA_FREQ
Definition: sepa_clique.c:65
static SCIP_DECL_SEPACOPY(sepaCopyClique)
Definition: sepa_clique.c:958
static TCLIQUE_GETNNODES(tcliqueGetnnodesClique)
Definition: sepa_clique.c:541
#define DEFAULT_MAXSEPACUTS
Definition: sepa_clique.c:73
#define SEPA_NAME
Definition: sepa_clique.c:62
static SCIP_DECL_SEPAFREE(sepaFreeClique)
Definition: sepa_clique.c:973
static SCIP_DECL_SEPAEXECSOL(sepaExecsolClique)
Definition: sepa_clique.c:1038
static TCLIQUE_NEWSOL(tcliqueNewsolClique)
Definition: sepa_clique.c:755
static SCIP_RETCODE loadTcliquegraph(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_clique.c:462
static SCIP_RETCODE tcliquegraphFree(SCIP *scip, TCLIQUE_GRAPH **tcliquegraph)
Definition: sepa_clique.c:167
static void updateTcliquegraph(SCIP *scip, SCIP_SEPADATA *sepadata)
Definition: sepa_clique.c:510
clique separator
tclique user interface
enum TCLIQUE_Status TCLIQUE_STATUS
Definition: tclique.h:68
int TCLIQUE_WEIGHT
Definition: tclique.h:48
void tcliqueMaxClique(TCLIQUE_GETNNODES((*getnnodes)), TCLIQUE_GETWEIGHTS((*getweights)), TCLIQUE_ISEDGE((*isedge)), TCLIQUE_SELECTADJNODES((*selectadjnodes)), TCLIQUE_GRAPH *tcliquegraph, TCLIQUE_NEWSOL((*newsol)), TCLIQUE_DATA *tcliquedata, int *maxcliquenodes, int *nmaxcliquenodes, TCLIQUE_WEIGHT *maxcliqueweight, TCLIQUE_WEIGHT maxfirstnodeweight, TCLIQUE_WEIGHT minweight, int maxntreenodes, int backtrackfreq, int maxnzeroextensions, int fixednode, int *ntreenodes, TCLIQUE_STATUS *status)
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:49
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SEPARATED
Definition: type_result.h:49
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:52
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62