Scippy

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