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