Scippy

SCIP

Solving Constraint Integer Programs

heur_init.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-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_init.c
17  * @brief initial primal heuristic for the vertex coloring problem
18  * @author Gerald Gamrath
19  *
20  * This file implements a heuristic which computes a starting solution for the coloring problem. It
21  * therefore computes maximal stable sets and creates one variable for each set, which is added to the
22  * LP.
23  *
24  * The heuristic is called only one time: before solving the root node.
25  *
26  * It checks, whether a solution-file was read in and a starting solution already exists. If this
27  * is not the case, an initial possible coloring is computed by a greedy method. After that, a
28  * tabu-search is called, which tries to reduce the number of colors needed. The tabu-search algorithm
29  * follows the description in
30  *
31  * "A Survey of Local Search Methods for Graph Coloring"@n
32  * by P. Galinier and A. Hertz@n
33  * Computers & Operations Research, 33 (2006)
34  *
35  * The tabu-search works as follows: given the graph and a number of colors it tries to color the
36  * nodes of the graph with at most the given number of colors. It starts with a random coloring. In
37  * each iteration, it counts the number of violated edges, that is, edges for which both incident
38  * nodes have the same color. It now switches one node to another color in each iteration, taking
39  * the node and color, that cause the greatest reduction of the number of violated edges, or if no
40  * such combination exists, the node and color that cause the smallest increase of that number. The
41  * former color of the node is forbidden for a couple of iterations in order to give the possibility
42  * to leave a local minimum.
43  *
44  * As long as the tabu-search finds a solution with the given number of colors, this number is reduced
45  * by 1 and the tabu-search is called another time. If no coloring was found after a given number
46  * of iterations, the tabu-search is stopped and variables for all sets of the last feasible coloring
47  * are created and added to the LP (after possible extension to maximal stable sets).
48  *
49  * The variables of these sets result in a feasible starting solution of the coloring problem.
50  *
51  * The tabu-search can be deactivated by setting the parameter <heuristics/initcol/usetabu> to
52  * FALSE. The number of iterations after which the tabu-search stops if no solution was yet found
53  * can be changed by the param <heuristics/initcol/maxiter>. A great effect is also obtained by
54  * changing the parameters <heuristics/initcol/tabubase> and <heuristics/initcol/tabugamma>, which
55  * determine the number of iterations for which the former color of a node is forbidden; more
56  * precisely, this number is <tabubase> + ncritical * <tabugamma>, where ncritical is the number
57  * of nodes, which are incident to violated edges. Finally, the level of output and the frequency of
58  * status lines can be changed by <heuristics/initcol/output> and <heuristics/initcol/dispfreq>.
59  */
60 
61 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
62 
63 #include <assert.h>
64 #include <string.h>
65 
66 #include "heur_init.h"
67 #include "pricer_coloring.h"
68 #include "probdata_coloring.h"
69 #include "reader_col.h"
70 #include "scip/cons_setppc.h"
71 #include "cons_storeGraph.h"
72 #include "tclique/tclique.h"
73 
74 #define HEUR_NAME "initcol"
75 #define HEUR_DESC "initial primal heuristic for coloring"
76 #define HEUR_DISPCHAR 't'
77 #define HEUR_PRIORITY 1
78 #define HEUR_FREQ 1
79 #define HEUR_FREQOFS 0
80 #define HEUR_MAXDEPTH 0
81 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
82 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
83 
84 
85 /* default values for parameters */
86 #define DEFAULT_USETABU TRUE
87 #define DEFAULT_MAXITER 100000
88 #define DEFAULT_TABUBASE 50
89 #define DEFAULT_TABUGAMMA 0.9
90 #define DEFAULT_OUTPUT 1
91 #define DEFAULT_DISPFREQ 10000
92 
93 
94 
95 /*
96  * Data structures
97  */
98 
99 /** primal heuristic data */
100 struct SCIP_HeurData
101 {
102  SCIP_Bool usetabu; /**< should the tabu search heuristic be used in order to improve the greedy-solution? */
103  int maxiter; /**< maximal number of iterations to be performed in each tabu-run */
104  int tabubase; /**< constant part of the tabu-duration */
105  SCIP_Real tabugamma; /**< factor for the linear part of the tabu-duration */
106  int output; /**< verbosity level for the output of the tabu search, 0: no output, 1: normal, 2: high */
107  int dispfreq; /**< frequency for displaying status information, only active with output verbosity level 2 */
108 };
109 
110 
111 
112 
113 /*
114  * Local methods
115  */
116 
117 
118 
119 /** checks whether one of the nodes has no color respectively has color -1 in the given array */
120 static
122  int nnodes, /**< the graph that should be colored */
123  int* colors /**< array of ints representing the colors */
124  )
125 {
126  int i;
127 
128  assert(colors != NULL);
129 
130  for( i = 0; i < nnodes; i++)
131  {
132  /* node not yet colored */
133  if(colors[i] == -1)
134  {
135  return TRUE;
136  }
137  }
138  return FALSE;
139 }
140 
141 
142 /** computes a stable set with a greedy-method and colors its nodes */
143 static
145  SCIP* scip, /**< SCIP data structure */
146  TCLIQUE_GRAPH* graph, /**< pointer to graph data structure */
147  int* colors, /**< array of ints representing the different colors, -1 means uncolored */
148  int nextcolor /**< color in which the stable set will be colored */
149  )
150 {
151  SCIP_Bool indNode;
152  int nnodes;
153  int i;
154  int j;
155  int* degrees;
156  int* sortednodes;
157  int* values;
158  int* stablesetnodes;
159  int nstablesetnodes;
160 
161  assert(graph != NULL);
162  assert(colors != NULL);
163 
164  /* get number of nodes */
165  nnodes = tcliqueGetNNodes(graph);
166 
167  /* get the degrees and weights for the nodes in the graph */
168  degrees = tcliqueGetDegrees(graph);
169  SCIP_CALL( SCIPallocBufferArray(scip, &stablesetnodes, nnodes) );
170  SCIP_CALL( SCIPallocBufferArray(scip, &values, nnodes) );
171  SCIP_CALL( SCIPallocBufferArray(scip, &sortednodes, nnodes) );
172 
173  /* set values to the nodes which are used for sorting them */
174  /* value = degree of the node + number of nodes if the node is yet uncolored,
175  therefore the yet colored nodes have lower values than the not yet colored nodes */
176  for( i = 0; i < nnodes; i++ )
177  {
178  sortednodes[i] = i;
179  values[i] = degrees[i] + ( colors[i] == -1 ? nnodes : 0);
180  }
181 
182  /* sort the nodes w.r.t. the computed values */
183  SCIPsortDownIntInt(values, sortednodes, nnodes);
184 
185  /* insert first node */
186  stablesetnodes[0] = sortednodes[0];
187  nstablesetnodes = 1;
188  for( i = 1; i < nnodes; i++)
189  {
190  if( colors[sortednodes[i]] != -1 )
191  {
192  break;
193  }
194  indNode = TRUE;
195  for( j = 0; j < nstablesetnodes; j++ )
196  {
197  if( tcliqueIsEdge(graph, sortednodes[i], stablesetnodes[j]) )
198  {
199  indNode = FALSE;
200  break;
201  }
202  }
203  if( indNode == TRUE )
204  {
205  stablesetnodes[nstablesetnodes] = sortednodes[i];
206  nstablesetnodes++;
207  }
208 
209  }
210  for( i = 0; i < nstablesetnodes; i++ )
211  {
212  assert(colors[stablesetnodes[i]] == -1);
213  colors[stablesetnodes[i]] = nextcolor;
214  }
215  SCIPfreeBufferArray(scip, &stablesetnodes);
216  SCIPfreeBufferArray(scip, &sortednodes);
217  SCIPfreeBufferArray(scip, &values);
218 
219  return SCIP_OKAY;
220 }
221 
222 
223 static
224 /** computes the initial coloring with a greedy method */
226  SCIP* scip, /**< SCIP data structure */
227  TCLIQUE_GRAPH* graph, /**< pointer to graph data structure */
228  int* colors, /**< array of ints representing the different colors */
229  int* ncolors /**< number of colors needed */
230  )
231 {
232  int nnodes;
233  int i;
234  int color;
235 
236  assert(scip != NULL);
237  assert(graph != NULL);
238  assert(colors != NULL);
239 
240  nnodes = COLORprobGetNNodes(scip);
241  assert(nnodes > 0);
242 
243  for( i = 0; i < nnodes; i++ )
244  {
245  colors[i] = -1;
246  }
247 
248  color = 0;
249  /* create stable sets until all Nodes are covered */
250  while( hasUncoloredNode(nnodes, colors) )
251  {
252  SCIP_CALL( greedyStableSet(scip, graph, colors, color) );
253  color++;
254  }
255  *ncolors = color;
256 
257  return SCIP_OKAY;
258 
259 }
260 
261 
262 #ifndef NDEBUG
263 /** computes the number of violated edges, that means the number of edges (i,j) where i and j have the same color */
264 static
266  TCLIQUE_GRAPH* graph, /**< the graph */
267  int* colors /**< colors of the nodes */
268  )
269 {
270  int nnodes;
271  int i;
272  int* j;
273  int cnt;
274 
275  assert(graph != NULL);
276  assert(colors != NULL);
277 
278  /* get the number of nodes */
279  nnodes = tcliqueGetNNodes(graph);
280  cnt = 0;
281 
282  /* count the number of violated edges, only consider edges (i,j) with i > j since the graph is undirected bu */
283  for( i = 0; i < nnodes; i++ )
284  {
285  for( j = tcliqueGetFirstAdjedge(graph,i); j <= tcliqueGetLastAdjedge(graph,i) && *j < i; j++ )
286  {
287  if( colors[i] == colors[*j] )
288  cnt++;
289  }
290  }
291  return cnt;
292 }
293 #endif
294 
295 
296 /** runs tabu coloring heuristic, gets a graph and a number of colors
297  * and tries to color the graph with at most that many colors;
298  * starts with a random coloring and switches one node to another color in each iteration,
299  * forbidding the old color for a couple of iterations
300  */
301 static
303  TCLIQUE_GRAPH* graph, /**< the graph, that should be colored */
304  int seed, /**< seed for the first random coloring */
305  int maxcolors, /**< number of colors, which are allowed */
306  int* colors, /**< output: the computed coloring */
307  SCIP_HEURDATA* heurdata, /**< data of the heuristic */
308  SCIP_Bool* success /**< pointer to store if something went wrong */
309  )
310 {
311  int nnodes;
312  int** tabu;
313  int** adj;
314  int obj;
315  int bestobj;
316  int i;
317  int j;
318  int node1;
319  int node2;
320  int color1;
321  int color2;
322  int* firstedge;
323  int* lastedge;
324  SCIP_Bool restrictive;
325  int iter;
326  int minnode;
327  int mincolor;
328  int minvalue;
329  int ncritical;
330  SCIP_Bool aspiration;
331  int d;
332  int oldcolor;
333 
334  assert(graph != NULL);
335  assert(heurdata != NULL);
336  assert(success != NULL);
337 
338  if( heurdata->output >= 1 )
339  printf("Running tabu coloring with maxcolors = %d...\n", maxcolors);
340 
341  /* get size */
342  nnodes = tcliqueGetNNodes(graph);
343 
344  srand( seed ); /*lint !e732*/
345 
346  /* init random coloring, optionally keeping colors from a previous coloring */
347  for( i = 0; i < nnodes; i++ )
348  {
349  if( colors[i] < 0 || colors[i] >= maxcolors )
350  {
351  int rnd = rand();
352  colors[i] = rnd % maxcolors;
353  }
354  assert( 0 <= colors[i] && colors[i] < maxcolors );
355  }
356 
357  /* init matrices */
358  SCIP_CALL( SCIPallocMemoryArray(scip, &tabu, nnodes) ); /* stores iteration at which tabu node/color pair will
359  * expire to be tabu
360  */
361  SCIP_CALL( SCIPallocMemoryArray(scip, &adj, nnodes) ); /* stores number of adjacent nodes using specified color */
362 
363  for( i = 0; i < nnodes; i++ )
364  {
365  SCIP_CALL( SCIPallocMemoryArray(scip, &(tabu[i]), maxcolors) ); /*lint !e866*/
366  SCIP_CALL( SCIPallocMemoryArray(scip, &(adj[i]), maxcolors) ); /*lint !e866*/
367  for( j = 0; j < maxcolors; j++ )
368  {
369  tabu[i][j] = 0;
370  adj[i][j] = 0;
371  }
372  }
373 
374  /* objective */
375  obj = 0;
376 
377  /* init adj-matrix and objective */
378  for( node1 = 0; node1 < nnodes; node1++ )
379  {
380  color1 = colors[node1];
381  firstedge = tcliqueGetFirstAdjedge(graph, node1);
382  lastedge = tcliqueGetLastAdjedge(graph, node1);
383  while( firstedge <= lastedge )
384  {
385  node2 = *firstedge;
386  color2 = colors[node2];
387  assert( 0 <= color2 && color2 < maxcolors );
388  (adj[node1][color2])++;
389  if( color1 == color2 )
390  obj++;
391  firstedge++;
392  }
393  }
394  assert( obj % 2 == 0 );
395  obj = obj / 2;
396  assert( obj == getNViolatedEdges(graph, colors) );
397 
398  bestobj = obj;
399  restrictive = FALSE;
400  iter = 0;
401  if( obj > 0 )
402  {
403  /* perform predefined number of iterations */
404  for( iter = 1; iter <= heurdata->maxiter; iter++ )
405  {
406  /* find best 1-move among those with critical vertex */
407  minnode = -1;
408  mincolor = -1;
409  minvalue = nnodes * nnodes;
410  ncritical = 0;
411  for( node1 = 0; node1 < nnodes; node1++ )
412  {
413  aspiration = FALSE;
414  color1 = colors[node1];
415  assert( 0 <= color1 && color1 < maxcolors );
416 
417  /* if node is critical (has incident violated edges) */
418  if( adj[node1][color1] > 0 )
419  {
420  ncritical++;
421  /* check all colors */
422  for( j = 0; j < maxcolors; j++ )
423  {
424  /* if color is new */
425  if( j != color1 )
426  {
427  /* change in the number of violated edges: */
428  d = adj[node1][j] - adj[node1][color1];
429 
430  /* 'aspiration criterion': stop if we get feasible solution */
431  if( obj + d == 0 )
432  {
433  if( heurdata->output >= 1 )
434  printf(" Feasible solution found after %d iterations!\n\n", iter);
435  minnode = node1;
436  mincolor = j;
437  minvalue = d;
438  aspiration = TRUE;
439  break;
440  }
441 
442  /* if not tabu and better value */
443  if( tabu[node1][j] < iter && d < minvalue )
444  {
445  minnode = node1;
446  mincolor = j;
447  minvalue = d;
448  }
449  }
450  }
451  }
452  if( aspiration )
453  break;
454  }
455 
456  /* if no candidate could be found - tabu list is too restrictive: just skip current iteration */
457  if( minnode == -1 )
458  {
459  restrictive = TRUE;
460  continue;
461  }
462  assert( minnode != -1 );
463  assert( mincolor >= 0 );
464 
465  /* perform changes */
466  assert( colors[minnode] != mincolor );
467  oldcolor = colors[minnode];
468  colors[minnode] = mincolor;
469  obj += minvalue;
470  assert( obj == getNViolatedEdges(graph, colors) );
471  if( obj < bestobj )
472  bestobj = obj;
473 
474  if( heurdata->output == 2 && (iter) % (heurdata->dispfreq) == 0 )
475  {
476  printf("Iter: %d obj: %d critical: %d node: %d color: %d delta: %d\n", iter, obj, ncritical, minnode,
477  mincolor, minvalue);
478  }
479 
480  /* terminate if valid coloring has been found */
481  if( obj == 0 )
482  break;
483 
484  /* update tabu list */
485  assert( tabu[minnode][oldcolor] < iter );
486  tabu[minnode][oldcolor] = iter + (heurdata->tabubase) + (int) (((double) ncritical) * (heurdata->tabugamma));
487 
488  /* update adj matrix */
489  for( firstedge = tcliqueGetFirstAdjedge(graph, minnode); firstedge <= tcliqueGetLastAdjedge(graph, minnode); firstedge++ )
490  {
491  (adj[*firstedge][mincolor])++;
492  (adj[*firstedge][oldcolor])--;
493  }
494  }
495  }
496  if( heurdata->output == 2 )
497  {
498  printf("Best objective: %d\n ", bestobj);
499  if( restrictive )
500  {
501  printf("\nTabu list is probably too restrictive.\n");
502  }
503  printf("\n");
504  }
505  if( heurdata->output >= 1 && bestobj != 0 )
506  {
507  printf(" No feasible solution found after %d iterations!\n\n", iter-1);
508  }
509 
510  for( i = 0; i < nnodes; i++ )
511  {
512  SCIPfreeMemoryArray(scip, &(adj[i]));
513  SCIPfreeMemoryArray(scip, &(tabu[i]));
514  }
515  SCIPfreeMemoryArray(scip, &adj);
516  SCIPfreeMemoryArray(scip, &tabu);
517 
518  /* check whether valid coloring has been found */
519  *success = (obj == 0);
520 
521  return SCIP_OKAY;
522 }
523 
524 
525 /*
526  * Callback methods of primal heuristic
527  */
528 
529 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
530 static
531 SCIP_DECL_HEURCOPY(heurCopyInit)
532 { /*lint --e{715}*/
533  assert(scip != NULL);
534  assert(heur != NULL);
535  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
536 
537  return SCIP_OKAY;
538 }
539 
540 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
541 /**! [SnippetHeurFreeInit] */
542 static
543 SCIP_DECL_HEURFREE(heurFreeInit)
544 {
545  SCIP_HEURDATA* heurdata;
546 
547  /* free heuristic rule data */
548  heurdata = SCIPheurGetData(heur);
549  SCIPfreeBlockMemory(scip, &heurdata);
550  SCIPheurSetData(heur, NULL);
551 
552  return SCIP_OKAY;
553 }
554 /**! [SnippetHeurFreeInit] */
555 
556 
557 /** execution method of primal heuristic */
558 static
559 SCIP_DECL_HEUREXEC(heurExecInit)
560 {
561  int i;
562  int j;
563  int k;
564  int nnodes;
565  SCIP_SOL* sol;
566  SCIP_Bool stored;
567  SCIP_Bool success;
568  SCIP_Bool indnode;
569  int* colors;
570  int* bestcolors;
571  int ncolors;
572  int nstablesetnodes;
573  int setnumber;
574  SCIP_VAR* var;
575  SCIP_CONS** constraints;
576  TCLIQUE_GRAPH* graph;
577  SCIP_HEURDATA* heurdata;
578  SCIP_Bool onlybest;
579  int maxvarsround;
580 
581  heurdata = SCIPheurGetData(heur);
582  assert(heurdata != NULL);
583 
584  *result = SCIP_DIDNOTFIND;
585  nnodes = COLORprobGetNNodes(scip);
586  graph = COLORprobGetGraph(scip);
587 
588  /* create stable sets if no solution was read */
589  if( COLORprobGetNStableSets(scip) == 0 )
590  {
591  /* get memory for arrays */
592  SCIP_CALL( SCIPallocBufferArray(scip, &colors, nnodes) );
593  SCIP_CALL( SCIPallocBufferArray(scip, &bestcolors, nnodes) );
594 
595  /* get the node-constraits */
596  constraints = COLORprobGetConstraints(scip);
597  assert(constraints != NULL);
598 
599  /* compute an initial coloring with a greedy method */
600  SCIP_CALL( greedyInitialColoring(scip, graph, bestcolors, &ncolors) );
601 
602  if( heurdata->usetabu )
603  {
604  /* try to find better colorings with tabu search method */
605  success = TRUE;
606  while( success )
607  {
608  ncolors--;
609 
610  /* initialize with colors from previous iteration; the last color is randomized */
611  SCIP_CALL( runTabuCol(graph, 0, ncolors, colors, heurdata, &success) );
612 
613  if( success )
614  {
615  for( i = 0; i < nnodes; i++ )
616  bestcolors[i] = colors[i];
617  }
618  }
619  }
620 
621  /* create vars for the computed coloring */
622  for( i = 0; i <= ncolors; i++ )
623  {
624  /* save nodes with color i in the array colors and the number of such nodes in nstablesetnodes */
625  nstablesetnodes = 0;
626  for( j = 0; j < nnodes; j++ )
627  {
628  if( bestcolors[j] == i )
629  {
630  colors[nstablesetnodes] = j;
631  nstablesetnodes++;
632  }
633  }
634 
635  /* try to add more nodes to the stable set without violating the stability */
636  for( j = 0; j < nnodes; j++ )
637  {
638  indnode = TRUE;
639  for( k = 0; k < nstablesetnodes; k++ )
640  {
641  if( j == colors[k] || tcliqueIsEdge(graph, j, colors[k]) )
642  {
643  indnode = FALSE;
644  break;
645  }
646  }
647 
648  if( indnode == TRUE )
649  {
650  colors[nstablesetnodes] = j;
651  nstablesetnodes++;
652  }
653  }
654 
655  /* create variable for the stable set and add it to SCIP */
656  SCIPsortDownInt(colors, nstablesetnodes);
657  SCIP_CALL( COLORprobAddNewStableSet(scip, colors, nstablesetnodes, &setnumber) );
658  assert(setnumber != -1);
659 
660  /* create variable for the stable set and add it to SCIP */
661  SCIP_CALL( SCIPcreateVar(scip, &var, NULL, 0.0, 1.0, 1.0, SCIP_VARTYPE_BINARY,
662  TRUE, TRUE, NULL, NULL, NULL, NULL, (SCIP_VARDATA*)(size_t)setnumber) ); /*lint !e571*/
663 
664  SCIP_CALL( COLORprobAddVarForStableSet(scip, setnumber, var) );
665  SCIP_CALL( SCIPaddVar(scip, var) );
666  SCIP_CALL( SCIPchgVarUbLazy(scip, var, 1.0) );
667 
668  for( j = 0; j < nstablesetnodes; j++ )
669  {
670  /* add variable to node constraints of nodes in the set */
671  SCIP_CALL( SCIPaddCoefSetppc(scip, constraints[colors[j]], var) );
672  }
673  }
674 
675  SCIPfreeBufferArray(scip, &bestcolors);
676  SCIPfreeBufferArray(scip, &colors);
677 
678  }
679 
680  /* create solution consisting of all yet created stable sets, i.e., all sets of the solution given by the solution
681  * file or created by the greedy and tabu search */
682  SCIP_CALL( SCIPcreateSol(scip, &sol, NULL) );
683  assert(sol != NULL);
684  for( i = 0; i < COLORprobGetNStableSets(scip); i++ )
685  {
687  }
688  SCIP_CALL( SCIPtrySolFree(scip, &sol, TRUE, FALSE, FALSE, FALSE, FALSE, &stored) );
689  assert(stored);
690 
691  /* set maximal number of variables to be priced in each round */
692  SCIP_CALL( SCIPgetBoolParam(scip, "pricers/coloring/onlybest", &onlybest) );
693  if( onlybest )
694  maxvarsround = COLORprobGetNStableSets(scip) * COLORprobGetNNodes(scip)/50;
695  else
696  maxvarsround = 1;
697  SCIP_CALL( SCIPsetIntParam(scip, "pricers/coloring/maxvarsround", maxvarsround) );
698 
699  *result = SCIP_FOUNDSOL;
700 
701  return SCIP_OKAY;
702 }/*lint !e715*/
703 
704 /*
705  * primal heuristic specific interface methods
706  */
707 
708 /** creates the init primal heuristic and includes it in SCIP */
710  SCIP* scip /**< SCIP data structure */
711  )
712 {
713  SCIP_HEURDATA* heurdata;
714  SCIP_HEUR* heur;
715 
716  /* create init primal heuristic data */
717  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
718 
719  heur = NULL;
720  /* include primal heuristic */
722  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecInit, heurdata) );
723  assert(heur != NULL);
724 
725  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyInit) );
726  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeInit) );
727 
728  /* add parameters */
730  "heuristics/initcol/usetabu",
731  "should the tabu search heuristic be used in order to improve the greedy-solution?",
732  &heurdata->usetabu, FALSE, DEFAULT_USETABU, NULL, NULL) );
733 
735  "heuristics/initcol/maxiter",
736  "maximal number of iterations to be performed in each tabu-run",
737  &heurdata->maxiter, TRUE, DEFAULT_MAXITER, 0, INT_MAX, NULL, NULL) );
738 
740  "heuristics/initcol/tabubase",
741  "constant part of the tabu-duration",
742  &heurdata->tabubase, TRUE, DEFAULT_TABUBASE, 0, INT_MAX, NULL, NULL) );
743 
745  "heuristics/initcol/tabugamma",
746  "factor for the linear part of the tabu-duration",
747  &heurdata->tabugamma, TRUE, DEFAULT_TABUGAMMA, -100.0, 100.0, NULL, NULL) );
748 
750  "heuristics/initcol/output",
751  "verbosity level for the output of the tabu search, 0: no output, 1: normal, 2: high",
752  &heurdata->output, FALSE, DEFAULT_OUTPUT, 0, 2, NULL, NULL) );
753 
755  "heuristics/initcol/dispfreq",
756  "frequency for displaying status information, only active with output verbosity level 2",
757  &heurdata->dispfreq, TRUE, DEFAULT_DISPFREQ, 0, INT_MAX, NULL, NULL) );
758 
759 
760  return SCIP_OKAY;
761 }
#define HEUR_FREQOFS
Definition: heur_init.c:79
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9372
struct TCLIQUE_Graph TCLIQUE_GRAPH
Definition: tclique.h:40
#define DEFAULT_TABUGAMMA
Definition: heur_init.c:89
problem data for vertex coloring algorithm
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
#define HEUR_DISPCHAR
Definition: heur_init.c:76
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition: scip_var.c:5161
#define FALSE
Definition: def.h:87
struct SCIP_VarData SCIP_VARDATA
Definition: type_var.h:107
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define DEFAULT_TABUBASE
Definition: heur_init.c:88
initial primal heuristic for the vertex coloring problem
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
file reader for vertex coloring instances
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
static SCIP_DECL_HEUREXEC(heurExecInit)
Definition: heur_init.c:559
tclique user interface
constraint handler for storing the graph at each node of the tree
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
Constraint handler for the set partitioning / packing / covering constraints .
#define DEFAULT_DISPFREQ
Definition: heur_init.c:91
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
#define HEUR_MAXDEPTH
Definition: heur_init.c:80
#define HEUR_PRIORITY
Definition: heur_init.c:77
TCLIQUE_GRAPH * COLORprobGetGraph(SCIP *scip)
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1441
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_RETCODE SCIPincludeHeurInit(SCIP *scip)
Definition: heur_init.c:709
int COLORprobGetNNodes(SCIP *scip)
#define DEFAULT_OUTPUT
Definition: heur_init.c:90
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)
variable pricer for the vertex coloring problem
#define HEUR_NAME
Definition: heur_init.c:74
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:384
#define HEUR_TIMING
Definition: heur_init.c:81
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
#define SCIP_Bool
Definition: def.h:84
SCIP_CONS ** COLORprobGetConstraints(SCIP *scip)
#define HEUR_FREQ
Definition: heur_init.c:78
static SCIP_Bool hasUncoloredNode(int nnodes, int *colors)
Definition: heur_init.c:121
int COLORprobGetNStableSets(SCIP *scip)
#define DEFAULT_USETABU
Definition: heur_init.c:86
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3231
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:105
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
static SCIP_RETCODE greedyInitialColoring(SCIP *scip, TCLIQUE_GRAPH *graph, int *colors, int *ncolors)
Definition: heur_init.c:225
static SCIP_RETCODE greedyStableSet(SCIP *scip, TCLIQUE_GRAPH *graph, int *colors, int nextcolor)
Definition: heur_init.c:144
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1667
static SCIP_DECL_HEURCOPY(heurCopyInit)
Definition: heur_init.c:531
static int getNViolatedEdges(TCLIQUE_GRAPH *graph, int *colors)
Definition: heur_init.c:265
void SCIPsortDownInt(int *intarray, int len)
#define SCIP_Real
Definition: def.h:177
static SCIP_RETCODE runTabuCol(TCLIQUE_GRAPH *graph, int seed, int maxcolors, int *colors, SCIP_HEURDATA *heurdata, SCIP_Bool *success)
Definition: heur_init.c:302
#define HEUR_USESSUBSCIP
Definition: heur_init.c:82
#define HEUR_DESC
Definition: heur_init.c:75
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
#define nnodes
Definition: gastrans.c:65
SCIPallocBlockMemory(scip, subsol))
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1352
static SCIP_DECL_HEURFREE(heurFreeInit)
Definition: heur_init.c:543
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
#define DEFAULT_MAXITER
Definition: heur_init.c:87
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319