SCIP

Solving Constraint Integer Programs

probdata_coloring.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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file probdata_coloring.c
17  * @brief problem data for vertex coloring algorithm
18  * @author Gerald Gamrath
19  *
20  * This file implements the problem data for the coloring algorithm.
21  *
22  * The problem data contains the original graph, preprocessing information, the preprocessed graph,
23  * the array with the node-constraints, and an array with all stable sets and corresponding
24  * variables.
25  *
26  * The preprocessing deletes nodes that have a lower degree than the size of a maximum clique.
27  * Additionally, it also deletes nodes that have a dominated neighborhood. For further information,
28  * look at the documentation for the method preprocessGraph().
29  *
30  * The deleted nodes and the relation between the nodes of the original graph and the nodes of the
31  * preprocessed graph are stored in order to convert a solution of the preprocessed problem to a
32  * solution for the original graph and vice versa.
33  *
34  * Each variable has a pointer of type SCIP_VARDATA* that is used in this case to store an integer
35  * representing the number of the stable set. With the aid of this, the corresponding stable set can
36  * be found in the array returned by COLORprobGetStableSets(). This array contains all stable sets
37  * and is also used to check whether a stable set found by the pricer is really new. This can be
38  * done by calling COLORprobStableSetIsNew(). All sets are sorted decreasingly with respect to the
39  * indices of the nodes. New candidates should also be sorted that way.
40  */
41
42 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
43 #include "probdata_coloring.h"
44
45 #define EVENTHDLR_NAME "probdatavardeleted"
46 #define EVENTHDLR_DESC "event handler for variable deleted event"
47
48 struct SCIP_ProbData
49 {
50  TCLIQUE_GRAPH* graph; /* the preprocessed graph */
51  SCIP_CONS** constraints; /* array of added constraints */
52  int constraintssize; /* allocated size of constraints array */
53
54  /* stable set / variable - information*/
55  int** stablesets; /* array of stable sets */
56  int* stablesetlengths; /* length of the array in stablesets */
57  int maxstablesets; /* length of array stablesets */
58  int nstablesets; /* number of stable sets saved in array stablesets */
59  SCIP_VAR** stablesetvars; /* variables belonging to stable sets */
60
61  /* preprocessing information */
62  TCLIQUE_GRAPH* oldgraph; /* the original graph */
63  int* deletednodes; /* array of nodes which were deleted during preprocessing */
64  int* new2oldnode; /* new2oldnode[i] = j iff node i in the (preprocessed) graph corresponds to node j in the old graph*/
65 };
66
67
68 /*
69  * Local methods
70  */
71
72 /**
73  * Preprocessing of the graph, using 2 methods in order to find redundant nodes
74  * that can be deleted and easily colored later.
75  *
76  * Foundation of these methods is the computation of a maximum clique C with M nodes.
77  * After this computation, the following two steps are repeated until no node was deleted
78  * in the last iteration:
79  *
80  * 1: Low-Degree:
81  * Iterativly delete all nodes v in the graph G with degree d(v) < M ( don't delete nodes of C )
82  *
83  * 2: Dominated Neighbourhood:
84  * If the neighbourhood of one node v is part of the neighbourhood of another node w, v can
85  * be deleted, since it can later get the same color as w.
86  */
87 static
89  SCIP* scip /**< SCIP data structure */
90  )
91 {
92  SCIP_PROBDATA* probdata; /* the problemdata */
93  SCIP_Bool changed; /* was the graph changed in the last round of preprocessing? */
94  SCIP_Bool dominates; /* is the neighbourhood of one node dominated by the neigbourhood of another one?*/
95  int* maxcliquenodes; /* pointer to store nodes of the maximum weight clique */
96  int nmaxcliquenodes; /* number of nodes in the maximum weight clique */
97  TCLIQUE_WEIGHT maxcliqueweight; /* weight of the maximum weight clique */
98  TCLIQUE_STATUS status; /* status of clique-computation */
99  TCLIQUE_GRAPH* currgraph; /* the current, not preprocessed graph in each step */
100  int currnnodes; /* the current number of nodes in each step */
101  int actnewnode; /* the number of nodes yet marked for beeing in the graph in the next round */
102  int* newnodes; /* the nodes that will be in the graph in the next round */
103  int* degrees; /* the degrees of the nodes */
104  int myround; /* the number of the current round */
105  int ndeletednodes; /* the total number of deleted nodes */
106  int nnodesdeleteddegreethisround; /* the number of nodes deleted due to low degree in the current round */
107  int nnodesdeletedneighbourthisround; /* the number of nodes deleted due to neighborhood in the current round */
108  int* firstedge; /* pointer for the edges in the graph */
109  int* lastedge; /* pointer for the edges in the graph */
110  int i;
111  int j;
112  char opt;
113
114  assert(scip != NULL);
115  probdata = SCIPgetProbData(scip);
116  assert(probdata != NULL);
117
118  printf("\npreprocessing...\n");
119
120  /* copy the old graph */
121  if( !tcliqueCreate(&currgraph) )
122  {
123  SCIPerrorMessage("could not flush the clique graph\n");
124  return SCIP_ERROR;
125  }
126
127  assert(currgraph != NULL);
128
129  if( !tcliqueAddNode(currgraph, tcliqueGetNNodes(probdata->oldgraph)-1, 0) )
130  {
131  SCIPerrorMessage("could not add a node to the clique graph\n");
132  return SCIP_ERROR;
133  }
134
135  for ( i = 0; i < tcliqueGetNNodes(probdata->oldgraph); i++ )
136  {
137  /* get adjacent nodes for node i */
140  while ( firstedge <= lastedge )
141  {
142  if ( *firstedge > i )
143  {
144  if( !tcliqueAddEdge(currgraph, i, *firstedge) )
145  {
146  SCIPerrorMessage("could not add an edge to the clique graph\n");
147  return SCIP_ERROR;
148  }
149  }
150  firstedge++;
151  }
152  }
153
154  if( !tcliqueFlush(currgraph) )
155  {
156  SCIPerrorMessage("could not flush the clique graph\n");
157  return SCIP_ERROR;
158  }
159
160  currnnodes = tcliqueGetNNodes(probdata->oldgraph);
161
162  /* get memory for array of deletednodes and new2oldnodes */
163  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->deletednodes), currnnodes) );
164  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->new2oldnode), currnnodes) );
165
166  SCIP_CALL( SCIPallocBufferArray(scip, &newnodes, COLORprobGetOriginalNNodes(scip)) );
167  SCIP_CALL( SCIPallocBufferArray(scip, &maxcliquenodes, COLORprobGetOriginalNNodes(scip)) );
168
169  for ( i = 0; i < currnnodes; i++ )
170  {
171  /* set weights of the nodes to 1 */
172  tcliqueChangeWeight(currgraph, i, 1);
173  /* every node in the graph represents the same node in the original graph */
174  probdata->new2oldnode[i] = i;
175  }
176
177  /* compute maximum clique */
178  tcliqueMaxClique(NULL, NULL, NULL, NULL, currgraph, NULL, NULL, maxcliquenodes,
179  &nmaxcliquenodes, &maxcliqueweight, 0, 0, 50000, 0, INT_MAX, -1, NULL, &status);
180  opt = ( status == TCLIQUE_OPTIMAL ? ' ' : '*' );
181  printf("size of the maximum clique: %d%c \n", nmaxcliquenodes, opt);
182
183  ndeletednodes = 0;
184  nnodesdeleteddegreethisround = 1;
185  nnodesdeletedneighbourthisround = 1;
186  myround = 0;
187
188  /* main loop */
189  while ( (nnodesdeleteddegreethisround > 0) || (nnodesdeletedneighbourthisround > 0) )
190  {
191  myround++;
192  nnodesdeleteddegreethisround = 0;
193  nnodesdeletedneighbourthisround = 0;
194  changed = TRUE;
195
196  /* node degree deletion loop */
197  while ( changed == TRUE )
198  {
199  changed = FALSE;
200  actnewnode = 0;
201  degrees = tcliqueGetDegrees(currgraph);
202  for (i = 0; i < currnnodes; i++)
203  {
204  /* degree is low, node can be deleted */
205  if ( (degrees[i] < nmaxcliquenodes )
206  && (!COLORprobIsNodeInArray(probdata->new2oldnode[i], maxcliquenodes, nmaxcliquenodes)) )
207  {
208  probdata->deletednodes[ndeletednodes] = probdata->new2oldnode[i];
209  changed = TRUE;
210  nnodesdeleteddegreethisround++;
211  ndeletednodes++;
212  }
213  /* node will be in the new graph, because degree is not low enough for deletion or it is in the maxClique */
214  else
215  {
216  newnodes[actnewnode] = probdata->new2oldnode[i];
217  actnewnode++;
218  }
219  }
220
221  /* at least one node was deleted, create new graph (tclique doesn't support deletion of nodes) */
222  if ( changed )
223  {
224  assert(actnewnode+ndeletednodes == COLORprobGetOriginalNNodes(scip));
225  /* create new current graph */
226  tcliqueFree(&currgraph);
227
228  if( !tcliqueCreate(&currgraph) )
229  {
230  SCIPerrorMessage("could not create the clique graph\n");
231  return SCIP_ERROR;
232  }
233
234  assert(currgraph != NULL);
235
236  if( !tcliqueAddNode(currgraph, actnewnode-1, 0) )
237  {
238  SCIPerrorMessage("could not add a node to the clique graph\n");
239  return SCIP_ERROR;
240  }
241
242  for ( i = 0; i < actnewnode; i++ )
243  {
244  /* get adjacent nodes for node newnodes[i] */
247  while ( firstedge <= lastedge )
248  {
249  /* try to find a node in newnodes which corresponds
250  to the node in the old graph, that is the end-node of the edge */
251  for ( j = i+1; j < actnewnode; j++ )
252  {
253  if ( *firstedge == newnodes[j] )
254  {
255  if( !tcliqueAddEdge(currgraph, i, j) )
256  {
257  SCIPerrorMessage("could not add an edge to the clique graph\n");
258  return SCIP_ERROR;
259  }
260
261  break;
262  }
263  }
264  firstedge++;
265  }
266  }
267
268  if( !tcliqueFlush(currgraph) )
269  {
270  SCIPerrorMessage("could not flush the clique graph\n");
271  return SCIP_ERROR;
272  }
273
274  /* update currnnodes */
275  currnnodes = tcliqueGetNNodes(currgraph);
276  /* update new2oldnodes */
277  for ( i = 0; i < actnewnode; i++ )
278  {
279  probdata->new2oldnode[i] = newnodes[i];
280  }
281  /* set the corresponding old node to -1 for all nodes not in the current graph (only for bug-finding) */
282  for ( i = actnewnode; i < COLORprobGetOriginalNNodes(scip); i++ )
283  {
284  probdata->new2oldnode[i] = -1;
285  }
286  }
287  } /* end node degree deletion loop */
288
289  /* set changed to TRUE for getting into the while-loop */
290  changed = TRUE;
291  /* loop for finding dominated neighborhoods */
292  while ( changed == TRUE )
293  {
294  changed = FALSE;
295  actnewnode = 0;
296  /* i is the node which is checked for being dominated */
297  for ( i = 0; i < currnnodes; i++ )
298  {
299  assert(!COLORprobIsNodeInArray(probdata->new2oldnode[i], probdata->deletednodes, ndeletednodes));
300
301  /* i must be not in the clique and not yet deleted */
302  if ( (!COLORprobIsNodeInArray(probdata->new2oldnode[i], maxcliquenodes, nmaxcliquenodes)) )
303  {
304  /* j is the node for which is checked whether it dominates i */
305  for ( j = 0; j < currnnodes; j++ )
306  {
307  /* i must be distinct from j, there must be no edge between i and j,
308  j may not have been deleted due to degree in the last round */
309  if ( (j != i) && !tcliqueIsEdge(currgraph, i, j)
310  && (!COLORprobIsNodeInArray(probdata->new2oldnode[j], probdata->deletednodes, ndeletednodes)) )
311  /** @todo only check nodes deleted in the last round */
312  {
313  /* check whether nodes adjacent to i are also adjacent to j <-> j dominates i */
314  dominates = TRUE;
315  /* get adjacent nodes for node i in currgraph */
318  while ( firstedge <= lastedge )
319  {
320  /* check whether (j,firstedge) is in currgraph, if not, j doesn't dominate i */
321  if ( !tcliqueIsEdge(currgraph, j, *firstedge) )
322  {
323  dominates = FALSE;
324  break;
325  }
326  firstedge++;
327  }
328  if ( dominates )
329  {
330  probdata->deletednodes[ndeletednodes] = probdata->new2oldnode[i];
331  changed = TRUE;
332  ndeletednodes++;
333  nnodesdeletedneighbourthisround++;
334  break; /* for j, because we already now that i is dominated and deleted i */
335  }
336  }
337  } /* end for j */
338
339  /* if i is dominated by no other node and thus not deleted,
340  put it into newnodes, so that it is in the next graph */
341  if ( ndeletednodes == 0 || probdata->deletednodes[ndeletednodes-1] != probdata->new2oldnode[i])
342  {
343  newnodes[actnewnode] = probdata->new2oldnode[i];
344  actnewnode++;
345  }
346  }
347  /* if i is in the maxClique and was thus not deleted,
348  put it into newnodes, so that it is in the next graph */
349  else
350  {
351  newnodes[actnewnode] = probdata->new2oldnode[i];
352  actnewnode++;
353  }
354  } /*end for i */
355
356  /* at least one node was deleted, create new graph (tclique doesn't support deletion of nodes) */
357  if ( changed )
358  {
359  assert(actnewnode+ndeletednodes == COLORprobGetOriginalNNodes(scip));
360  /* create new current graph */
361  tcliqueFree(&currgraph);
362
363  if( !tcliqueCreate(&currgraph) )
364  {
365  SCIPerrorMessage("could not create the clique graph\n");
366  return SCIP_ERROR;
367  }
368
369  assert(currgraph != NULL);
370
371  if( !tcliqueAddNode(currgraph, actnewnode-1, 0) )
372  {
373  SCIPerrorMessage("could not add a node to the clique graph\n");
374  return SCIP_ERROR;
375  }
376
377  for ( i = 0; i < actnewnode; i++ )
378  {
379  /* get adjacent nodes for node newnodes[i] */
382  while ( firstedge <= lastedge )
383  {
384  /* try to find a node in newnodes which corresponds
385  to the node in the old graph, that is the end-node of the edge */
386  for ( j = i+1; j < actnewnode; j++ )
387  {
388  if ( *firstedge == newnodes[j] )
389  {
390
391  if( !tcliqueAddEdge(currgraph, i, j) )
392  {
393  SCIPerrorMessage("could not add an edge to the clique graph\n");
394  return SCIP_ERROR;
395  }
396  break;
397  }
398  }
399  firstedge++;
400  }
401  }
402
403  if( !tcliqueFlush(currgraph) )
404  {
405  SCIPerrorMessage("could not flush the clique graph\n");
406  return SCIP_ERROR;
407  }
408
409  /* update currnnodes */
410  currnnodes = tcliqueGetNNodes(currgraph);
411
412  /* update new2oldnodes */
413  for ( i = 0; i < actnewnode; i++ )
414  {
415  probdata->new2oldnode[i] = newnodes[i];
416  }
417
418  /* set the corresponding old node to -1 for all nodes not in the current graph (only for bug-finding) */
419  for ( i = actnewnode; i < COLORprobGetOriginalNNodes(scip); i++ )
420  {
421  probdata->new2oldnode[i] = -1;
422  }
423  }
424  } /* end of loop for finding dominated neighbourhoods */
425
426  printf("Round %d of preprocessing:\n", myround);
427  printf(" deleted low degree vertices: %d\n", nnodesdeleteddegreethisround);
428  printf(" deleted almost cliques: %d\n", nnodesdeletedneighbourthisround);
429
430  }
431
432  for ( i = ndeletednodes; i < COLORprobGetOriginalNNodes(scip); i++ )
433  {
434  probdata->deletednodes[i] = -1;
435  }
436
437  printf("preprocessing overall deleted vertices: %d\n\n", ndeletednodes);
438  /* copy preprocessed graph into problem data */
439  probdata->graph = currgraph;
440
441  SCIPfreeBufferArray(scip, &newnodes);
442  SCIPfreeBufferArray(scip, &maxcliquenodes);
443
444  return SCIP_OKAY;
445 }
446
447
448
449
450 /*
451  * Callback methods of probdata
452  */
453
454 /** transforms the problem */
455 static
456 SCIP_DECL_PROBTRANS(probtransColoring)
457 {
458  int i;
459  int j;
460  int* firstedge;
461  int* lastedge;
462
463  assert(scip != NULL);
464  assert(sourcedata != NULL);
465  assert(targetdata != NULL);
466
467  /* allocate memory */
468  SCIP_CALL( SCIPallocBlockMemory(scip, targetdata) );
469
470  if( !tcliqueCreate(&((*targetdata)->graph)) ) /* create the transformed graph */
471  {
472  SCIPerrorMessage("could not create the clique graph\n");
473  return SCIP_ERROR;
474  }
475
476  (*targetdata)->maxstablesets = sourcedata->maxstablesets; /* copy length of array sets */
477  (*targetdata)->nstablesets = sourcedata->nstablesets; /* copy number of sets saved in array sets */
478  (*targetdata)->oldgraph = sourcedata->oldgraph; /* copy link to original graph */
479
480  /* allocate memory for sets and lenghts of the sets */
481  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesets), sourcedata->maxstablesets) );
482  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesetlengths), sourcedata->maxstablesets) );
483  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesetvars), sourcedata->maxstablesets) );
484  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->deletednodes), tcliqueGetNNodes(sourcedata->oldgraph)) );
485  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->new2oldnode), tcliqueGetNNodes(sourcedata->oldgraph)) );
486
487  for ( i = 0; i < tcliqueGetNNodes(sourcedata->oldgraph); i++ )
488  {
489  (*targetdata)->deletednodes[i] = sourcedata->deletednodes[i];
490  (*targetdata)->new2oldnode[i] = sourcedata->new2oldnode[i];
491  }
492
493  /* copy stablesetlengths and stablesets */
494  for ( i = 0; i < sourcedata->nstablesets; i++ )
495  {
496  assert(sourcedata->stablesetvars[i] != NULL);
497  (*targetdata)->stablesetlengths[i] = sourcedata->stablesetlengths[i];
498  SCIP_CALL( SCIPtransformVar(scip, sourcedata->stablesetvars[i], &((*targetdata)->stablesetvars[i])) );
499  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->stablesets[i]), sourcedata->stablesetlengths[i]) ); /*lint !e866*/
500  for ( j = 0; j <sourcedata->stablesetlengths[i]; j++ )
501  {
502  (*targetdata)->stablesets[i][j] = sourcedata->stablesets[i][j];
503  }
504  }
505
506  /* create array for constraints */
507  (*targetdata)->constraintssize = tcliqueGetNNodes(sourcedata->graph);
508  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*targetdata)->constraints, (*targetdata)->constraintssize) );
509  /* tranform constraints */
510  SCIP_CALL( SCIPtransformConss(scip, tcliqueGetNNodes(sourcedata->graph), sourcedata->constraints,
511  (*targetdata)->constraints) );
512  /* copy the graph */
513  if( !tcliqueAddNode((*targetdata)->graph, tcliqueGetNNodes(sourcedata->graph)-1, 0) )
514  {
515  SCIPerrorMessage("could not add a node to the clique graph\n");
516  return SCIP_ERROR;
517  }
518
519  for ( i = 0; i < tcliqueGetNNodes(sourcedata->graph); i++ )
520  {
521  /* get adjacent nodes for node i */
524  while ( firstedge <= lastedge )
525  {
526  if ( *firstedge > i )
527  {
528  if( !tcliqueAddEdge((*targetdata)->graph, i, *firstedge) )
529  {
530  SCIPerrorMessage("could not add an edge to the clique graph\n");
531  return SCIP_ERROR;
532  }
533  }
534  firstedge++;
535  }
536  }
537
538  if( !tcliqueFlush((*targetdata)->graph) )
539  {
540  SCIPerrorMessage("could not flush the clique graph\n");
541  return SCIP_ERROR;
542  }
543
544  return SCIP_OKAY;
545 }
546
547
548 /** deletes the transformed problem */
549 static
550 SCIP_DECL_PROBDELTRANS(probdeltransColoring)
551 {
552  int i;
553
554  assert(scip != NULL);
555  assert(probdata != NULL);
556
557  /* release constraints and free array for constraints */
558  for ( i = 0; i < tcliqueGetNNodes((*probdata)->graph); i++)
559  {
560  SCIP_CALL( SCIPreleaseCons(scip, &((*probdata)->constraints[i])) );
561  }
562  SCIPfreeBlockMemoryArray(scip, &((*probdata)->constraints), (*probdata)->constraintssize);
563
564  /* free the arrays for the stable sets and release the related variables */
565  for ( i = (*probdata)->nstablesets-1; i >= 0; i-- )
566  {
567  SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesets[i]), (*probdata)->stablesetlengths[i]); /*lint !e866*/
568  SCIP_CALL( SCIPreleaseVar(scip, &((*probdata)->stablesetvars[i])) );
569  }
570
571  SCIPfreeBlockMemoryArray(scip, &((*probdata)->new2oldnode), tcliqueGetNNodes((*probdata)->oldgraph));
572  SCIPfreeBlockMemoryArray(scip, &((*probdata)->deletednodes), tcliqueGetNNodes((*probdata)->oldgraph));
573  SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesetvars), (*probdata)->maxstablesets);
574  SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesetlengths), (*probdata)->maxstablesets);
575  SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesets), (*probdata)->maxstablesets);
576
577  tcliqueFree(&(*probdata)->graph);
578  SCIPfreeBlockMemory(scip, probdata);
579  return SCIP_OKAY;
580 }
581
582 static
583 SCIP_DECL_PROBDELORIG(probdelorigColoring)
584 {
585  int i;
586
587  assert(probdata != NULL);
588  assert(*probdata != NULL);
589
590  SCIPfreeBlockMemoryArray(scip, &((*probdata)->new2oldnode), tcliqueGetNNodes((*probdata)->oldgraph));
591  SCIPfreeBlockMemoryArray(scip, &((*probdata)->deletednodes), tcliqueGetNNodes((*probdata)->oldgraph));
592
593  for ( i = (*probdata)->nstablesets-1; i >= 0; i-- )
594  {
595  SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesets[i]), (*probdata)->stablesetlengths[i]); /*lint !e866*/
596  SCIP_CALL( SCIPreleaseVar(scip, &((*probdata)->stablesetvars[i])) );
597  }
598  SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesetvars), (*probdata)->maxstablesets);
599  SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesetlengths), (*probdata)->maxstablesets);
600  SCIPfreeBlockMemoryArray(scip, &((*probdata)->stablesets), (*probdata)->maxstablesets);
601
602  /* release Constraints */
603  for ( i = 0; i < tcliqueGetNNodes((*probdata)->graph); i++ )
604  {
605  SCIP_CALL( SCIPreleaseCons(scip, &((*probdata)->constraints[i])) );
606  }
607  SCIPfreeBlockMemoryArray(scip, &((*probdata)->constraints), (*probdata)->constraintssize);
608
609  /* free memory used for graph */
610  tcliqueFree(&((*probdata)->graph));
611  tcliqueFree(&((*probdata)->oldgraph));
612
613  /* free probdata */
614  SCIPfreeBlockMemory(scip, probdata);
615
616  return SCIP_OKAY;
617 }
618
619
620 /*
621  * Callback methods of event handler
622  */
623
624 /** execution method of event handler */
625 static
626 SCIP_DECL_EVENTEXEC(eventExecProbdatavardeleted)
627 {
628  SCIP_VAR* var;
629  SCIP_PROBDATA* probdata;
630  int idx;
631
633  var = SCIPeventGetVar(event);
634  probdata = (SCIP_PROBDATA*) eventdata;
635
636  assert(probdata != NULL);
637  assert(var != NULL);
638
639  /* get index of variable in stablesets array */
640  idx = (int)(size_t) SCIPvarGetData(var);
641
642  SCIPdebugMessage("remove variable %s [%d] from list of stable sets\n", SCIPvarGetName(var), idx);
643
644  assert(probdata->stablesetvars[idx] == var);
645
646  /* remove variable from stablesets array and release it */
647  SCIPfreeBlockMemoryArray(scip, &(probdata->stablesets[idx]), probdata->stablesetlengths[idx]); /*lint !e866*/
648  SCIP_CALL( SCIPreleaseVar(scip, &(probdata->stablesetvars[idx])) );
649
650  /* move all subsequent variables to the front */
651  for( ; idx < probdata->nstablesets - 1; idx++)
652  {
653  probdata->stablesets[idx] = probdata->stablesets[idx + 1];
654  probdata->stablesetlengths[idx] = probdata->stablesetlengths[idx + 1];
655  probdata->stablesetvars[idx] = probdata->stablesetvars[idx + 1];
656  SCIPvarSetData(probdata->stablesetvars[idx], (SCIP_VARDATA*) (size_t) idx); /*lint !e571*/
657  }
658
659  probdata->nstablesets--;
660
661  return SCIP_OKAY;
662 }/*lint !e715*/
663
664
665
666 /*
667  * probdata specific interface methods
668  */
669
670 /** sets up the problem data */
672  SCIP* scip, /**< SCIP data structure */
673  const char* name, /**< problem name */
674  int nnodes, /**< number of nodes */
675  int nedges, /**< number of edges */
676  int** edges /**< array with start- and endpoints of the edges */
677  )
678 {
679  int i;
680  SCIP_PROBDATA* probdata = NULL;
681
682  assert(nnodes > 0); /* at least one node */
683  assert(nedges >= 0); /* no negative number of edges */
684
685  printf("Creating problem: %s \n", name);
686
687  /* allocate memory */
688  SCIP_CALL( SCIPallocBlockMemory(scip, &probdata) );
689
690  /* create graph */
691  if( !tcliqueCreate(&((probdata)->oldgraph)) )
692  {
693  SCIPerrorMessage("could not create the clique graph\n");
694  return SCIP_ERROR;
695  }
696
697  /* add all nodes from 0 to nnodes-1 */
698  if( !tcliqueAddNode((probdata)->oldgraph, nnodes-1, 0) )
699  {
700  SCIPerrorMessage("could not add a node to the clique graph\n");
701  return SCIP_ERROR;
702  }
703
704
705  /* add all edges, first into cache, then flush to add all of them to the graph */
706  for ( i = 0; i < nedges; i++ )
707  {
708  assert((edges[i][0] > 0) && (edges[i][0] <= nnodes));
709  assert((edges[i][1] > 0) && (edges[i][1] <= nnodes));
710
711  if( !tcliqueAddEdge((probdata)->oldgraph, edges[i][0]-1, edges[i][1]-1) )
712  {
713  SCIPerrorMessage("could not add an edge to the clique graph\n");
714  return SCIP_ERROR;
715  }
716  }
717
718  if( !tcliqueFlush((probdata)->oldgraph) )
719  {
720  SCIPerrorMessage("could not flush the clique graph\n");
721  return SCIP_ERROR;
722  }
723
724  /* create constraints */
725  probdata->constraintssize = nnodes;
726  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->constraints), probdata->constraintssize) );
727
728  /* at the beginning memory for 2 sets */
729  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->stablesets), 2) );
730  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->stablesetlengths), 2) );
731  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->stablesetvars), 2) );
732
733  probdata->maxstablesets = 2;
734  probdata->nstablesets = 0;
735
736  /* include variable deleted event handler into SCIP */
738  eventExecProbdatavardeleted, NULL) );
739
740  /* create problem in SCIP */
741  SCIP_CALL( SCIPcreateProb(scip, name, probdelorigColoring, probtransColoring, probdeltransColoring,
742  NULL, NULL, NULL, probdata) );
743
744  SCIP_CALL( preprocessGraph(scip) );
745
746  return SCIP_OKAY;
747 }
748
749
750 /* ----------------------------------- external methods -------------------------- */
751
752 /** returns the number of stable sets / variables */
754  SCIP* scip /**< SCIP data structure */
755  )
756 {
757  SCIP_PROBDATA* probdata;
758
759  assert(scip != NULL);
760  probdata = SCIPgetProbData(scip);
761  assert(probdata != NULL);
762
763  return probdata->nstablesets;
764 }
765
766
767 /** prints all stable sets to standard output */
769  SCIP* scip /**< SCIP data structure */
770  )
771 {
772  SCIP_PROBDATA* probdata;
773  int i;
774  int j;
775
776  assert(scip != NULL);
777  probdata = SCIPgetProbData(scip);
778  assert(probdata != NULL);
779
780  for ( i = 0; i < probdata->nstablesets; i++ )
781  {
782  printf( "Set %d: ", i);
783  for ( j = 0; j < probdata->stablesetlengths[i]; j++ )
784  {
785  printf("%d, ", probdata->stablesets[i][j]+1);
786  }
787  printf("ub = %f", SCIPvarGetUbLocal(probdata->stablesetvars[i]));
788  printf(", inLP = %u", SCIPvarIsInLP(probdata->stablesetvars[i]));
789  printf("\n");
790  }
791 }
792
793
794 /** prints the requested stable set to standard output */
796  SCIP* scip, /**< SCIP data structure */
797  int setnumber /**< the number of the requested set */
798  )
799 {
800  SCIP_PROBDATA* probdata;
801  int i;
802  int j;
803
804  assert(scip != NULL);
805  probdata = SCIPgetProbData(scip);
806  assert(probdata != NULL);
807
808  i = setnumber;
809  printf( "Set %d: ", i);
810  for ( j = 0; j < probdata->stablesetlengths[i]; j++ )
811  {
812  printf("%d, ", probdata->stablesets[i][j]+1);
813  }
814  if ( probdata->stablesetvars[i] != NULL )
815  printf("ub = %f", SCIPvarGetUbLocal(probdata->stablesetvars[i]));
816  printf("\n");
817 }
818
819
820
821
822 /** adds a variable that belongs to a given stable set */
824  SCIP* scip, /**< SCIP data structure */
825  int setindex, /**< index of the stable set */
826  SCIP_VAR* var /**< pointer to the variable */
827  )
828 {
829  SCIP_PROBDATA* probdata;
830
831  assert(scip != NULL);
832  probdata = SCIPgetProbData(scip);
833  assert(probdata != NULL);
834  assert((setindex >= 0) && (setindex < probdata->nstablesets));
835
836  /* catch variable deleted event on the variable to update the stablesetvars array in the problem data */
838  (SCIP_EVENTDATA*) probdata, NULL) );
839
840  probdata->stablesetvars[setindex] = var;
841
842  return SCIP_OKAY;
843 }
844
845
846 /** gets the variable belonging to a given stable set */
848  SCIP* scip, /**< SCIP data structure */
849  int setindex /**< index of the stable set */
850  )
851 {
852  SCIP_PROBDATA* probdata;
853
854  assert(scip != NULL);
855  probdata = SCIPgetProbData(scip);
856  assert(probdata != NULL);
857  assert ( (setindex >= 0) && (setindex < probdata->nstablesets));
858
859  return probdata->stablesetvars[setindex];
860 }
861
862
863 /** checks whether a node is in a given stable set, returns true iff it is */
865  SCIP* scip, /**< SCIP data structure */
866  int setindex, /**< index of the stable set */
867  int node /**< number of the node */
868  )
869 {
870  SCIP_PROBDATA* probdata;
871  int l;
872  int u;
873  int m;
874
875  assert(scip != NULL);
876  probdata = SCIPgetProbData(scip);
877  assert(probdata != NULL);
878
879  l = 0;
880  u = probdata->stablesetlengths[setindex]-1;
881  while ( l <= u )
882  {
883  m = (l+u)/2;
884  if ( probdata->stablesets[setindex][m] == node )
885  {
886  return TRUE;
887  }
888  if ( probdata->stablesets[setindex][m] > node )
889  {
890  l = m+1;
891  }
892  if ( probdata->stablesets[setindex][m] < node )
893  {
894  u = m-1;
895  }
896  }
897  return FALSE;
898 }
899
900
901 /** checks whether the first set is equal to the second set, both sets have to be sorted in a decreasing way */
903  SCIP* scip, /**< SCIP data structure */
904  int* set1, /**< array of nodes in the first set */
905  int nset1nodes, /**< number of nodes in the first set */
906  int* set2, /**< array of nodes in the second set */
907  int nset2nodes /**< number of nodes in the second set */
908  )
909 {
910
911  int i;
912
913  assert(scip != NULL);
914  assert(set1 != NULL && set2 != NULL);
915  assert(nset1nodes > 0 && nset2nodes > 0);
916
917  if ( nset1nodes != nset2nodes )
918  {
919  return FALSE;
920  }
921  for ( i = 0; i < nset1nodes; i++ )
922  {
923  if ( set1[i] != set2[i] )
924  {
925  return FALSE;
926  }
927  }
928  return TRUE;
929
930 }
931
932
933 /** checks whether the given stable set is new returns TRUE if the stable is new, FALSE if it is equal to an already
934  * existing stable set
935  */
937  SCIP* scip, /**< SCIP data structure */
938  int* stablesetnodes, /**< array of nodes in the stable set */
939  int nstablesetnodes /**< number of nodes in the stable set */
940  )
941 {
942  SCIP_PROBDATA* probdata;
943  int i;
944
945  assert(stablesetnodes != NULL);
946  assert(scip != NULL);
947  probdata = SCIPgetProbData(scip);
948  assert(probdata != NULL);
949
950  /* sort the set */
951  SCIPsortDownInt(stablesetnodes, nstablesetnodes);
952
953  for ( i = 0; i < COLORprobGetNStableSets(scip); i++ )
954  {
955  if ( COLORprobStableSetsAreEqual(scip, stablesetnodes, nstablesetnodes,
956  probdata->stablesets[i],
957  probdata->stablesetlengths[i]) )
958  {
959  return FALSE;
960  }
961  }
962
963  return TRUE;
964 }
965
966 /** adds a new stable set, the set must be sorted in descending order;
967  * @note you need to check whether it is new before adding it
968  */
970  SCIP* scip, /**< SCIP data structure */
971  int* stablesetnodes, /**< array of nodes in the stable set */
972  int nstablesetnodes, /**< number of nodes in the stable set */
973  int* setindex /**< return value: index of the stable set */
974  )
975 {
976  SCIP_PROBDATA* probdata;
977  int newsize;
978  int i;
979
980  assert(stablesetnodes != NULL);
981  assert(scip != NULL);
982  probdata = SCIPgetProbData(scip);
983  assert(probdata != NULL);
984
985  /* the set should be sorted in descending */
986 #ifndef NDEBUG
987  for ( i = 0; i < nstablesetnodes-2; i++ )
988  {
989  assert(stablesetnodes[i]>stablesetnodes[i+1]);
990  }
991 #endif
992
993  /* ensure that array is big enough */
994  if ( (probdata->nstablesets + 1) > probdata->maxstablesets)
995  {
996  newsize = SCIPcalcMemGrowSize(scip, probdata->maxstablesets + 1);
997  assert(newsize > probdata->nstablesets + 1);
998  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(probdata->stablesets), probdata->maxstablesets, newsize) );
999  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(probdata->stablesetlengths), probdata->maxstablesets, newsize) );
1000  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(probdata->stablesetvars), probdata->maxstablesets, newsize) );
1001  SCIPdebugMessage("Set-array resized: %d --> %d\n", probdata->maxstablesets, newsize);
1002  probdata->maxstablesets = newsize;
1003  }
1004
1005  /* allocate memory for the new stable set */
1006  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->stablesets[probdata->nstablesets]), nstablesetnodes) ); /*lint !e866*/
1007  probdata->stablesetlengths[probdata->nstablesets] = nstablesetnodes;
1008  probdata->stablesetvars[probdata->nstablesets] = NULL;
1009  for ( i = 0; i < nstablesetnodes; i++ )
1010  {
1011  assert(stablesetnodes[i] >= 0);
1012  probdata->stablesets[probdata->nstablesets][i] = stablesetnodes[i];
1013  }
1014  *setindex = probdata->nstablesets;
1015
1016  probdata->nstablesets++;
1017
1018  return SCIP_OKAY;
1019 }
1020
1021
1022 /** returns the stable set with the given index */
1024  SCIP* scip, /**< SCIP data structure */
1025  int setindex, /**< index of the stable set */
1026  int** stableset, /**< return value: pointer to the stable set */
1027  int* nelements /**< return value: number of elements in the stable set */
1028  )
1029 {
1030  SCIP_PROBDATA* probdata;
1031
1032  assert(scip != NULL);
1033  probdata = SCIPgetProbData(scip);
1034  assert(probdata != NULL);
1035
1036  *stableset = probdata->stablesets[setindex];
1037  *nelements = probdata->stablesetlengths[setindex];
1038 }
1039
1040
1041 /** returns all stable sets */
1043  SCIP* scip, /**< SCIP data structure */
1044  int*** stablesets, /**< return value: pointer to the stable sets */
1045  int** nelements, /**< return value: number of elements in the stable sets */
1046  int* nstablesets /**< return value: number of sets */
1047  )
1048 {
1049  SCIP_PROBDATA* probdata;
1050
1051  assert(scip != NULL);
1052  probdata = SCIPgetProbData(scip);
1053  assert(probdata != NULL);
1054
1055  *stablesets = probdata->stablesets;
1056  *nelements = probdata->stablesetlengths;
1057  *nstablesets = probdata->nstablesets;
1058 }
1059
1060
1061 /** returns the number of nodes in the (preprocessed) graph */
1063  SCIP* scip /**< SCIP data structure */
1064  )
1065 {
1066  SCIP_PROBDATA* probdata;
1067
1068  assert(scip != NULL);
1069  probdata = SCIPgetProbData(scip);
1070  assert(probdata != NULL);
1071
1072  return tcliqueGetNNodes(probdata->graph);
1073 }
1074
1075
1076 /** returns the number of nodes in the original graph */
1078  SCIP* scip /**< SCIP data structure */
1079  )
1080 {
1081  SCIP_PROBDATA* probdata;
1082
1083  assert(scip != NULL);
1084  probdata = SCIPgetProbData(scip);
1085  assert(probdata != NULL);
1086
1087  return tcliqueGetNNodes(probdata->oldgraph);
1088 }
1089
1090
1091 /** returns the (preprocessed) graph */
1093  SCIP* scip /**< SCIP data structure */
1094  )
1095 {
1096
1097  SCIP_PROBDATA* probdata;
1098
1099  assert(scip != NULL);
1100  probdata = SCIPgetProbData(scip);
1101  assert(probdata != NULL);
1102
1103  return probdata->graph;
1104 }
1105
1106
1107 /** returns the original graph */
1109  SCIP* scip /**< SCIP data structure */
1110  )
1111 {
1112  SCIP_PROBDATA* probdata;
1113
1114  assert(scip != NULL);
1115  probdata = SCIPgetProbData(scip);
1116  assert(probdata != NULL);
1117
1118  return probdata->oldgraph;
1119 }
1120
1121
1122 /** returns the array of nodes deleted during preprocessing, length = COLORprobGetOriginalNNodes(), filled with -1 at the end */
1124  SCIP* scip /**< SCIP data structure */
1125  )
1126 {
1127  SCIP_PROBDATA* probdata;
1128
1129  assert(scip != NULL);
1130  probdata = SCIPgetProbData(scip);
1131  assert(probdata != NULL);
1132
1133  return probdata->deletednodes;
1134 }
1135
1136
1137 /** returns the array in which for every node in the preprocessed graph, the related node in the original graph is saved */
1139  SCIP* scip /**< SCIP data structure */
1140  )
1141 {
1142  SCIP_PROBDATA* probdata;
1143
1144  assert(scip != NULL);
1145  probdata = SCIPgetProbData(scip);
1146  assert(probdata != NULL);
1147
1148  return probdata->new2oldnode;
1149 }
1150
1151
1152
1153 /** returns the node in the preprocessed graph, that belongs to the given node, returns -1 if node was deleted */
1155  SCIP* scip, /**< SCIP data structure */
1156  int node /**< a node in the original graph */
1157  )
1158 {
1159  SCIP_PROBDATA* probdata;
1160  int i;
1161
1162  assert(scip != NULL);
1163  probdata = SCIPgetProbData(scip);
1164
1165  assert(probdata != NULL);
1166  assert(node >= 0 && node < COLORprobGetOriginalNNodes(scip));
1167
1168  for ( i = 0; i < COLORprobGetOriginalNNodes(scip); i++ )
1169  {
1170  if ( probdata->new2oldnode[i] == node )
1171  return i;
1172  if ( probdata->new2oldnode[i] == -1 )
1173  return -1;
1174  }
1175  return -1;
1176
1177 }
1178
1179
1180 /** returns all node-constraints */
1182  SCIP* scip /**< SCIP data structure */
1183  )
1184 {
1185  SCIP_PROBDATA* probdata;
1186
1187  assert(scip != NULL);
1188  probdata = SCIPgetProbData(scip);
1189  assert(probdata != NULL);
1190
1191  return probdata->constraints;
1192 }
1193
1194
1195 /** returns the node-constraint belonging to a given node */
1197  SCIP* scip, /**< SCIP data structure */
1198  int node /**< number of the node, for which this constraint assures coloring */
1199  )
1200 {
1201  SCIP_PROBDATA* probdata;
1202
1203  assert(scip != NULL);
1204  probdata = SCIPgetProbData(scip);
1205  assert(probdata != NULL);
1206  assert(node >= 0 && node < tcliqueGetNNodes(probdata->graph));
1207
1208  return probdata->constraints[node];
1209 }
1210
1211
1212 /** computes the complementary graph for a given graph and stores it in the given pointer */
1214  SCIP* scip, /**< SCIP data structure */
1215  TCLIQUE_GRAPH* graph, /**< the given graph */
1216  TCLIQUE_GRAPH* cgraph /**< the complementary graph is saved in here */
1217  )
1218 {
1219  int nnodes;
1220  int i;
1221  int j;
1222  int* firstedge;
1223  int* lastedge;
1224
1225  assert(scip != NULL);
1226  assert(graph != NULL);
1227  assert(cgraph != NULL);
1228
1229  /* get number of nodes */
1230  nnodes = tcliqueGetNNodes(graph);
1231  assert(nnodes > 0);
1232
1233  /* add all nodes from 0 to nnodes-1 */
1234  if( !tcliqueAddNode(cgraph, nnodes-1, 0) )
1235  {
1236  SCIPerrorMessage("could not add a node to the clique graph\n");
1237  return SCIP_ERROR;
1238  }
1239
1240  /* add edge between i and j iff there is no edge between i and j in old graph */
1241  /* assumption: all edges are undirected, (i,j) exists --> (j,i) exists */
1242  for ( i = 0; i < nnodes; i++ )
1243  {
1246  for ( j = 0; j < *firstedge && j < i; j++ )
1247  {
1248  if( !tcliqueAddEdge(cgraph, i, j) )
1249  {
1250  SCIPerrorMessage("could not add an edge to the clique graph\n");
1251  return SCIP_ERROR;
1252  }
1253  }
1254  while ( firstedge < lastedge )
1255  {
1256  for ( j = *firstedge+1; j < *(firstedge+1) && j < i; j++ )
1257  {
1258  if( !tcliqueAddEdge(cgraph, i, j) )
1259  {
1260  SCIPerrorMessage("could not add an edge to the clique graph\n");
1261  return SCIP_ERROR;
1262  }
1263  }
1264  firstedge++;
1265  }
1266  for ( j = (*lastedge)+1; j < COLORprobGetNNodes(scip) && j < i; j++ )
1267  {
1268  if( !tcliqueAddEdge(cgraph, i, j) )
1269  {
1270  SCIPerrorMessage("could not add an edge to the clique graph\n");
1271  return SCIP_ERROR;
1272  }
1273  }
1274  }
1275
1276  if( !tcliqueFlush(cgraph) )
1277  {
1278  SCIPerrorMessage("could not flush the clique graph\n");
1279  return SCIP_ERROR;
1280  }
1281
1282  for ( i = 0; i < COLORprobGetNNodes(scip); i++ )
1283  {
1284  for ( j = i+1; j < COLORprobGetNNodes(scip); j++ )
1285  {
1286  assert((tcliqueIsEdge(graph, i, j) && !tcliqueIsEdge(cgraph, i, j))
1287  || (!tcliqueIsEdge(graph, i, j) && tcliqueIsEdge(cgraph, i, j)));
1288  }
1289  }
1290
1291  return SCIP_OKAY;
1292 }
1293
1294
1295 /** creates all node-constraints and saves them in an array */
1297  SCIP* scip /**< SCIP data structure */
1298  )
1299 {
1300  SCIP_CONS** constraints;
1301  int nnodes;
1302  int i;
1303
1304  assert(scip != NULL);
1305
1306  constraints = COLORprobGetConstraints(scip);
1307  assert(constraints != NULL);
1308  nnodes = COLORprobGetNNodes(scip);
1309  for ( i = 0; i < nnodes; i++ )
1310  {
1311  char consname[SCIP_MAXSTRLEN];
1312
1313  /* create the constraint */
1314  sprintf(consname, "Node-Constraint%d", i+1);
1315
1316  SCIP_CALL( SCIPcreateConsSetcover(scip, &constraints[i], consname, 0, NULL, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE) );
1318  }
1319
1320  return SCIP_OKAY;
1321 }
1322
1323
1324 /** checks whether the given node is in the given array */
1326  int node, /**< the number of the node */
1327  int* arraynodes, /**< the nodes of the maximum stableset */
1328  int narraynodes /**< number of nodes in the maximum stableset */
1329  )
1330 {
1331  int i;
1332
1333  assert(arraynodes != NULL);
1334
1335  for ( i = 0; i < narraynodes; i++ )
1336  {
1337  if ( arraynodes[i] == node )
1338  {
1339  return TRUE;
1340  }
1341  }
1342  return FALSE;
1343 }
1344
1345 /** checks whether the given two given arrays are equal */
1347  int* array1nodes, /**< the nodes of the first set */
1348  int narray1nodes, /**< number of nodes in the first set */
1349  int* array2nodes, /**< the nodes of the second set */
1350  int narray2nodes /**< number of nodes in the second set */
1351  )
1352 {
1353  int i;
1354
1355  assert(array1nodes != NULL);
1356  assert(narray1nodes > 0);
1357  assert(array2nodes != NULL);
1358  assert(narray2nodes > 0);
1359
1360  if ( narray1nodes != narray2nodes )
1361  {
1362  return FALSE;
1363  }
1364  for ( i = 0; i < narray1nodes; i++ )
1365  {
1366  if ( array1nodes[i] != array2nodes[i] )
1367  {
1368  return FALSE;
1369  }
1370  }
1371  return TRUE;
1372 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:116
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:105
#define NULL
Definition: def.h:239
enum TCLIQUE_Status TCLIQUE_STATUS
Definition: tclique.h:59
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:99
void tcliqueFree(TCLIQUE_GRAPH **tcliquegraph)
int COLORprobGetOriginalNNodes(SCIP *scip)
TCLIQUE_Bool tcliqueCreate(TCLIQUE_GRAPH **tcliquegraph)
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:40
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:422
problem data for vertex coloring algorithm
TCLIQUE_Bool tcliqueAddNode(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
#define SCIP_MAXSTRLEN
Definition: def.h:260
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
Definition: scip_prob.c:162
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:210
SCIP_RETCODE SCIPcreateConsSetcover(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, 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: cons_setppc.c:9172
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:172
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
SCIP_RETCODE SCIPtransformConss(SCIP *scip, int nconss, SCIP_CONS **conss, SCIP_CONS **transconss)
Definition: scip_cons.c:1639
#define EVENTHDLR_DESC
#define FALSE
Definition: def.h:65
struct SCIP_VarData SCIP_VARDATA
Definition: type_var.h:107
#define TRUE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
void COLORprobGetStableSets(SCIP *scip, int ***stablesets, int **nelements, int *nstablesets)
#define SCIPdebugMessage
Definition: pub_message.h:77
SCIP_EVENTHDLR * SCIPfindEventhdlr(SCIP *scip, const char *name)
Definition: scip_event.c:302
void COLORprobPrintStableSet(SCIP *scip, int setnumber)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
int COLORprobGetNewNodeForOriginalNode(SCIP *scip, int node)
int * COLORprobGetOriginalNodesForNewNodes(SCIP *scip)
SCIP_CONS * COLORprobGetConstraint(SCIP *scip, int node)
TCLIQUE_GRAPH * COLORprobGetGraph(SCIP *scip)
TCLIQUE_Bool tcliqueAddEdge(TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)
#define SCIPerrorMessage
Definition: pub_message.h:45
Definition: scip_prob.c:2822
void COLORprobGetStableSet(SCIP *scip, int setindex, int **stableset, int *nelements)
void tcliqueChangeWeight(TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)
int COLORprobGetNNodes(SCIP *scip)
int * tcliqueGetDegrees(TCLIQUE_GRAPH *tcliquegraph)
SCIP_RETCODE COLORprobAddVarForStableSet(SCIP *scip, int setindex, SCIP_VAR *var)
SCIP_RETCODE COLORprobAddNewStableSet(SCIP *scip, int *stablesetnodes, int nstablesetnodes, int *setindex)
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16729
SCIP_Bool COLORprobStableSetsAreEqual(SCIP *scip, int *set1, int nset1nodes, int *set2, int nset2nodes)
TCLIQUE_GRAPH * COLORprobGetOriginalGraph(SCIP *scip)
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)
#define SCIP_CALL(x)
Definition: def.h:351
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
SCIP_Bool COLORprobStableSetIsNew(SCIP *scip, int *stablesetnodes, int nstablesetnodes)
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:1018
#define SCIP_Bool
Definition: def.h:62
SCIP_CONS ** COLORprobGetConstraints(SCIP *scip)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:995
SCIP_Bool SCIPvarIsInLP(SCIP_VAR *var)
Definition: var.c:17068
#define EVENTHDLR_NAME
int COLORprobGetNStableSets(SCIP *scip)
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)
SCIP_VARDATA * SCIPvarGetData(SCIP_VAR *var)
Definition: var.c:16749
int * COLORprobGetDeletedNodes(SCIP *scip)
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
static SCIP_DECL_PROBDELORIG(probdelorigColoring)
static SCIP_DECL_EVENTEXEC(eventExecProbdatavardeleted)
SCIP_RETCODE SCIPcreateProbColoring(SCIP *scip, const char *name, int nnodes, int nedges, int **edges)
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:1020
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1187
void SCIPsortDownInt(int *intarray, int len)
SCIP_Bool COLORprobIsNodeInArray(int node, int *arraynodes, int narraynodes)
void COLORprobPrintStableSets(SCIP *scip)
SCIP_Bool COLORprobEqualSortedArrays(int *array1nodes, int narray1nodes, int *array2nodes, int narray2nodes)
static SCIP_DECL_PROBTRANS(probtransColoring)
SCIP_RETCODE SCIPtransformVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1352
SCIP_RETCODE COLORprobSetUpArrayOfCons(SCIP *scip)
static SCIP_RETCODE preprocessGraph(SCIP *scip)
TCLIQUE_Bool tcliqueFlush(TCLIQUE_GRAPH *tcliquegraph)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17409
#define nnodes
Definition: gastrans.c:65
static SCIP_DECL_PROBDELTRANS(probdeltransColoring)
int TCLIQUE_WEIGHT
Definition: tclique.h:39
void SCIPvarSetData(SCIP_VAR *var, SCIP_VARDATA *vardata)
Definition: var.c:16759
#define SCIP_EVENTTYPE_VARDELETED
Definition: type_event.h:57