# SCIP

Solving Constraint Integer Programs

cons_storeGraph.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 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file cons_storeGraph.c
17  * @brief constraint handler for storing the graph at each node of the tree
18  * @author Gerald Gamrath
19  *
20  * This file implements the constraints that are used for the branching in the coloring algorithm.
21  *
22  * For each node in the branch-and-bound tree, a constraint of this type is created, which stores
23  * all restrictions related to that branch-and-bound node.
24  *
25  * First of all, it stores the type of the constraint ("same" or "differ", the root has type root)
26  * and the two nodes in the graph on which this restriction is applied. When the branch-and-bound
27  * node corresponding to the constraint is examined for the first time, the constraint creates a
28  * graph that takes into account all the restrictions, which are active at this node.
29  * At the root, this is the original (preprocessed) graph. At any other branch-and-bound node, it
30  * takes the graph of the constraint related to the branch-and-bound parent node of the current node and
31  * modifies it so that all restrictions up to this node are respected. Since the graph in the
32  * branch-and-bound parent respects all restrictions on the path to that node, only the last
33  * requirement, the one saved at the current branch-and-bound node, must be added.
34  * This is done as follows: Adding a DIFFER(v,w) constraint is easy, since it suffices to add
35  * an edge between v and w. For a SAME(v,w) constraint, the original idea is to collapse the nodes v
36  * and w into one single vertex. Since this is not possible in the tclique-graph data structure, we
37  * introduce new edges in the graph, so that v and w have the same neighborhood. Hence, in the
38  * pricing routine, each new stable set will either contain both nodes or none of them, since we
39  * create (inclusion-) maximal sets.
40  *
41  * This does of course not hold for sets created in a higher level of the branch-and-bound tree or
42  * in another subtree. In order to forbid all of these sets, which do not fulfill the current
43  * restrictions, a propagation is started when the node is entered the first time and repeated
44  * later, if the node is reentered after the creation of new variables in another subtree. The
45  * propagation simply fixes all variables to 0 which represent a stable set that does not
46  * fulfill the restriction at the current node.
47  *
48  * The information about all fusions of nodes (caused by the SAME() operation) is stored, so that the nodes
49  * constituting a union can be accessed easily. Each union has a representative and a set of nodes, whereas
50  * each node knows the representative of the union it belongs to. At the beginning, each node forms its own
51  * union and therefore each node also represents this union, consisting of only this node. Later on, some
52  * nodes represent unions of several nodes, while other nodes are part of a union which they do not represent,
53  * so they have another node as representative. The representatives of the nodes are returned by the methods
54  * COLORconsGetRepresentative() / COLORconsGetRepresentatives(), the union represented by a node is returned
55  * by COLORconsGetUnion(), the array of unions, indexed by the representing node, is returned by
56  * COLORconsGetUnions().
57  */
58
59 #include <assert.h>
60 #include <string.h>
61
62 #include "scip/type_cons.h"
63 #include "cons_storeGraph.h"
64 #include "probdata_coloring.h"
65 #include "tclique/tclique.h"
67 #include "scip/cons_linear.h"
68
69
70 /* constraint handler properties */
71 #define CONSHDLR_NAME "storeGraph"
72 #define CONSHDLR_DESC "storing graph at nodes of the tree constraint handler"
73 #define CONSHDLR_ENFOPRIORITY 0 /**< priority of the constraint handler for constraint enforcing */
74 #define CONSHDLR_CHECKPRIORITY 2000000 /**< priority of the constraint handler for checking feasibility */
75 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
76 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
77  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
78 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
79 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
81 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
83
84 /** constraint data for storing graph constraints */
85 struct SCIP_ConsData
86 {
87  TCLIQUE_GRAPH* graph; /* the current graph in the B&B-node belonging to this constraint */
88  TCLIQUE_GRAPH* cgraph; /* the complementary graph of the current graph */
89  SCIP_CONS* fathercons; /* the constraint sticking at the B&B-node's father */
90  int* representativeofnode; /* r...[i] = j if node j is representative of the union containing node i */
91  int** unionofnode; /* for all represantatives of a union an array with all the union's members */
92  int* nnodesinunion; /* value at position i = #elements in unionofnode[i] */
93  int node1; /* first node for DIFFER / SAME */
94  int node2; /* second node for DIFFER / SAME */
95  COLOR_CONSTYPE type; /* type of the branching operation: COLOR_CONSTYPE_DIFFER oder COLOR_CONSTYPE_SAME */
96  int propagatedvars; /* number of Vars that existed, the last time, the related node was propagated,
97  used to determine whether the constraint should be repropagated*/
98  SCIP_Bool created; /* flag for saving the creation status of the graph saved in the cons,
99  at the beginning false, after the first activation set to true */
100  SCIP_NODE* stickingatnode; /* the node in the B&B-tree at which the cons is sticking */
101 };
102
103
104 /** constraint handler data */
105 struct SCIP_ConshdlrData
106 {
107  SCIP_CONS** stack; /**< stack for storing active constraints */
108  int nstack; /**< number of elements on the stack */
109  int maxstacksize; /**< maximum size of the stack */
110 };
111
112
113 /*
114  * Local methods
115  */
116
117 /** creates and captures the storeGraph constraint for the root node*/
118 static
120  SCIP* scip, /**< SCIP data structure */
121  SCIP_CONS** cons, /**< pointer to hold the created constraint */
122  const char* name, /**< name of constraint */
123  TCLIQUE_GRAPH* graph /**< the original graph */
124  )
125 {
126  SCIP_CONSHDLR* conshdlr;
127  SCIP_CONSDATA* consdata;
128  int i;
129  int nnodes;
130
131  assert(scip != NULL);
132  assert(graph != NULL);
133  nnodes = tcliqueGetNNodes(graph);
134  /* find the storeGraph constraint handler */
135  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
136  if ( conshdlr == NULL )
137  {
139  return SCIP_PLUGINNOTFOUND;
140  }
141
142  SCIPdebugMessage("Creating graph storage constraint at root node.\n");
143
144  /* create constraint data */
145  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
146  consdata->graph = graph;
147  consdata->node1 = -1;
148  consdata->node2 = -1;
149  consdata->type = COLOR_CONSTYPE_ROOT;
150  consdata->fathercons = NULL;
151  consdata->propagatedvars = 0;
152  consdata->stickingatnode = NULL;
153  consdata->created = TRUE;
154
155  /* allocate memory for the arrays and fill them */
156  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->representativeofnode), nnodes) );
157  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->nnodesinunion), nnodes) );
158  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->unionofnode), nnodes) );
159  for ( i = 0; i < nnodes; i++ )
160  {
161  consdata->representativeofnode[i] = i;
162  consdata->nnodesinunion[i] = 1;
163  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->unionofnode[i]), 1) ); /*lint !e866*/
164  consdata->unionofnode[i][0] = i;
165  }
166
167  /* create the complementary graph */
168  if( !tcliqueCreate(&(consdata->cgraph)) )
169  {
170  SCIPerrorMessage("could not flush the clique graph\n");
171  return SCIP_ERROR;
172  }
173
174  assert(consdata->cgraph != NULL);
175
176  SCIP_CALL( COLORprobGetComplementaryGraph(scip, graph, consdata->cgraph) );
177
178  /* create constraint */
179  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, FALSE, FALSE, FALSE, FALSE, FALSE,
180  TRUE, FALSE, TRUE, FALSE, FALSE));
181
182  return SCIP_OKAY;
183 }
184
185
186 /*
187  * Callback methods
188  */
189
190 #ifdef SCIP_DISABLED_CODE
191 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
192 /** We do not want to copy store graph constraints into subSCIPs since they just store information about
193  * branching decisions and are used to enforce those.
194  * However, in subSCIPs, we only want to solve the current MIP with a branch-and-cut approach.
195  */
196 #define conshdlrCopyStoreGraph NULL
197 #endif
198
199 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
200 static
201 SCIP_DECL_CONSFREE(consFreeStoreGraph)
202 {
203  SCIP_CONSHDLRDATA* conshdlrData;
204
205  assert(scip != NULL);
206  assert(conshdlr != NULL);
207  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
208
209  conshdlrData = SCIPconshdlrGetData(conshdlr);
210  assert(conshdlrData != NULL);
211
212  SCIPdebugMessage("freeing store graph constraint handler\n");
213
214  /* free constraint handler storage */
215  assert(conshdlrData->stack == NULL);
216  SCIPfreeBlockMemory(scip, &conshdlrData);
217
218  return SCIP_OKAY;
219 }
220
221
222 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
223 static
224 SCIP_DECL_CONSINITSOL(consInitsolStoreGraph)
225 {
226  SCIP_CONSHDLRDATA* conshdlrData;
227  SCIP_CONS* cons;
228  assert(scip != NULL);
229  assert(conshdlr != NULL);
230  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
231
232  conshdlrData = SCIPconshdlrGetData(conshdlr);
233  assert(conshdlrData != NULL);
234
235  /* prepare stack */
236  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &conshdlrData->stack, conshdlrData->maxstacksize) );
237  SCIP_CALL( createConsStoreGraphAtRoot(scip, &cons, "root", COLORprobGetGraph(scip)) );
238
239  /* release constraints */
240  conshdlrData->stack[0] = cons;
241  conshdlrData->nstack = 1;
242
243  return SCIP_OKAY;
244 }/*lint !e715*/
245
246
247 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
248 static
249 SCIP_DECL_CONSEXITSOL(consExitsolStoreGraph)
250 {
251  SCIP_CONSHDLRDATA* conshdlrData;
252
253  assert(scip != NULL);
254  assert(conshdlr != NULL);
255  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
256
257  conshdlrData = SCIPconshdlrGetData(conshdlr);
258  assert(conshdlrData != NULL);
259  assert(conshdlrData->nstack == 1); /* at this point the stack should only have the root-constraint on it */
260  SCIP_CALL( SCIPreleaseCons(scip, &(conshdlrData->stack[0])) );
261  conshdlrData->stack[0] = NULL;
262  SCIPdebugMessage("exiting store graph constraint handler\n");
263
264  /* free stack */
265  SCIPfreeBlockMemoryArray(scip, &conshdlrData->stack, conshdlrData->maxstacksize);
266
267  return SCIP_OKAY;
268 }/*lint !e715*/
269
270
271 /** frees specific constraint data */
272 static
273 SCIP_DECL_CONSDELETE(consDeleteStoreGraph)
274 {
275  int i;
276
277  assert(scip != NULL);
278  assert(conshdlr != NULL);
279  assert(cons != NULL);
280  assert(consdata != NULL);
281  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
282  assert(*consdata != NULL);
283
284  SCIPdebugMessage("Deleting store graph constraint: <%s(%d,%d)>.\n", SCIPconsGetName(cons), (*consdata)->node1+1, (*consdata)->node2+1);
285
286  /* free constraint data */
287  if ( (*consdata)->type == COLOR_CONSTYPE_ROOT )
288  {
289  for ( i = tcliqueGetNNodes((*consdata)->graph)-1; i >= 0; i-- )
290  {
291  SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode[i]), (*consdata)->nnodesinunion[i]); /*lint !e866*/
292  assert((*consdata)->nnodesinunion[i] == 1);
293  }
294  SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode), tcliqueGetNNodes((*consdata)->graph));
295  SCIPfreeBlockMemoryArray(scip, &((*consdata)->nnodesinunion), tcliqueGetNNodes((*consdata)->graph));
296  SCIPfreeBlockMemoryArray(scip, &((*consdata)->representativeofnode), tcliqueGetNNodes((*consdata)->graph));
297  tcliqueFree(&((*consdata)->cgraph));
298  }
299  else
300  {
301  if ((*consdata)->created)
302  {
303  for ( i = tcliqueGetNNodes((*consdata)->graph)-1; i >= 0; i-- )
304  {
305  if ( (*consdata)->nnodesinunion[i] > 0 )
306  {
307  SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode[i]), (*consdata)->nnodesinunion[i]); /*lint !e866*/
308  (*consdata)->unionofnode[i] = NULL;
309  }
310  }
311  SCIPfreeBlockMemoryArray(scip, &((*consdata)->unionofnode), tcliqueGetNNodes((*consdata)->graph));
312  SCIPfreeBlockMemoryArray(scip, &((*consdata)->nnodesinunion), tcliqueGetNNodes((*consdata)->graph));
313  SCIPfreeBlockMemoryArray(scip, &((*consdata)->representativeofnode), tcliqueGetNNodes((*consdata)->graph));
314
315  (*consdata)->unionofnode = NULL;
316  (*consdata)->representativeofnode = NULL;
317  (*consdata)->nnodesinunion = NULL;
318
319  if ((*consdata)->graph != NULL)
320  {
321  tcliqueFree(&((*consdata)->graph));
322  }
323  if ((*consdata)->cgraph != NULL)
324  {
325  tcliqueFree(&((*consdata)->cgraph));
326  }
327  }
328  }
329  SCIPfreeBlockMemory(scip, consdata);
330
331  return SCIP_OKAY;
332 }
333
334
335 /** constraint enforcing method of constraint handler for LP solutions */
336 static
337 SCIP_DECL_CONSENFOLP(consEnfolpStoreGraph)
338 {
339  assert(scip != NULL);
340  assert(conshdlr != NULL);
341  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
342  assert(result != NULL);
343
344  /* do nothing */
345  *result = SCIP_FEASIBLE;
346
347  return SCIP_OKAY;
348 }/*lint !e715*/
349
350
351 /** constraint enforcing method of constraint handler for pseudo solutions */
352 static
353 SCIP_DECL_CONSENFOPS(consEnfopsStoreGraph)
354 {
355  assert(scip != NULL);
356  assert(conshdlr != NULL);
357  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
358  assert(result != NULL);
359
360  /* do nothing */
361  *result = SCIP_FEASIBLE;
362
363  return SCIP_OKAY;
364 }/*lint !e715*/
365
366
367 /** feasibility check method of constraint handler for integral solutions */
368 static
369 SCIP_DECL_CONSCHECK(consCheckStoreGraph)
370 {
371  assert(scip != NULL);
372  assert(conshdlr != NULL);
373  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
374  assert(result != NULL);
375
376  /* do nothing */
377  *result = SCIP_FEASIBLE;
378
379  return SCIP_OKAY;
380 }/*lint !e715*/
381
382
383 /** variable rounding lock method of constraint handler */
384 static
385 SCIP_DECL_CONSLOCK(consLockStoreGraph)
386 {
387  assert(scip != NULL);
388  assert(conshdlr != NULL);
389  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
390  assert(cons != NULL);
391
392  SCIPdebugMessage("Locking method for store graph constraint: <%s>.\n", SCIPconsGetName(cons));
393
394  return SCIP_OKAY;
395 }/*lint !e715*/
396
397
398 /** constraint activation notification method of constraint handler */
399 static
400 SCIP_DECL_CONSACTIVE(consActiveStoreGraph)
401 {
402  SCIP_CONSHDLRDATA* conshdlrData;
403  SCIP_CONSDATA* consdata;
404  SCIP_CONSDATA* olddata;
405  TCLIQUE_GRAPH* fathergraph;
406  int i;
407  int j;
408  int* firstedge;
409  int* lastedge;
410  int inserted;
411  int nnodes;
412
413  assert(conshdlr != NULL);
414  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
415  assert(cons != NULL);
416
417  conshdlrData = SCIPconshdlrGetData(conshdlr);
418  assert(conshdlrData != NULL);
419  assert(conshdlrData->stack != NULL);
420
421  consdata = SCIPconsGetData(cons);
422  assert(consdata != NULL);
423  assert((consdata->type == COLOR_CONSTYPE_ROOT) || (consdata->fathercons != NULL));
424
425  SCIPdebugMessage("Activating store graph constraint: <%s(%d,%d)> [stack size: %d].\n", SCIPconsGetName(cons),
426  (consdata->node1+1), (consdata->node2+1), conshdlrData->nstack+1);
427
428  /* put constraint on the stack */
429  if ( conshdlrData->nstack >= conshdlrData->maxstacksize )
430  {
431  int newsize = SCIPcalcMemGrowSize(scip, conshdlrData->nstack + 1);
432
433  SCIPdebugMessage("reallocating Memory for stack! %d --> %d\n", conshdlrData->maxstacksize, newsize);
434
435  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(conshdlrData->stack), conshdlrData->maxstacksize, newsize) ); /*lint !e715 !e647*/
436  conshdlrData->maxstacksize = newsize;
437  }
438  conshdlrData->stack[conshdlrData->nstack] = cons;
439  ++(conshdlrData->nstack);
440
441  /* if the current graph was not yet created, create it now */
442  if ( consdata->created == FALSE )
443  {
444  consdata->created = TRUE;
445  olddata = SCIPconsGetData(consdata->fathercons);
446  assert((consdata->type == COLOR_CONSTYPE_ROOT)
447  || (consdata->node1 == olddata->representativeofnode[consdata->node1]
448  && consdata->node2 == olddata->representativeofnode[consdata->node2]));
449  nnodes = tcliqueGetNNodes(olddata->graph);
450  fathergraph = olddata->graph;
451
452  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->representativeofnode), nnodes) );
453  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->nnodesinunion), nnodes) );
454  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->unionofnode), nnodes) );
455
456  for ( i = 0; i < nnodes; i++ )
457  {
458  consdata->representativeofnode[i] = olddata->representativeofnode[i];
459  consdata->nnodesinunion[i] = olddata->nnodesinunion[i];
460  if ( consdata->nnodesinunion[i] > 0 )
461  {
462  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->unionofnode[i]), consdata->nnodesinunion[i]) ); /*lint !e866*/
463  for ( j = 0; j < consdata->nnodesinunion[i]; j++ )
464  {
465  consdata->unionofnode[i][j] = olddata->unionofnode[i][j];
466  }
467  }
468  }
469
470  /* copy the graph */
471  if( !tcliqueCreate(&(consdata->graph)) )
472  {
473  SCIPerrorMessage("could not flush the clique graph\n");
474  return SCIP_ERROR;
475  }
476
477  if( !tcliqueAddNode((consdata)->graph, nnodes-1, 0) )
478  {
479  SCIPerrorMessage("could not add a node to the clique graph\n");
480  return SCIP_ERROR;
481  }
482
483  for ( i = 0; i < nnodes; i++ )
484  {
485  /* get adjacent nodes for node i and add them to new graph*/
488  while ( firstedge <= lastedge )
489  {
490  if ( *firstedge > i )
491  {
492  if( !tcliqueAddEdge(consdata->graph, i, *firstedge) )
493  {
494  SCIPerrorMessage("could not add an edge to the clique graph\n");
495  return SCIP_ERROR;
496  }
497  }
498  firstedge++;
499  }
500  }
501
502  if( !tcliqueFlush(consdata->graph) )
503  {
504  SCIPerrorMessage("could not flush the clique graph\n");
505  return SCIP_ERROR;
506  }
507
508  assert(consdata->representativeofnode[consdata->node2] == consdata->node2);
509  assert(consdata->representativeofnode[consdata->node1] == consdata->node1);
510
511  /* type == COLOR_CONSTYPE_DIFFER --> insert edge between node1 and node2 */
512  if (consdata->type == COLOR_CONSTYPE_DIFFER)
513  {
514  for ( i = 0; i < consdata->nnodesinunion[consdata->representativeofnode[consdata->node2]]; i++ )
515  {
516  for ( j = 0; j < consdata->nnodesinunion[consdata->representativeofnode[consdata->node1]]; j++ )
517  {
519  consdata->unionofnode[consdata->representativeofnode[consdata->node2]][i])
520  )
521  {
522  SCIPerrorMessage("could not add an edge to the clique graph\n");
523  return SCIP_ERROR;
524  }
525  }
526  }
527
528  if( !tcliqueFlush(consdata->graph) )
529  {
530  SCIPerrorMessage("could not flush the clique graph\n");
531  return SCIP_ERROR;
532  }
533  }
534  /* type == COLOR_CONSTYPE_SAME --> insert edge (node2, i) - if not yet existing - if there exists an edge (node1, i) and vice versa */
535  else
536  {
537  assert(consdata->type == COLOR_CONSTYPE_SAME);
538  inserted = 0;
539
540  /* add edges from all nodes of union2 to all nodes adjacent to union1 */
541  for ( i = 0; i < consdata->nnodesinunion[consdata->node2]; i++ )
542  {
543  /* set representative of nodes in the union of node2 */
544  consdata->representativeofnode[consdata->unionofnode[consdata->node2][i]] = consdata->node1;
545
546  /* insert edges to all nodes adjacent to node1 */
549  while ( firstedge <= lastedge )
550  {
551  if ( !tcliqueIsEdge(fathergraph, *firstedge, consdata->node2) )
552  {
553  if( !tcliqueAddEdge(consdata->graph, consdata->unionofnode[consdata->node2][i], *firstedge) )
554  {
555  SCIPerrorMessage("could not add an edge to the clique graph\n");
556  return SCIP_ERROR;
557  }
558  inserted++;
559  }
560  firstedge++;
561  }
562  }
563  /* add edges from all nodes of union1 to all nodes adjacent to union2 */
564  for ( i = 0; i < consdata->nnodesinunion[consdata->node1]; i++ )
565  {
566  /* insert edges to all nodes adjacent to node2 */
569  while ( firstedge <= lastedge )
570  {
571  if ( !tcliqueIsEdge(fathergraph, *firstedge, consdata->node1) )
572  {
573  if( ! tcliqueAddEdge(consdata->graph, consdata->unionofnode[consdata->node1][i], *firstedge) )
574  {
575  SCIPerrorMessage("could not add an edge to the clique graph\n");
576  return SCIP_ERROR;
577  }
578  inserted++;
579  }
580  firstedge++;
581  }
582  }
583  if ( inserted > 0 )
584  {
585  if( !tcliqueFlush(consdata->graph) )
586  {
587  SCIPerrorMessage("could not flush the clique graph\n");
588  return SCIP_ERROR;
589  }
590  }
591
592  /* update union represented by node1 */
593  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(consdata->unionofnode[consdata->node1]),
594  consdata->nnodesinunion[consdata->node1],
595  (consdata->nnodesinunion[consdata->node1]) + (consdata->nnodesinunion[consdata->node2])) ); /*lint !e866*/
596  for ( i = 0; i < consdata->nnodesinunion[consdata->node2]; i ++ )
597  {
598  consdata->unionofnode[consdata->node1][consdata->nnodesinunion[consdata->node1]+i]
599  = consdata->unionofnode[consdata->node2][i];
600  }
601  SCIPfreeBlockMemoryArray(scip, &(consdata->unionofnode[consdata->node2]),
602  consdata->nnodesinunion[consdata->node2]); /*lint !e866*/
603  consdata->nnodesinunion[consdata->node1] =
604  (consdata->nnodesinunion[consdata->node1]) + (consdata->nnodesinunion[consdata->node2]);
605  consdata->nnodesinunion[consdata->node2] = 0;
606  consdata->unionofnode[consdata->node2] = NULL;
607
608  /* the constraint associated to node2 can be removed from this branch-and-bound node and its subtree */
609  SCIP_CALL( SCIPdelConsLocal(scip, COLORprobGetConstraint(scip, consdata->node2)));
610  }
611
612  /* create the complementary graph */
613  if( !tcliqueCreate(&(consdata->cgraph)) )
614  {
615  SCIPerrorMessage("could not flush the clique graph\n");
616  return SCIP_ERROR;
617  }
618  assert(consdata->cgraph != NULL);
619  SCIP_CALL( COLORprobGetComplementaryGraph(scip, consdata->graph, consdata->cgraph) );
620  }
621  /* if new variables where created after the last propagation of this cons, repropagate it */
622  else
623  {
624  if ( (consdata->type != COLOR_CONSTYPE_ROOT) && (consdata->propagatedvars < SCIPgetNTotalVars(scip)) )
625  {
626  SCIP_CALL( SCIPrepropagateNode(scip, consdata->stickingatnode) );
627  }
628  }
629
630  return SCIP_OKAY;
631 }
632
633
634
635 /** constraint deactivation notification method of constraint handler */
636 static
637 SCIP_DECL_CONSDEACTIVE(consDeactiveStoreGraph)
638 {
639  SCIP_CONSHDLRDATA* conshdlrData;
640 #ifdef SCIP_DEBUG
641  SCIP_CONSDATA* consdata;
642 #endif
643
644  assert(scip != NULL);
645  assert(conshdlr != NULL);
646  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
647  assert(cons != NULL);
648
649  conshdlrData = SCIPconshdlrGetData(conshdlr);
650  assert(conshdlrData != NULL);
651  assert(conshdlrData->stack != NULL);
652  assert(conshdlrData->nstack > 0);
653  assert(cons == conshdlrData->stack[conshdlrData->nstack-1]);
654
655 #ifdef SCIP_DEBUG
656  consdata = SCIPconsGetData(cons);
657
658  SCIPdebugMessage("Deactivating store graph constraint: <%s(%d,%d)> [stack size: %d].\n", SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1), conshdlrData->nstack-1);
659 #endif
660
661  /* remove constraint from the stack */
662  --conshdlrData->nstack;
663
664  return SCIP_OKAY;
665 }
666
667
668
669 /** domain propagation method of constraint handler */
670 static
671 SCIP_DECL_CONSPROP(consPropStoreGraph)
672 {
673  SCIP_CONSHDLRDATA* conshdlrData;
674  SCIP_CONS* cons;
675  SCIP_CONSDATA* consdata;
676  SCIP_VAR* var;
677  int** sets;
678  int* nsetelements;
679  int nsets;
680  int i;
681  int propcount;
682
683  assert(conshdlr != NULL);
684  conshdlrData = SCIPconshdlrGetData(conshdlr);
685  assert(conshdlrData != NULL);
686  assert(conshdlrData->stack != NULL);
687
688  /* get all stable sets */
689  COLORprobGetStableSets(scip, &sets, &nsetelements, &nsets);
690  *result = SCIP_DIDNOTFIND;
691  propcount = 0;
692
693  /* the constraint data of the cons related to the current node */
694  cons = conshdlrData->stack[conshdlrData->nstack-1];
695  consdata = SCIPconsGetData(cons);
696
697  SCIPdebugMessage( "Starting propagation of store graph constraint <%s(%d,%d)> .\n", SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1));
698
699  /* propagation for differ: set upper bound to 0 for all stable sets, which contain both nodes */
700  if (consdata->type == COLOR_CONSTYPE_DIFFER)
701  {
702  for ( i = 0; i < nsets; i++ )
703  {
705  {
706  if ( COLORprobIsNodeInStableSet(scip, i, consdata->node1) && COLORprobIsNodeInStableSet(scip, i, consdata->node2) )
707  {
708  var = COLORprobGetVarForStableSet(scip, i);
709  SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
710  propcount++;
711  }
712  }
713  }
714  }
715
716  /* propagation for same: set upper bound to 0 for all stable sets, which do not contain both nodes */
717  if ( consdata->type == COLOR_CONSTYPE_SAME )
718  {
719  for ( i = 0; i < nsets; i++ )
720  {
722  {
723  if ( (COLORprobIsNodeInStableSet(scip, i, consdata->node1) || COLORprobIsNodeInStableSet(scip, i, consdata->node2))
724  && !(COLORprobIsNodeInStableSet(scip, i, consdata->node1) && COLORprobIsNodeInStableSet(scip, i, consdata->node2)) )
725  {
726  var = COLORprobGetVarForStableSet(scip, i);
727  SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
728  propcount++;
729  }
730  }
731  }
732  }
733
734  SCIPdebugMessage( "Finished propagation of store graph constraint <%s(%d,%d)>, %d vars fixed.\n", SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1), propcount);
735
737  consdata->propagatedvars = SCIPgetNTotalVars(scip);
738
739  return SCIP_OKAY;
740 }/*lint !e715*/
741
742 /*
743  * interface methods
744  */
745
746
747 /** creates the handler for storeGraph constraints and includes it in SCIP */
749  SCIP* scip /**< SCIP data structure */
750  )
751 {
752  SCIP_CONSHDLRDATA* conshdlrData;
753  SCIP_CONSHDLR* conshdlr;
754
755  SCIPdebugMessage("Including graph storage constraint handler.\n");
756
757  SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrData) );
758  conshdlrData->stack = NULL;
759  conshdlrData->nstack = 0;
760  conshdlrData->maxstacksize = 25;
761
762  conshdlr = NULL;
763  /* include constraint handler */
766  consEnfolpStoreGraph, consEnfopsStoreGraph, consCheckStoreGraph, consLockStoreGraph,
767  conshdlrData) );
768  assert(conshdlr != NULL);
769
770  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteStoreGraph) );
771  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeStoreGraph) );
772  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolStoreGraph) );
773  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolStoreGraph) );
774  SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveStoreGraph) );
775  SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveStoreGraph) );
776  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropStoreGraph, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
778
779  return SCIP_OKAY;
780 }
781
782 /** creates and captures a storeGraph constraint, uses knowledge of the B&B-father*/
784  SCIP* scip, /**< SCIP data structure */
785  SCIP_CONS** cons, /**< pointer to hold the created constraint */
786  const char* name, /**< name of constraint */
787  SCIP_CONS* fatherconstraint, /**< constraint in B&B-father */
788  COLOR_CONSTYPE type, /**< type of the constraint: COLOR_CONSTYPE_SAME or COLOR_CONSTYPE_DIFFER */
789  int node1, /**< the first node of the constraint */
790  int node2, /**< the second node of the constraint */
791  SCIP_NODE* stickingnode /**< the B&B-tree node at which the constraint will be sticking */
792  )
793 {
794  SCIP_CONSHDLR* conshdlr;
795  SCIP_CONSDATA* consdata;
796  int temp;
797
798  assert(scip != NULL);
799  assert(fatherconstraint != NULL);
800  assert(type == COLOR_CONSTYPE_SAME || type == COLOR_CONSTYPE_DIFFER);
801  assert(stickingnode != NULL);
802
803  /* find the storeGraph constraint handler */
804  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
805  if ( conshdlr == NULL )
806  {
808  return SCIP_PLUGINNOTFOUND;
809  }
810
811  /* create constraint data */
812  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
813
814  if ( node1 > node2 )
815  {
816  temp = node1;
817  node1 = node2;
818  node2 = temp;
819  }
820  SCIPdebugMessage("Creating store graph constraint: <%s(%d,%d)>. \n", name, (node1+1), (node2+1));
821
822  consdata->node1 = node1;
823  consdata->node2 = node2;
824  consdata->type = type;
825  consdata->fathercons = fatherconstraint;
826  consdata->propagatedvars = 0;
827  consdata->stickingatnode = stickingnode;
828  consdata->created = FALSE;
829
830
831  /* create constraint */
832  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, FALSE, FALSE, FALSE, FALSE, TRUE,
833  TRUE, FALSE, TRUE, FALSE, TRUE) );
834
835  return SCIP_OKAY;
836 }
837
838
839
840
841 /* ----------------------------------- external methods -------------------------- */
842
843 /** returns the store graph constraint of the current node, needs the pointer to the constraint handler */
845  SCIP_CONSHDLR* conshdlr /**< constaint handler for store-graph constraints */
846  )
847 {
848  SCIP_CONSHDLRDATA* conshdlrData;
849
850  assert(conshdlr != NULL);
851  conshdlrData = SCIPconshdlrGetData(conshdlr);
852  assert(conshdlrData != NULL);
853  assert(conshdlrData->stack != NULL);
854
855  return conshdlrData->stack[conshdlrData->nstack-1];
856 }
857
858
859 /** returns the store graph constraint of the current node, only needs the pointer to scip */
861  SCIP* scip /**< SCIP data structure */
862  )
863 {
864  SCIP_CONSHDLR* conshdlr;
865  SCIP_CONSHDLRDATA* conshdlrData;
866
867  assert(scip != NULL);
868  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
869  if ( conshdlr == NULL )
870  {
872  return NULL;
873  }
874  conshdlrData = SCIPconshdlrGetData(conshdlr);
875  assert(conshdlrData != NULL);
876  assert(conshdlrData->stack != NULL);
877  assert(conshdlrData->nstack > 0);
878
879  return conshdlrData->stack[conshdlrData->nstack-1];
880 }
881
882
883 /** returns the current graph */
885  SCIP* scip /**< SCIP data structure */
886  )
887 {
888  SCIP_CONSHDLR* conshdlr;
889  SCIP_CONS* cons;
890  SCIP_CONSDATA* consdata;
891  SCIP_CONSHDLRDATA* conshdlrData;
892
893  assert(scip != NULL);
894  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
895  if ( conshdlr == NULL )
896  {
898  return NULL;
899  }
900  conshdlrData = SCIPconshdlrGetData(conshdlr);
901  assert(conshdlrData != NULL);
902  assert(conshdlrData->stack != NULL);
903  cons = conshdlrData->stack[conshdlrData->nstack-1];
904  assert(cons != NULL);
905
906  consdata = SCIPconsGetData(cons);
907  return consdata->graph;
908 }
909
910
911 /** returns the complementary graph */
913  SCIP* scip /**< SCIP data structure */
914  )
915 {
916  SCIP_CONSHDLR* conshdlr;
917  SCIP_CONS* cons;
918  SCIP_CONSDATA* consdata;
919  SCIP_CONSHDLRDATA* conshdlrData;
920
921  assert(scip != NULL);
922
923  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
924  if ( conshdlr == NULL )
925  {
927  return NULL;
928  }
929
930  conshdlrData = SCIPconshdlrGetData(conshdlr);
931  assert(conshdlrData != NULL);
932  assert(conshdlrData->stack != NULL);
933
934  cons = conshdlrData->stack[conshdlrData->nstack-1];
935  assert(cons != NULL);
936
937  consdata = SCIPconsGetData(cons);
938  return consdata->cgraph;
939 }
940
941
942 /** returns array of representatives of all nodes */
944  SCIP* scip /**< SCIP data structure */
945  )
946 {
947  SCIP_CONSHDLR* conshdlr;
948  SCIP_CONSHDLRDATA* conshdlrData;
949  SCIP_CONS* cons;
950  SCIP_CONSDATA* consdata;
951
952  assert(scip != NULL);
953
954  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
955  if ( conshdlr == NULL )
956  {
958  return NULL;
959  }
960
961  conshdlrData = SCIPconshdlrGetData(conshdlr);
962  assert(conshdlrData != NULL);
963  assert(conshdlrData->stack != NULL);
964
965  cons = conshdlrData->stack[conshdlrData->nstack-1];
966  consdata = SCIPconsGetData(cons);
967  return consdata->representativeofnode;
968 }
969
970 /** returns the representative of the union which contains a given node */
972  SCIP* scip, /**< SCIP data structure */
973  int node /**< the node, for wich the representative is searched */
974  )
975 {
976  SCIP_CONSHDLR* conshdlr;
977  SCIP_CONSHDLRDATA* conshdlrData;
978  SCIP_CONS* cons;
979  SCIP_CONSDATA* consdata;
980
981  assert(scip != NULL);
982
983  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
984  if ( conshdlr == NULL )
985  {
987  return -1;
988  }
989
990  conshdlrData = SCIPconshdlrGetData(conshdlr);
991  assert(conshdlrData != NULL);
992  assert(conshdlrData->stack != NULL);
993
994  cons = conshdlrData->stack[conshdlrData->nstack-1];
995  consdata = SCIPconsGetData(cons);
996  assert(consdata != NULL);
997
998  assert(node >= 0 && node < tcliqueGetNNodes(consdata->graph));
999
1000  return consdata->representativeofnode[node];
1001 }
1002
1003 /** returns the array of all unions, a union is saved in the array at the position of its representative */
1004 void COLORconsGetUnions(
1005  SCIP* scip, /**< SCIP data structure */
1006  int*** unions, /**< output: array containing array which contains nodes in the union */
1007  int** lengths /**< output: lengths of the unions */
1008  )
1009 {
1010  SCIP_CONSHDLR* conshdlr;
1011  SCIP_CONSHDLRDATA* conshdlrData;
1012  SCIP_CONS* cons;
1013  SCIP_CONSDATA* consdata;
1014
1015  assert(scip != NULL);
1016  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
1017  if ( conshdlr == NULL )
1018  {
1020  return;
1021  }
1022
1023  conshdlrData = SCIPconshdlrGetData(conshdlr);
1024  assert(conshdlrData != NULL);
1025  assert(conshdlrData->stack != NULL);
1026
1027  cons = conshdlrData->stack[conshdlrData->nstack-1];
1028  consdata = SCIPconsGetData(cons);
1029  assert(consdata != NULL);
1030
1031  *unions = consdata->unionofnode;
1032  *lengths = consdata->nnodesinunion;
1033 }
1034
1035 /** returns the union which has a given node as representative */
1036 void COLORconsGetUnion(
1037  SCIP* scip, /**< SCIP data structure */
1038  int** nodesinunion, /**< output: array containig nodes in the union */
1039  int* nnodesinunion, /**< output: length of the union */
1040  int node /**< the node, whose union we want to get */
1041  )
1042 {
1043  SCIP_CONSHDLR* conshdlr;
1044  SCIP_CONSHDLRDATA* conshdlrData;
1045  SCIP_CONS* cons;
1046  SCIP_CONSDATA* consdata;
1047
1048  assert(scip != NULL);
1049  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
1050  if ( conshdlr == NULL )
1051  {
1053  return;
1054  }
1055  conshdlrData = SCIPconshdlrGetData(conshdlr);
1056  assert(conshdlrData != NULL);
1057  assert(conshdlrData->stack != NULL);
1058  cons = conshdlrData->stack[conshdlrData->nstack-1];
1059  consdata = SCIPconsGetData(cons);
1060  assert(consdata != NULL);
1061
1062  *nodesinunion = consdata->unionofnode[node];
1063  *nnodesinunion = consdata->nnodesinunion[node];
1064 }
1065
1066 /** returns the stack and the number of elements on it */
1067 void COLORconsGetStack(
1068  SCIP* scip, /**< SCIP data structure */
1069  SCIP_CONS*** stack, /**< return value: pointer to the stack */
1070  int* nstackelements /**< return value: pointer to int, for number of elements on the stack */
1071  )
1072 {
1073  SCIP_CONSHDLR* conshdlr;
1074  SCIP_CONSHDLRDATA* conshdlrData;
1075
1076  assert(scip != NULL);
1077  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
1078  if ( conshdlr == NULL )
1079  {
1081  return;
1082  }
1083  conshdlrData = SCIPconshdlrGetData(conshdlr);
1084  assert(conshdlrData != NULL);
1085  assert(conshdlrData != NULL);
1086  assert(conshdlrData->stack != NULL);
1087
1088  *stack = conshdlrData->stack;
1089  *nstackelements = conshdlrData->nstack;
1090 }
1091
1092
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
#define CONSHDLR_PROPFREQ
SCIP_CONS * COLORconsGetActiveStoreGraphConsFromHandler(SCIP_CONSHDLR *conshdlr)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:90
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:563
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
void COLORconsGetStack(SCIP *scip, SCIP_CONS ***stack, int *nstackelements)
TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:40
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
problem data for vertex coloring algorithm
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:130
SCIP_CONS * COLORconsGetActiveStoreGraphCons(SCIP *scip)
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDEACTIVE((*consdeactive)))
Definition: scip_cons.c:678
SCIP_RETCODE COLORincludeConshdlrStoreGraph(SCIP *scip)
static SCIP_RETCODE createConsStoreGraphAtRoot(SCIP *scip, SCIP_CONS **cons, const char *name, TCLIQUE_GRAPH *graph)
#define CONSHDLR_NAME
static SCIP_DECL_CONSEXITSOL(consExitsolStoreGraph)
#define CONSHDLR_EAGERFREQ
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:166
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
file reader for vertex coloring instances
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
#define SCIPdebugMessage
Definition: pub_message.h:87
tclique user interface
constraint handler for storing the graph at each node of the tree
static SCIP_DECL_CONSDELETE(consDeleteStoreGraph)
#define CONSHDLR_ENFOPRIORITY
#define CONSHDLR_PROP_TIMING
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip_cons.c:934
SCIP_RETCODE SCIPrepropagateNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:468
unsigned int stickingatnode
Definition: struct_cons.h:70
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:429
SCIP_CONS * COLORprobGetConstraint(SCIP *scip, int node)
TCLIQUE_GRAPH * COLORprobGetGraph(SCIP *scip)
static SCIP_DECL_CONSCHECK(consCheckStoreGraph)
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
#define SCIPerrorMessage
Definition: pub_message.h:55
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4175
int COLORconsGetRepresentative(SCIP *scip, int node)
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3473
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8085
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4763
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:357
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4195
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
int SCIPgetNTotalVars(SCIP *scip)
Definition: scip_prob.c:2568
#define CONSHDLR_NEEDSCONS
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
static SCIP_DECL_CONSLOCK(consLockStoreGraph)
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:56
void COLORconsGetUnion(SCIP *scip, int **nodesinunion, int *nnodesinunion, int node)
#define SCIP_Bool
Definition: def.h:84
SCIP_Bool COLORprobIsNodeInStableSet(SCIP *scip, int setindex, int node)
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
SCIP_RETCODE COLORprobGetComplementaryGraph(SCIP *scip, TCLIQUE_GRAPH *graph, TCLIQUE_GRAPH *cgraph)
static SCIP_DECL_CONSDEACTIVE(consDeactiveStoreGraph)
static SCIP_DECL_CONSENFOLP(consEnfolpStoreGraph)
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
static SCIP_DECL_CONSINITSOL(consInitsolStoreGraph)
int * COLORconsGetRepresentatives(SCIP *scip)
Constraint handler for linear constraints in their most general form, .
#define CONSHDLR_CHECKPRIORITY
#define CONSHDLR_DELAYPROP
TCLIQUE_GRAPH * COLORconsGetComplementaryGraph(SCIP *scip)
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8115
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
static SCIP_DECL_CONSENFOPS(consEnfopsStoreGraph)
enum COLOR_ConsType COLOR_CONSTYPE
static SCIP_DECL_CONSPROP(consPropStoreGraph)
#define CONSHDLR_DESC
SCIP_RETCODE COLORcreateConsStoreGraph(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONS *fatherconstraint, COLOR_CONSTYPE type, int node1, int node2, SCIP_NODE *stickingnode)
static SCIP_DECL_CONSFREE(consFreeStoreGraph)
TCLIQUE_Bool tcliqueFlush(TCLIQUE_GRAPH *tcliquegraph)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:55
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
#define nnodes
Definition: gastrans.c:65
void COLORconsGetUnions(SCIP *scip, int ***unions, int **lengths)
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSACTIVE((*consactive)))
Definition: scip_cons.c:655
SCIPallocBlockMemory(scip, subsol))
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:453
static SCIP_DECL_CONSACTIVE(consActiveStoreGraph)
type definitions for constraints and constraint handlers
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:266