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-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file 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 */
347  for( i = 0; i < nnodes; i++ )
348  {
349  int rnd = rand();
350  colors[i] = rnd % maxcolors;
351  assert( 0 <= colors[i] && colors[i] < maxcolors );
352  }
353 
354  /* init matrices */
355  SCIP_CALL( SCIPallocMemoryArray(scip, &tabu, nnodes) ); /* stores iteration at which tabu node/color pair will
356  * expire to be tabu
357  */
358  SCIP_CALL( SCIPallocMemoryArray(scip, &adj, nnodes) ); /* stores number of adjacent nodes using specified color */
359 
360  for( i = 0; i < nnodes; i++ )
361  {
362  SCIP_CALL( SCIPallocMemoryArray(scip, &(tabu[i]), maxcolors) ); /*lint !e866*/
363  SCIP_CALL( SCIPallocMemoryArray(scip, &(adj[i]), maxcolors) ); /*lint !e866*/
364  for( j = 0; j < maxcolors; j++ )
365  {
366  tabu[i][j] = 0;
367  adj[i][j] = 0;
368  }
369  }
370 
371  /* objective */
372  obj = 0;
373 
374  /* init adj-matrix and objective */
375  for( node1 = 0; node1 < nnodes; node1++ )
376  {
377  color1 = colors[node1];
378  firstedge = tcliqueGetFirstAdjedge(graph, node1);
379  lastedge = tcliqueGetLastAdjedge(graph, node1);
380  while( firstedge <= lastedge )
381  {
382  node2 = *firstedge;
383  color2 = colors[node2];
384  assert( 0 <= color2 && color2 < maxcolors );
385  (adj[node1][color2])++;
386  if( color1 == color2 )
387  obj++;
388  firstedge++;
389  }
390  }
391  assert( obj % 2 == 0 );
392  obj = obj / 2;
393  assert( obj == getNViolatedEdges(graph, colors) );
394 
395  bestobj = obj;
396  restrictive = FALSE;
397  iter = 0;
398  if( obj > 0 )
399  {
400  /* perform predefined number of iterations */
401  for( iter = 1; iter <= heurdata->maxiter; iter++ )
402  {
403  /* find best 1-move among those with critical vertex */
404  minnode = -1;
405  mincolor = -1;
406  minvalue = nnodes * nnodes;
407  ncritical = 0;
408  for( node1 = 0; node1 < nnodes; node1++ )
409  {
410  aspiration = FALSE;
411  color1 = colors[node1];
412  assert( 0 <= color1 && color1 < maxcolors );
413 
414  /* if node is critical (has incident violated edges) */
415  if( adj[node1][color1] > 0 )
416  {
417  ncritical++;
418  /* check all colors */
419  for( j = 0; j < maxcolors; j++ )
420  {
421  /* if color is new */
422  if( j != color1 )
423  {
424  /* change in the number of violated edges: */
425  d = adj[node1][j] - adj[node1][color1];
426 
427  /* 'aspiration criterion': stop if we get feasible solution */
428  if( obj + d == 0 )
429  {
430  if( heurdata->output >= 1 )
431  printf(" Feasible solution found after %d iterations!\n\n", iter);
432  minnode = node1;
433  mincolor = j;
434  minvalue = d;
435  aspiration = TRUE;
436  break;
437  }
438 
439  /* if not tabu and better value */
440  if( tabu[node1][j] < iter && d < minvalue )
441  {
442  minnode = node1;
443  mincolor = j;
444  minvalue = d;
445  }
446  }
447  }
448  }
449  if( aspiration )
450  break;
451  }
452 
453  /* if no candidate could be found - tabu list is too restrictive: just skip current iteration */
454  if( minnode == -1 )
455  {
456  restrictive = TRUE;
457  continue;
458  }
459  assert( minnode != -1 );
460  assert( mincolor >= 0 );
461 
462  /* perform changes */
463  assert( colors[minnode] != mincolor );
464  oldcolor = colors[minnode];
465  colors[minnode] = mincolor;
466  obj += minvalue;
467  assert( obj == getNViolatedEdges(graph, colors) );
468  if( obj < bestobj )
469  bestobj = obj;
470 
471  if( heurdata->output == 2 && (iter) % (heurdata->dispfreq) == 0 )
472  {
473  printf("Iter: %d obj: %d critical: %d node: %d color: %d delta: %d\n", iter, obj, ncritical, minnode,
474  mincolor, minvalue);
475  }
476 
477  /* terminate if valid coloring has been found */
478  if( obj == 0 )
479  break;
480 
481  /* update tabu list */
482  assert( tabu[minnode][oldcolor] < iter );
483  tabu[minnode][oldcolor] = iter + (heurdata->tabubase) + (int) (((double) ncritical) * (heurdata->tabugamma));
484 
485  /* update adj matrix */
486  for( firstedge = tcliqueGetFirstAdjedge(graph, minnode); firstedge <= tcliqueGetLastAdjedge(graph, minnode); firstedge++ )
487  {
488  (adj[*firstedge][mincolor])++;
489  (adj[*firstedge][oldcolor])--;
490  }
491  }
492  }
493  if( heurdata->output == 2 )
494  {
495  printf("Best objective: %d\n ", bestobj);
496  if( restrictive )
497  {
498  printf("\nTabu list is probably too restrictive.\n");
499  }
500  printf("\n");
501  }
502  if( heurdata->output >= 1 && bestobj != 0 )
503  {
504  printf(" No feasible solution found after %d iterations!\n\n", iter-1);
505  }
506 
507  for( i = 0; i < nnodes; i++ )
508  {
509  SCIPfreeMemoryArray(scip, &(adj[i]));
510  SCIPfreeMemoryArray(scip, &(tabu[i]));
511  }
512  SCIPfreeMemoryArray(scip, &adj);
513  SCIPfreeMemoryArray(scip, &tabu);
514 
515  /* check whether valid coloring has been found */
516  *success = (obj == 0);
517 
518  return SCIP_OKAY;
519 }
520 
521 
522 /*
523  * Callback methods of primal heuristic
524  */
525 
526 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
527 static
528 SCIP_DECL_HEURCOPY(heurCopyInit)
529 { /*lint --e{715}*/
530  assert(scip != NULL);
531  assert(heur != NULL);
532  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
533 
534  return SCIP_OKAY;
535 }
536 
537 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
538 /**! [SnippetHeurFreeInit] */
539 static
540 SCIP_DECL_HEURFREE(heurFreeInit)
541 {
542  SCIP_HEURDATA* heurdata;
543 
544  /* free heuristic rule data */
545  heurdata = SCIPheurGetData(heur);
546  SCIPfreeBlockMemory(scip, &heurdata);
547  SCIPheurSetData(heur, NULL);
548 
549  return SCIP_OKAY;
550 }
551 /**! [SnippetHeurFreeInit] */
552 
553 
554 /** execution method of primal heuristic */
555 static
556 SCIP_DECL_HEUREXEC(heurExecInit)
557 {
558  int i;
559  int j;
560  int k;
561  int nnodes;
562  SCIP_SOL* sol;
563  SCIP_Bool stored;
564  SCIP_Bool success;
565  SCIP_Bool indnode;
566  int* colors;
567  int* bestcolors;
568  int ncolors;
569  int nstablesetnodes;
570  int setnumber;
571  SCIP_VAR* var;
572  SCIP_CONS** constraints;
573  TCLIQUE_GRAPH* graph;
574  SCIP_HEURDATA* heurdata;
575 
576  heurdata = SCIPheurGetData(heur);
577  assert(heurdata != NULL);
578 
579  *result = SCIP_DIDNOTFIND;
580  nnodes = COLORprobGetNNodes(scip);
581  graph = COLORprobGetGraph(scip);
582  /* create stable sets if no solution was read */
583  if( COLORprobGetNStableSets(scip) == 0 )
584  {
585  /* get memory for arrays */
586  SCIP_CALL( SCIPallocBufferArray(scip, &colors, nnodes) );
587  SCIP_CALL( SCIPallocBufferArray(scip, &bestcolors, nnodes) );
588 
589  /* get the node-constraits */
590  constraints = COLORprobGetConstraints(scip);
591  assert(constraints != NULL);
592 
593  /* compute an initial coloring with a greedy method */
594  SCIP_CALL( greedyInitialColoring(scip, graph, bestcolors, &ncolors) );
595 
596  if( heurdata->usetabu )
597  {
598  /* try to find better colorings with tabu search method */
599  success = TRUE;
600  while( success )
601  {
602  ncolors--;
603  SCIP_CALL( runTabuCol(graph, 0, ncolors, colors, heurdata, &success) );
604 
605  if( success )
606  {
607  for( i = 0; i < nnodes; i++ )
608  {
609  bestcolors[i] = colors[i];
610  }
611  }
612 
613  }
614  }
615 
616  /* create vars for the computed coloring */
617  for( i = 0; i <= ncolors; i++ )
618  {
619  /* save nodes with color i in the array colors and the number of such nodes in nstablesetnodes */
620  nstablesetnodes = 0;
621  for( j = 0; j < nnodes; j++ )
622  {
623  if( bestcolors[j] == i )
624  {
625  colors[nstablesetnodes] = j;
626  nstablesetnodes++;
627  }
628  }
629  /* try to add more nodes to the stable set without violating the stability */
630  for( j = 0; j < nnodes; j++ )
631  {
632  indnode = TRUE;
633  for( k = 0; k < nstablesetnodes; k++ )
634  {
635  if( j == colors[k] || tcliqueIsEdge(graph, j, colors[k]) )
636  {
637  indnode = FALSE;
638  break;
639  }
640  }
641  if( indnode == TRUE )
642  {
643  colors[nstablesetnodes] = j;
644  nstablesetnodes++;
645  }
646  }
647  /* create variable for the stable set and add it to SCIP */
648  SCIPsortDownInt(colors, nstablesetnodes);
649  SCIP_CALL( COLORprobAddNewStableSet(scip, colors, nstablesetnodes, &setnumber) );
650  assert(setnumber != -1);
651 
652  /* create variable for the stable set and add it to SCIP */
653  SCIP_CALL( SCIPcreateVar(scip, &var, NULL, 0.0, 1.0, 1.0, SCIP_VARTYPE_BINARY,
654  TRUE, TRUE, NULL, NULL, NULL, NULL, (SCIP_VARDATA*)(size_t)setnumber) ); /*lint !e571*/
655 
656  SCIP_CALL( COLORprobAddVarForStableSet(scip, setnumber, var) );
657  SCIP_CALL( SCIPaddVar(scip, var) );
658  SCIP_CALL( SCIPchgVarUbLazy(scip, var, 1.0) );
659 
660  for( j = 0; j < nstablesetnodes; j++ )
661  {
662  /* add variable to node constraints of nodes in the set */
663  SCIP_CALL( SCIPaddCoefSetppc(scip, constraints[colors[j]], var) );
664  }
665 
666 
667  }
668 
669  SCIPfreeBufferArray(scip, &bestcolors);
670  SCIPfreeBufferArray(scip, &colors);
671 
672  }
673  /* create solution consisting of all yet created stable sets,
674  that means all sets of the solution given by the solution file or created by the greedy and tabu search */
675  SCIP_CALL( SCIPcreateSol(scip, &sol, NULL) );
676  assert(sol != NULL);
677  for( i = 0; i < COLORprobGetNStableSets(scip); i++ )
678  {
680  }
681  SCIP_CALL( SCIPtrySolFree(scip, &sol, TRUE, FALSE, FALSE, FALSE, FALSE, &stored) );
682  assert(stored);
683 
684  /* set maximal number of variables to be priced in each round */
685  SCIP_CALL( SCIPsetIntParam(scip, "pricers/coloring/maxvarsround",
687 
688  *result = SCIP_FOUNDSOL;
689 
690  return SCIP_OKAY;
691 }/*lint !e715*/
692 
693 /*
694  * primal heuristic specific interface methods
695  */
696 
697 /** creates the init primal heuristic and includes it in SCIP */
699  SCIP* scip /**< SCIP data structure */
700  )
701 {
702  SCIP_HEURDATA* heurdata;
703  SCIP_HEUR* heur;
704 
705  /* create init primal heuristic data */
706  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
707 
708  heur = NULL;
709  /* include primal heuristic */
711  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecInit, heurdata) );
712  assert(heur != NULL);
713 
714  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyInit) );
715  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeInit) );
716 
717  /* add parameters */
719  "heuristics/initcol/usetabu",
720  "should the tabu search heuristic be used in order to improve the greedy-solution?",
721  &heurdata->usetabu, FALSE, DEFAULT_USETABU, NULL, NULL) );
722 
724  "heuristics/initcol/maxiter",
725  "maximal number of iterations to be performed in each tabu-run",
726  &heurdata->maxiter, TRUE, DEFAULT_MAXITER, 0, INT_MAX, NULL, NULL) );
727 
729  "heuristics/initcol/tabubase",
730  "constant part of the tabu-duration",
731  &heurdata->tabubase, TRUE, DEFAULT_TABUBASE, 0, INT_MAX, NULL, NULL) );
732 
734  "heuristics/initcol/tabugamma",
735  "factor for the linear part of the tabu-duration",
736  &heurdata->tabugamma, TRUE, DEFAULT_TABUGAMMA, -100.0, 100.0, NULL, NULL) );
737 
739  "heuristics/initcol/output",
740  "verbosity level for the output of the tabu search, 0: no output, 1: normal, 2: high",
741  &heurdata->output, FALSE, DEFAULT_OUTPUT, 0, 2, NULL, NULL) );
742 
744  "heuristics/initcol/dispfreq",
745  "frequency for displaying status information, only active with output verbosity level 2",
746  &heurdata->dispfreq, TRUE, DEFAULT_DISPFREQ, 0, INT_MAX, NULL, NULL) );
747 
748 
749  return SCIP_OKAY;
750 }
#define HEUR_FREQOFS
Definition: heur_init.c:79
#define NULL
Definition: def.h:246
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9229
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:88
#define HEUR_DISPCHAR
Definition: heur_init.c:76
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:72
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition: scip_var.c:5085
#define FALSE
Definition: def.h:72
struct SCIP_VarData SCIP_VARDATA
Definition: type_var.h:107
#define TRUE
Definition: def.h:71
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#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:51
void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
file reader for vertex coloring instances
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
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:187
static SCIP_DECL_HEUREXEC(heurExecInit)
Definition: heur_init.c:556
tclique user interface
constraint handler for storing the graph at each node of the tree
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
Constraint handler for the set partitioning / packing / covering constraints .
#define DEFAULT_DISPFREQ
Definition: heur_init.c:91
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
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:155
#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:1254
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:248
SCIP_RETCODE SCIPincludeHeurInit(SCIP *scip)
Definition: heur_init.c:698
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
#define SCIP_CALL(x)
Definition: def.h:358
#define HEUR_TIMING
Definition: heur_init.c:81
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1270
#define SCIP_Bool
Definition: def.h:69
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:3276
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:578
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:104
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:1724
static SCIP_DECL_HEURCOPY(heurCopyInit)
Definition: heur_init.c:528
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:157
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:232
#define nnodes
Definition: gastrans.c:65
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
static SCIP_DECL_HEURFREE(heurFreeInit)
Definition: heur_init.c:540
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:211
#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:129
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:377