83#define HEUR_NAME "initcol"
84#define HEUR_DESC "initial primal heuristic for coloring"
85#define HEUR_DISPCHAR 't'
86#define HEUR_PRIORITY 1
89#define HEUR_MAXDEPTH 0
90#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
91#define HEUR_USESSUBSCIP FALSE
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
174 nnodes = tcliqueGetNNodes(graph);
188 values[
i] = degrees[
i] + ( colors[
i] == -1 ?
nnodes : 0);
195 stablesetnodes[0] = sortednodes[0];
199 if( colors[sortednodes[
i]] != -1 )
204 for( j = 0; j < nstablesetnodes; j++ )
206 if( tcliqueIsEdge(graph, sortednodes[
i], stablesetnodes[j]) )
212 if( indNode ==
TRUE )
214 stablesetnodes[nstablesetnodes] = sortednodes[
i];
219 for(
i = 0;
i < nstablesetnodes;
i++ )
221 assert(colors[stablesetnodes[
i]] == -1);
222 colors[stablesetnodes[
i]] = nextcolor;
288 nnodes = tcliqueGetNNodes(graph);
296 if( colors[
i] == colors[*j] )
348 printf(
"Running tabu coloring with maxcolors = %d...\n", maxcolors);
351 nnodes = tcliqueGetNNodes(graph);
358 if( colors[
i] < 0 || colors[
i] >= maxcolors )
361 colors[
i] = rnd % maxcolors;
363 assert( 0 <= colors[
i] && colors[
i] < maxcolors );
376 for( j = 0; j < maxcolors; j++ )
387 for( node1 = 0; node1 <
nnodes; node1++ )
389 color1 = colors[node1];
392 while( firstedge <= lastedge )
395 color2 = colors[node2];
396 assert( 0 <= color2 && color2 < maxcolors );
397 (adj[node1][color2])++;
398 if( color1 == color2 )
413 for( iter = 1; iter <=
heurdata->maxiter; iter++ )
420 for( node1 = 0; node1 <
nnodes; node1++ )
423 color1 = colors[node1];
424 assert( 0 <= color1 && color1 < maxcolors );
427 if( adj[node1][color1] > 0 )
431 for( j = 0; j < maxcolors; j++ )
437 d = adj[node1][j] - adj[node1][color1];
443 printf(
" Feasible solution found after %d iterations!\n\n", iter);
452 if( tabu[node1][j] < iter && d < minvalue )
475 assert( colors[minnode] != mincolor );
476 oldcolor = colors[minnode];
477 colors[minnode] = mincolor;
485 printf(
"Iter: %d obj: %d critical: %d node: %d color: %d delta: %d\n", iter,
obj, ncritical, minnode,
494 assert( tabu[minnode][oldcolor] < iter );
495 tabu[minnode][oldcolor] = iter + (
heurdata->tabubase) + (
int) (((double) ncritical) * (
heurdata->tabugamma));
500 (adj[*firstedge][mincolor])++;
501 (adj[*firstedge][oldcolor])--;
507 printf(
"Best objective: %d\n ", bestobj);
510 printf(
"\nTabu list is probably too restrictive.\n");
514 if(
heurdata->output >= 1 && bestobj != 0 )
516 printf(
" No feasible solution found after %d iterations!\n\n", iter-1);
528 *success = (
obj == 0);
625 bestcolors[
i] = colors[
i];
631 for(
i = 0;
i <= ncolors;
i++ )
635 for( j = 0; j <
nnodes; j++ )
637 if( bestcolors[j] ==
i )
639 colors[nstablesetnodes] = j;
645 for( j = 0; j <
nnodes; j++ )
648 for( k = 0; k < nstablesetnodes; k++ )
650 if( j == colors[k] || tcliqueIsEdge(graph, j, colors[k]) )
657 if( indnode ==
TRUE )
659 colors[nstablesetnodes] = j;
677 for( j = 0; j < nstablesetnodes; j++ )
739 "heuristics/initcol/usetabu",
740 "should the tabu search heuristic be used in order to improve the greedy-solution?",
744 "heuristics/initcol/maxiter",
745 "maximal number of iterations to be performed in each tabu-run",
749 "heuristics/initcol/tabubase",
750 "constant part of the tabu-duration",
754 "heuristics/initcol/tabugamma",
755 "factor for the linear part of the tabu-duration",
759 "heuristics/initcol/output",
760 "verbosity level for the output of the tabu search, 0: no output, 1: normal, 2: high",
764 "heuristics/initcol/dispfreq",
765 "frequency for displaying status information, only active with output verbosity level 2",
Constraint handler for the set partitioning / packing / covering constraints .
constraint handler for storing the graph at each node of the tree
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
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)
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)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
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)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
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)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
#define SCIPallocMemoryArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPfreeMemoryArray(scip, ptr)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
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)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
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)
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortDownInt(int *intarray, int len)
SCIPcreateSol(scip, &heurdata->sol, heur))
static SCIP_RETCODE greedyStableSet(SCIP *scip, TCLIQUE_GRAPH *graph, int *colors, int nextcolor)
static SCIP_RETCODE runTabuCol(TCLIQUE_GRAPH *graph, int seed, int maxcolors, int *colors, SCIP_HEURDATA *heurdata, SCIP_Bool *success)
#define DEFAULT_TABUGAMMA
SCIP_RETCODE SCIPincludeHeurInit(SCIP *scip)
static SCIP_RETCODE greedyInitialColoring(SCIP *scip, TCLIQUE_GRAPH *graph, int *colors, int *ncolors)
static SCIP_Bool hasUncoloredNode(int nnodes, int *colors)
static int getNViolatedEdges(TCLIQUE_GRAPH *graph, int *colors)
initial primal heuristic for the vertex coloring problem
assert(minobj< SCIPgetCutoffbound(scip))
variable pricer for the vertex coloring problem
SCIP_CONS ** COLORprobGetConstraints(SCIP *scip)
SCIP_RETCODE COLORprobAddNewStableSet(SCIP *scip, int *stablesetnodes, int nstablesetnodes, int *setindex)
int COLORprobGetNNodes(SCIP *scip)
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
TCLIQUE_GRAPH * COLORprobGetGraph(SCIP *scip)
SCIP_RETCODE COLORprobAddVarForStableSet(SCIP *scip, int setindex, SCIP_VAR *var)
int COLORprobGetNStableSets(SCIP *scip)
problem data for vertex coloring algorithm
file reader for vertex coloring instances
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
int * tcliqueGetDegrees(TCLIQUE_GRAPH *tcliquegraph)
int * tcliqueGetFirstAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
struct TCLIQUE_Graph TCLIQUE_GRAPH
struct SCIP_Cons SCIP_CONS
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
struct SCIP_Heur SCIP_HEUR
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_VarData SCIP_VARDATA