heur_init.c
Go to the documentation of this file.
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
37 * tabu-search is called, which tries to reduce the number of colors needed. The tabu-search algorithm
45 * nodes of the graph with at most the given number of colors. It starts with a random coloring. In
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
53 * As long as the tabu-search finds a solution with the given number of colors, this number is reduced
55 * of iterations, the tabu-search is stopped and variables for all sets of the last feasible coloring
63 * changing the parameters <heuristics/initcol/tabubase> and <heuristics/initcol/tabugamma>, which
66 * of nodes, which are incident to violated edges. Finally, the level of output and the frequency of
70 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
111 SCIP_Bool usetabu; /**< should the tabu search heuristic be used in order to improve the greedy-solution? */
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 */
128 /** checks whether one of the nodes has no color respectively has color -1 in the given array */
272 /** computes the number of violated edges, that means the number of edges (i,j) where i and j have the same color */
291 /* count the number of violated edges, only consider edges (i,j) with i > j since the graph is undirected bu */
367 SCIP_CALL( SCIPallocMemoryArray(scip, &tabu, nnodes) ); /* stores iteration at which tabu node/color pair will
370 SCIP_CALL( SCIPallocMemoryArray(scip, &adj, nnodes) ); /* stores number of adjacent nodes using specified color */
465 /* if no candidate could be found - tabu list is too restrictive: just skip current iteration */
485 printf("Iter: %d obj: %d critical: %d node: %d color: %d delta: %d\n", iter, obj, ncritical, minnode,
495 tabu[minnode][oldcolor] = iter + (heurdata->tabubase) + (int) (((double) ncritical) * (heurdata->tabugamma));
498 for( firstedge = tcliqueGetFirstAdjedge(graph, minnode); firstedge <= tcliqueGetLastAdjedge(graph, minnode); firstedge++ )
633 /* save nodes with color i in the array colors and the number of such nodes in nstablesetnodes */
689 /* create solution consisting of all yet created stable sets, i.e., all sets of the solution given by the solution
730 SCIP_CALL( SCIPincludeHeurBasic(scip, &heur, HEUR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_PRIORITY, HEUR_FREQ, HEUR_FREQOFS,
Definition: type_result.h:56
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9385
Definition: struct_scip.h:68
problem data for vertex coloring algorithm
Definition: struct_var.h:207
SCIP_RETCODE SCIPchgVarUbLazy(SCIP *scip, SCIP_VAR *var, SCIP_Real lazyub)
Definition: scip_var.c:5170
Definition: type_var.h:62
initial primal heuristic for the vertex coloring problem
void SCIPsortDownIntInt(int *intarray1, int *intarray2, int len)
file reader for vertex coloring instances
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
tclique user interface
constraint handler for storing the graph at each node of the tree
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1371
Constraint handler for the set partitioning / packing / covering constraints .
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
Definition: struct_sol.h:73
Definition: type_result.h:44
Definition: struct_cons.h:46
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
int * tcliqueGetDegrees(TCLIQUE_GRAPH *tcliquegraph)
Definition: tclique_graph.c:782
SCIP_RETCODE COLORprobAddVarForStableSet(SCIP *scip, int setindex, SCIP_VAR *var)
Definition: probdata_coloring.c:832
SCIP_RETCODE COLORprobAddNewStableSet(SCIP *scip, int *stablesetnodes, int nstablesetnodes, int *setindex)
Definition: probdata_coloring.c:978
variable pricer for the vertex coloring problem
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
Definition: type_retcode.h:42
SCIP_VAR * COLORprobGetVarForStableSet(SCIP *scip, int setindex)
Definition: probdata_coloring.c:856
Definition: struct_heur.h:97
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1221
SCIP_CONS ** COLORprobGetConstraints(SCIP *scip)
Definition: probdata_coloring.c:1190
static SCIP_Bool hasUncoloredNode(int nnodes, int *colors)
Definition: heur_init.c:130
int * tcliqueGetLastAdjedge(TCLIQUE_GRAPH *tcliquegraph, int node)
Definition: tclique_graph.c:828
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:3240
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)
Definition: tclique_graph.c:804
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
static int getNViolatedEdges(TCLIQUE_GRAPH *graph, int *colors)
Definition: heur_init.c:274
void SCIPsortDownInt(int *intarray, int len)
static SCIP_RETCODE runTabuCol(TCLIQUE_GRAPH *graph, int seed, int maxcolors, int *colors, SCIP_HEURDATA *heurdata, SCIP_Bool *success)
Definition: heur_init.c:311
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
Definition: objbenders.h:43
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
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:328