Scippy

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 /* */
6 /* Copyright (C) 2002-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
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"
66 #include "reader_col.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? */
80 
81 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
82 
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  {
138  SCIPerrorMessage("storeGraph constraint handler not found\n");
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*/
486  firstedge = tcliqueGetFirstAdjedge(fathergraph, i);
487  lastedge = tcliqueGetLastAdjedge(fathergraph, i);
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  {
518  if( !tcliqueAddEdge(consdata->graph, consdata->unionofnode[consdata->representativeofnode[consdata->node1]][j],
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 */
547  firstedge = tcliqueGetFirstAdjedge(fathergraph, consdata->node1);
548  lastedge = tcliqueGetLastAdjedge(fathergraph, consdata->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 */
567  firstedge = tcliqueGetFirstAdjedge(fathergraph, consdata->node2);
568  lastedge = tcliqueGetLastAdjedge(fathergraph, consdata->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 
609  /* create the complementary graph */
610  if( !tcliqueCreate(&(consdata->cgraph)) )
611  {
612  SCIPerrorMessage("could not flush the clique graph\n");
613  return SCIP_ERROR;
614  }
615  assert(consdata->cgraph != NULL);
616  SCIP_CALL( COLORprobGetComplementaryGraph(scip, consdata->graph, consdata->cgraph) );
617  }
618  /* if new variables where created after the last propagation of this cons, repropagate it */
619  else
620  {
621  if ( (consdata->type != COLOR_CONSTYPE_ROOT) && (consdata->propagatedvars < SCIPgetNTotalVars(scip)) )
622  {
623  SCIP_CALL( SCIPrepropagateNode(scip, consdata->stickingatnode) );
624  }
625  }
626 
627  return SCIP_OKAY;
628 }
629 
630 
631 
632 /** constraint deactivation notification method of constraint handler */
633 static
634 SCIP_DECL_CONSDEACTIVE(consDeactiveStoreGraph)
635 {
636  SCIP_CONSHDLRDATA* conshdlrData;
637 #ifdef SCIP_DEBUG
638  SCIP_CONSDATA* consdata;
639 #endif
640 
641  assert(scip != NULL);
642  assert(conshdlr != NULL);
643  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
644  assert(cons != NULL);
645 
646  conshdlrData = SCIPconshdlrGetData(conshdlr);
647  assert(conshdlrData != NULL);
648  assert(conshdlrData->stack != NULL);
649  assert(conshdlrData->nstack > 0);
650  assert(cons == conshdlrData->stack[conshdlrData->nstack-1]);
651 
652 #ifdef SCIP_DEBUG
653  consdata = SCIPconsGetData(cons);
654 
655  SCIPdebugMessage("Deactivating store graph constraint: <%s(%d,%d)> [stack size: %d].\n", SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1), conshdlrData->nstack-1);
656 #endif
657 
658  /* remove constraint from the stack */
659  --conshdlrData->nstack;
660 
661  return SCIP_OKAY;
662 }
663 
664 
665 
666 /** domain propagation method of constraint handler */
667 static
668 SCIP_DECL_CONSPROP(consPropStoreGraph)
669 {
670  SCIP_CONSHDLRDATA* conshdlrData;
671  SCIP_CONS* cons;
672  SCIP_CONSDATA* consdata;
673  SCIP_VAR* var;
674  int** sets;
675  int* nsetelements;
676  int nsets;
677  int i;
678  int propcount;
679 
680  assert(conshdlr != NULL);
681  conshdlrData = SCIPconshdlrGetData(conshdlr);
682  assert(conshdlrData != NULL);
683  assert(conshdlrData->stack != NULL);
684 
685  /* get all stable sets */
686  COLORprobGetStableSets(scip, &sets, &nsetelements, &nsets);
687  *result = SCIP_DIDNOTFIND;
688  propcount = 0;
689 
690  /* the constraint data of the cons related to the current node */
691  cons = conshdlrData->stack[conshdlrData->nstack-1];
692  consdata = SCIPconsGetData(cons);
693 
694  SCIPdebugMessage( "Starting propagation of store graph constraint <%s(%d,%d)> .\n", SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1));
695 
696  /* propagation for differ: set upper bound to 0 for all stable sets, which contain both nodes */
697  if (consdata->type == COLOR_CONSTYPE_DIFFER)
698  {
699  for ( i = 0; i < nsets; i++ )
700  {
702  {
703  if ( COLORprobIsNodeInStableSet(scip, i, consdata->node1) && COLORprobIsNodeInStableSet(scip, i, consdata->node2) )
704  {
705  var = COLORprobGetVarForStableSet(scip, i);
706  SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
707  propcount++;
708  }
709  }
710  }
711  }
712 
713  /* propagation for same: set upper bound to 0 for all stable sets, which do not contain both nodes */
714  if ( consdata->type == COLOR_CONSTYPE_SAME )
715  {
716  for ( i = 0; i < nsets; i++ )
717  {
719  {
720  if ( (COLORprobIsNodeInStableSet(scip, i, consdata->node1) || COLORprobIsNodeInStableSet(scip, i, consdata->node2))
721  && !(COLORprobIsNodeInStableSet(scip, i, consdata->node1) && COLORprobIsNodeInStableSet(scip, i, consdata->node2)) )
722  {
723  var = COLORprobGetVarForStableSet(scip, i);
724  SCIP_CALL( SCIPchgVarUb(scip, var, 0.0) );
725  propcount++;
726  }
727  }
728  }
729  }
730 
731  SCIPdebugMessage( "Finished propagation of store graph constraint <%s(%d,%d)>, %d vars fixed.\n", SCIPconsGetName(cons), (consdata->node1+1), (consdata->node2+1), propcount);
732 
734  consdata->propagatedvars = SCIPgetNTotalVars(scip);
735 
736  return SCIP_OKAY;
737 }/*lint !e715*/
738 
739 /*
740  * interface methods
741  */
742 
743 
744 /** creates the handler for storeGraph constraints and includes it in SCIP */
746  SCIP* scip /**< SCIP data structure */
747  )
748 {
749  SCIP_CONSHDLRDATA* conshdlrData;
750  SCIP_CONSHDLR* conshdlr;
751 
752  SCIPdebugMessage("Including graph storage constraint handler.\n");
753 
754  SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrData) );
755  conshdlrData->stack = NULL;
756  conshdlrData->nstack = 0;
757  conshdlrData->maxstacksize = 25;
758 
759  conshdlr = NULL;
760  /* include constraint handler */
763  consEnfolpStoreGraph, consEnfopsStoreGraph, consCheckStoreGraph, consLockStoreGraph,
764  conshdlrData) );
765  assert(conshdlr != NULL);
766 
767  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteStoreGraph) );
768  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeStoreGraph) );
769  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolStoreGraph) );
770  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolStoreGraph) );
771  SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveStoreGraph) );
772  SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveStoreGraph) );
773  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropStoreGraph, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
775 
776  return SCIP_OKAY;
777 }
778 
779 /** creates and captures a storeGraph constraint, uses knowledge of the B&B-father*/
781  SCIP* scip, /**< SCIP data structure */
782  SCIP_CONS** cons, /**< pointer to hold the created constraint */
783  const char* name, /**< name of constraint */
784  SCIP_CONS* fatherconstraint, /**< constraint in B&B-father */
785  COLOR_CONSTYPE type, /**< type of the constraint: COLOR_CONSTYPE_SAME or COLOR_CONSTYPE_DIFFER */
786  int node1, /**< the first node of the constraint */
787  int node2, /**< the second node of the constraint */
788  SCIP_NODE* stickingnode /**< the B&B-tree node at which the constraint will be sticking */
789  )
790 {
791  SCIP_CONSHDLR* conshdlr;
792  SCIP_CONSDATA* consdata;
793  int temp;
794 
795  assert(scip != NULL);
796  assert(fatherconstraint != NULL);
797  assert(type == COLOR_CONSTYPE_SAME || type == COLOR_CONSTYPE_DIFFER);
798  assert(stickingnode != NULL);
799 
800  /* find the storeGraph constraint handler */
801  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
802  if ( conshdlr == NULL )
803  {
804  SCIPerrorMessage("storeGraph constraint handler not found\n");
805  return SCIP_PLUGINNOTFOUND;
806  }
807 
808  /* create constraint data */
809  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
810 
811  if ( node1 > node2 )
812  {
813  temp = node1;
814  node1 = node2;
815  node2 = temp;
816  }
817  SCIPdebugMessage("Creating store graph constraint: <%s(%d,%d)>. \n", name, (node1+1), (node2+1));
818 
819  consdata->node1 = node1;
820  consdata->node2 = node2;
821  consdata->type = type;
822  consdata->fathercons = fatherconstraint;
823  consdata->propagatedvars = 0;
824  consdata->stickingatnode = stickingnode;
825  consdata->created = FALSE;
826 
827 
828  /* create constraint */
829  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, FALSE, FALSE, FALSE, FALSE, TRUE,
830  TRUE, FALSE, TRUE, FALSE, TRUE) );
831 
832  return SCIP_OKAY;
833 }
834 
835 
836 
837 
838 /* ----------------------------------- external methods -------------------------- */
839 
840 /** returns the store graph constraint of the current node, needs the pointer to the constraint handler */
842  SCIP_CONSHDLR* conshdlr /**< constaint handler for store-graph constraints */
843  )
844 {
845  SCIP_CONSHDLRDATA* conshdlrData;
846 
847  assert(conshdlr != NULL);
848  conshdlrData = SCIPconshdlrGetData(conshdlr);
849  assert(conshdlrData != NULL);
850  assert(conshdlrData->stack != NULL);
851 
852  return conshdlrData->stack[conshdlrData->nstack-1];
853 }
854 
855 
856 /** returns the store graph constraint of the current node, only needs the pointer to scip */
858  SCIP* scip /**< SCIP data structure */
859  )
860 {
861  SCIP_CONSHDLR* conshdlr;
862  SCIP_CONSHDLRDATA* conshdlrData;
863 
864  assert(scip != NULL);
865  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
866  if ( conshdlr == NULL )
867  {
868  SCIPerrorMessage("storeGraph constraint handler not found\n");
869  return NULL;
870  }
871  conshdlrData = SCIPconshdlrGetData(conshdlr);
872  assert(conshdlrData != NULL);
873  assert(conshdlrData->stack != NULL);
874  assert(conshdlrData->nstack > 0);
875 
876  return conshdlrData->stack[conshdlrData->nstack-1];
877 }
878 
879 
880 /** returns the current graph */
882  SCIP* scip /**< SCIP data structure */
883  )
884 {
885  SCIP_CONSHDLR* conshdlr;
886  SCIP_CONS* cons;
887  SCIP_CONSDATA* consdata;
888  SCIP_CONSHDLRDATA* conshdlrData;
889 
890  assert(scip != NULL);
891  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
892  if ( conshdlr == NULL )
893  {
894  SCIPerrorMessage("storeGraph constraint handler not found\n");
895  return NULL;
896  }
897  conshdlrData = SCIPconshdlrGetData(conshdlr);
898  assert(conshdlrData != NULL);
899  assert(conshdlrData->stack != NULL);
900  cons = conshdlrData->stack[conshdlrData->nstack-1];
901  assert(cons != NULL);
902 
903  consdata = SCIPconsGetData(cons);
904  return consdata->graph;
905 }
906 
907 
908 /** returns the complementary graph */
910  SCIP* scip /**< SCIP data structure */
911  )
912 {
913  SCIP_CONSHDLR* conshdlr;
914  SCIP_CONS* cons;
915  SCIP_CONSDATA* consdata;
916  SCIP_CONSHDLRDATA* conshdlrData;
917 
918  assert(scip != NULL);
919 
920  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
921  if ( conshdlr == NULL )
922  {
923  SCIPerrorMessage("storeGraph constraint handler not found\n");
924  return NULL;
925  }
926 
927  conshdlrData = SCIPconshdlrGetData(conshdlr);
928  assert(conshdlrData != NULL);
929  assert(conshdlrData->stack != NULL);
930 
931  cons = conshdlrData->stack[conshdlrData->nstack-1];
932  assert(cons != NULL);
933 
934  consdata = SCIPconsGetData(cons);
935  return consdata->cgraph;
936 }
937 
938 
939 /** returns array of representatives of all nodes */
941  SCIP* scip /**< SCIP data structure */
942  )
943 {
944  SCIP_CONSHDLR* conshdlr;
945  SCIP_CONSHDLRDATA* conshdlrData;
946  SCIP_CONS* cons;
947  SCIP_CONSDATA* consdata;
948 
949  assert(scip != NULL);
950 
951  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
952  if ( conshdlr == NULL )
953  {
954  SCIPerrorMessage("storeGraph constraint handler not found\n");
955  return NULL;
956  }
957 
958  conshdlrData = SCIPconshdlrGetData(conshdlr);
959  assert(conshdlrData != NULL);
960  assert(conshdlrData->stack != NULL);
961 
962  cons = conshdlrData->stack[conshdlrData->nstack-1];
963  consdata = SCIPconsGetData(cons);
964  return consdata->representativeofnode;
965 }
966 
967 /** returns the representative of the union which contains a given node */
969  SCIP* scip, /**< SCIP data structure */
970  int node /**< the node, for wich the representative is searched */
971  )
972 {
973  SCIP_CONSHDLR* conshdlr;
974  SCIP_CONSHDLRDATA* conshdlrData;
975  SCIP_CONS* cons;
976  SCIP_CONSDATA* consdata;
977 
978  assert(scip != NULL);
979 
980  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
981  if ( conshdlr == NULL )
982  {
983  SCIPerrorMessage("storeGraph constraint handler not found\n");
984  return -1;
985  }
986 
987  conshdlrData = SCIPconshdlrGetData(conshdlr);
988  assert(conshdlrData != NULL);
989  assert(conshdlrData->stack != NULL);
990 
991  cons = conshdlrData->stack[conshdlrData->nstack-1];
992  consdata = SCIPconsGetData(cons);
993  assert(consdata != NULL);
994 
995  assert(node >= 0 && node < tcliqueGetNNodes(consdata->graph));
996 
997  return consdata->representativeofnode[node];
998 }
999 
1000 /** returns the array of all unions, a union is saved in the array at the position of its representative */
1001 void COLORconsGetUnions(
1002  SCIP* scip, /**< SCIP data structure */
1003  int*** unions, /**< output: array containing array which contains nodes in the union */
1004  int** lengths /**< output: lengths of the unions */
1005  )
1006 {
1007  SCIP_CONSHDLR* conshdlr;
1008  SCIP_CONSHDLRDATA* conshdlrData;
1009  SCIP_CONS* cons;
1010  SCIP_CONSDATA* consdata;
1011 
1012  assert(scip != NULL);
1013  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
1014  if ( conshdlr == NULL )
1015  {
1016  SCIPerrorMessage("storeGraph constraint handler not found\n");
1017  return;
1018  }
1019 
1020  conshdlrData = SCIPconshdlrGetData(conshdlr);
1021  assert(conshdlrData != NULL);
1022  assert(conshdlrData->stack != NULL);
1023 
1024  cons = conshdlrData->stack[conshdlrData->nstack-1];
1025  consdata = SCIPconsGetData(cons);
1026  assert(consdata != NULL);
1027 
1028  *unions = consdata->unionofnode;
1029  *lengths = consdata->nnodesinunion;
1030 }
1031 
1032 /** returns the union which has a given node as representative */
1033 void COLORconsGetUnion(
1034  SCIP* scip, /**< SCIP data structure */
1035  int** nodesinunion, /**< output: array containig nodes in the union */
1036  int* nnodesinunion, /**< output: length of the union */
1037  int node /**< the node, whose union we want to get */
1038  )
1039 {
1040  SCIP_CONSHDLR* conshdlr;
1041  SCIP_CONSHDLRDATA* conshdlrData;
1042  SCIP_CONS* cons;
1043  SCIP_CONSDATA* consdata;
1044 
1045  assert(scip != NULL);
1046  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
1047  if ( conshdlr == NULL )
1048  {
1049  SCIPerrorMessage("storeGraph constraint handler not found\n");
1050  return;
1051  }
1052  conshdlrData = SCIPconshdlrGetData(conshdlr);
1053  assert(conshdlrData != NULL);
1054  assert(conshdlrData->stack != NULL);
1055  cons = conshdlrData->stack[conshdlrData->nstack-1];
1056  consdata = SCIPconsGetData(cons);
1057  assert(consdata != NULL);
1058 
1059  *nodesinunion = consdata->unionofnode[node];
1060  *nnodesinunion = consdata->nnodesinunion[node];
1061 }
1062 
1063 /** returns the stack and the number of elements on it */
1064 void COLORconsGetStack(
1065  SCIP* scip, /**< SCIP data structure */
1066  SCIP_CONS*** stack, /**< return value: pointer to the stack */
1067  int* nstackelements /**< return value: pointer to int, for number of elements on the stack */
1068  )
1069 {
1070  SCIP_CONSHDLR* conshdlr;
1071  SCIP_CONSHDLRDATA* conshdlrData;
1072 
1073  assert(scip != NULL);
1074  conshdlr = SCIPfindConshdlr(scip, "storeGraph");
1075  if ( conshdlr == NULL )
1076  {
1077  SCIPerrorMessage("storeGraph constraint handler not found\n");
1078  return;
1079  }
1080  conshdlrData = SCIPconshdlrGetData(conshdlr);
1081  assert(conshdlrData != NULL);
1082  assert(conshdlrData != NULL);
1083  assert(conshdlrData->stack != NULL);
1084 
1085  *stack = conshdlrData->stack;
1086  *nstackelements = conshdlrData->nstack;
1087 }
1088 
1089 
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
#define CONSHDLR_PROPFREQ
SCIP_CONS * COLORconsGetActiveStoreGraphConsFromHandler(SCIP_CONSHDLR *conshdlr)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:86
#define NULL
Definition: def.h:253
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:876
void COLORconsGetStack(SCIP *scip, SCIP_CONS ***stack, int *nstackelements)
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:452
SCIP_EXPORT TCLIQUE_Bool tcliqueFlush(TCLIQUE_GRAPH *tcliquegraph)
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:933
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:40
SCIP_EXPORT TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
problem data for vertex coloring algorithm
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:165
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSACTIVE((*consactive)))
Definition: scip_cons.c:654
SCIP_CONS * COLORconsGetActiveStoreGraphCons(SCIP *scip)
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
SCIP_EXPORT int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
#define FALSE
Definition: def.h:73
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:562
file reader for vertex coloring instances
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
#define SCIPdebugMessage
Definition: pub_message.h:77
tclique user interface
constraint handler for storing the graph at each node of the tree
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
static SCIP_DECL_CONSDELETE(consDeleteStoreGraph)
#define CONSHDLR_ENFOPRIORITY
#define CONSHDLR_PROP_TIMING
SCIP_EXPORT TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:356
unsigned int stickingatnode
Definition: struct_cons.h:73
TCLIQUE_GRAPH * COLORprobGetGraph(SCIP *scip)
static SCIP_DECL_CONSCHECK(consCheckStoreGraph)
#define SCIPerrorMessage
Definition: pub_message.h:45
int COLORconsGetRepresentative(SCIP *scip, int node)
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:428
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8106
#define SCIP_CALL(x)
Definition: def.h:365
#define CONSHDLR_NEEDSCONS
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
static SCIP_DECL_CONSLOCK(consLockStoreGraph)
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:51
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:129
void COLORconsGetUnion(SCIP *scip, int **nodesinunion, int *nnodesinunion, int node)
#define SCIP_Bool
Definition: def.h:70
SCIP_EXPORT void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
SCIP_Bool COLORprobIsNodeInStableSet(SCIP *scip, int setindex, int node)
SCIP_RETCODE COLORprobGetComplementaryGraph(SCIP *scip, TCLIQUE_GRAPH *graph, TCLIQUE_GRAPH *cgraph)
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4211
static SCIP_DECL_CONSDEACTIVE(consDeactiveStoreGraph)
static SCIP_DECL_CONSENFOLP(consEnfolpStoreGraph)
static SCIP_DECL_CONSINITSOL(consInitsolStoreGraph)
int * COLORconsGetRepresentatives(SCIP *scip)
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4704
#define CONSHDLR_CHECKPRIORITY
#define CONSHDLR_DELAYPROP
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17418
TCLIQUE_GRAPH * COLORconsGetComplementaryGraph(SCIP *scip)
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDEACTIVE((*consdeactive)))
Definition: scip_cons.c:677
static SCIP_DECL_CONSENFOPS(consEnfopsStoreGraph)
enum COLOR_ConsType COLOR_CONSTYPE
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8076
static SCIP_DECL_CONSPROP(consPropStoreGraph)
#define CONSHDLR_DESC
SCIP_RETCODE SCIPrepropagateNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:444
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4191
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)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:50
#define nnodes
Definition: gastrans.c:65
void COLORconsGetUnions(SCIP *scip, int ***unions, int **lengths)
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
SCIP_EXPORT int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1109
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:265
static SCIP_DECL_CONSACTIVE(consActiveStoreGraph)
SCIP_EXPORT TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
type definitions for constraints and constraint handlers
int SCIPgetNTotalVars(SCIP *scip)
Definition: scip_prob.c:2564