Detailed Description

initial primal heuristic for the vertex coloring problem

Author: Gerald Gamrath

This file implements a heuristic which computes a starting solution for the coloring problem. It therefore computes maximal stable sets and creates one variable for each set, which is added to the LP.

The heuristic is called only one time: before solving the root node.

It checks, whether a solution-file was read in and a starting solution already exists. If this is not the case, an initial possible coloring is computed by a greedy method. After that, a tabu-search is called, which tries to reduce the number of colors needed. The tabu-search algorithm follows the description in

"A Survey of Local Search Methods for Graph Coloring"
by P. Galinier and A. Hertz
Computers & Operations Research, 33 (2006)

The tabu-search works as follows: given the graph and a number of colors it tries to color the nodes of the graph with at most the given number of colors. It starts with a random coloring. In each iteration, it counts the number of violated edges, that is, edges for which both incident nodes have the same color. It now switches one node to another color in each iteration, taking the node and color, that cause the greatest reduction of the number of violated edges, or if no such combination exists, the node and color that cause the smallest increase of that number. The former color of the node is forbidden for a couple of iterations in order to give the possibility to leave a local minimum.

As long as the tabu-search finds a solution with the given number of colors, this number is reduced by 1 and the tabu-search is called another time. If no coloring was found after a given number of iterations, the tabu-search is stopped and variables for all sets of the last feasible coloring are created and added to the LP (after possible extension to maximal stable sets).

The variables of these sets result in a feasible starting solution of the coloring problem.

The tabu-search can be deactivated by setting the parameter <heuristics/initcol/usetabu> to FALSE. The number of iterations after which the tabu-search stops if no solution was yet found can be changed by the param <heuristics/initcol/maxiter>. A great effect is also obtained by changing the parameters <heuristics/initcol/tabubase> and <heuristics/initcol/tabugamma>, which determine the number of iterations for which the former color of a node is forbidden; more precisely, this number is <tabubase> + ncritical * <tabugamma>, where ncritical is the number of nodes, which are incident to violated edges. Finally, the level of output and the frequency of status lines can be changed by <heuristics/initcol/output> and <heuristics/initcol/dispfreq>.

Definition in file heur_init.c.

#include <assert.h>
#include <string.h>
#include "heur_init.h"
#include "pricer_coloring.h"
#include "probdata_coloring.h"
#include "reader_col.h"
#include "scip/cons_setppc.h"
#include "cons_storeGraph.h"
#include "tclique/tclique.h"

Go to the source code of this file.

Macros
#define	HEUR_NAME "initcol"

#define	HEUR_DESC "initial primal heuristic for coloring"

#define	HEUR_DISPCHAR 't'

#define	HEUR_PRIORITY 1

#define	HEUR_FREQ 1

#define	HEUR_FREQOFS 0

#define	HEUR_MAXDEPTH 0

#define	HEUR_TIMING SCIP_HEURTIMING_BEFORENODE

#define	HEUR_USESSUBSCIP FALSE

#define	DEFAULT_USETABU TRUE

#define	DEFAULT_MAXITER 100000

#define	DEFAULT_TABUBASE 50

#define	DEFAULT_TABUGAMMA 0.9

#define	DEFAULT_OUTPUT 1

#define	DEFAULT_DISPFREQ 10000

Functions
static SCIP_Bool	hasUncoloredNode (int nnodes, int *colors)

static SCIP_RETCODE	greedyStableSet (SCIP scip, TCLIQUE_GRAPH graph, int *colors, int nextcolor)

static SCIP_RETCODE	greedyInitialColoring (SCIP scip, TCLIQUE_GRAPH graph, int colors, int ncolors)

static int	getNViolatedEdges (TCLIQUE_GRAPH graph, int colors)

static SCIP_RETCODE	runTabuCol (TCLIQUE_GRAPH graph, int seed, int maxcolors, int colors, SCIP_HEURDATA heurdata, SCIP_Bool success)

static	SCIP_DECL_HEURCOPY (heurCopyInit)

static	SCIP_DECL_HEURFREE (heurFreeInit)

static	SCIP_DECL_HEUREXEC (heurExecInit)

SCIP_RETCODE	SCIPincludeHeurInit (SCIP *scip)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "initcol"

Definition at line 83 of file heur_init.c.

Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeHeurInit().

◆ HEUR_DESC

#define HEUR_DESC "initial primal heuristic for coloring"

Definition at line 84 of file heur_init.c.

Referenced by SCIPincludeHeurInit().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR 't'

Definition at line 85 of file heur_init.c.

Referenced by SCIPincludeHeurInit().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY 1

Definition at line 86 of file heur_init.c.

Referenced by SCIPincludeHeurInit().

◆ HEUR_FREQ

#define HEUR_FREQ 1

Definition at line 87 of file heur_init.c.

Referenced by SCIPincludeHeurInit().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 88 of file heur_init.c.

Referenced by SCIPincludeHeurInit().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH 0

Definition at line 89 of file heur_init.c.

Referenced by SCIPincludeHeurInit().

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE

Definition at line 90 of file heur_init.c.

Referenced by SCIPincludeHeurInit().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 91 of file heur_init.c.

Referenced by SCIPincludeHeurInit().

◆ DEFAULT_USETABU

#define DEFAULT_USETABU TRUE

Definition at line 95 of file heur_init.c.

Referenced by SCIPincludeHeurInit().

◆ DEFAULT_MAXITER

#define DEFAULT_MAXITER 100000

Definition at line 96 of file heur_init.c.

Referenced by SCIPincludeHeurInit().

◆ DEFAULT_TABUBASE

#define DEFAULT_TABUBASE 50

Definition at line 97 of file heur_init.c.

Referenced by SCIPincludeHeurInit().

◆ DEFAULT_TABUGAMMA

#define DEFAULT_TABUGAMMA 0.9

Definition at line 98 of file heur_init.c.

Referenced by SCIPincludeHeurInit().

◆ DEFAULT_OUTPUT

#define DEFAULT_OUTPUT 1

Definition at line 99 of file heur_init.c.

Referenced by SCIPincludeHeurInit().

◆ DEFAULT_DISPFREQ

#define DEFAULT_DISPFREQ 10000

Definition at line 100 of file heur_init.c.

Referenced by SCIPincludeHeurInit().

Function Documentation

◆ hasUncoloredNode()

static SCIP_Bool hasUncoloredNode	(	int	nnodes,
		int *	colors
	)

static

checks whether one of the nodes has no color respectively has color -1 in the given array

Parameters

nnodes	the graph that should be colored
colors	array of ints representing the colors

Definition at line 130 of file heur_init.c.

References FALSE, nnodes, NULL, and TRUE.

Referenced by greedyInitialColoring().

◆ greedyStableSet()

static SCIP_RETCODE greedyStableSet	(	SCIP *	scip,
		TCLIQUE_GRAPH *	graph,
		int *	colors,
		int	nextcolor
	)

static

computes a stable set with a greedy-method and colors its nodes

Parameters

scip	SCIP data structure
graph	pointer to graph data structure
colors	array of ints representing the different colors, -1 means uncolored
nextcolor	color in which the stable set will be colored

Definition at line 153 of file heur_init.c.

References FALSE, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortDownIntInt(), tcliqueGetDegrees(), and TRUE.

Referenced by greedyInitialColoring().

◆ greedyInitialColoring()

static SCIP_RETCODE greedyInitialColoring	(	SCIP *	scip,
		TCLIQUE_GRAPH *	graph,
		int *	colors,
		int *	ncolors
	)

static

computes the initial coloring with a greedy method

Parameters

scip	SCIP data structure
graph	pointer to graph data structure
colors	array of ints representing the different colors
ncolors	number of colors needed

Definition at line 234 of file heur_init.c.

References COLORprobGetNNodes(), greedyStableSet(), hasUncoloredNode(), nnodes, NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by SCIP_DECL_HEUREXEC().

◆ getNViolatedEdges()

static int getNViolatedEdges	(	TCLIQUE_GRAPH *	graph,
		int *	colors
	)

static

computes the number of violated edges, that means the number of edges (i,j) where i and j have the same color

Parameters

graph	the graph
colors	colors of the nodes

Definition at line 274 of file heur_init.c.

References nnodes, NULL, tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().

Referenced by runTabuCol().

◆ runTabuCol()

static SCIP_RETCODE runTabuCol	(	TCLIQUE_GRAPH *	graph,
		int	seed,
		int	maxcolors,
		int *	colors,
		SCIP_HEURDATA *	heurdata,
		SCIP_Bool *	success
	)

static

runs tabu coloring heuristic, gets a graph and a number of colors and tries to color the graph with at most that many colors; starts with a random coloring and switches one node to another color in each iteration, forbidding the old color for a couple of iterations

Parameters

graph	the graph, that should be colored
seed	seed for the first random coloring
maxcolors	number of colors, which are allowed
colors	output: the computed coloring
heurdata	data of the heuristic
success	pointer to store if something went wrong

Definition at line 311 of file heur_init.c.

References FALSE, getNViolatedEdges(), nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, SCIPfreeMemoryArray, tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyInit )

static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 540 of file heur_init.c.

References HEUR_NAME, NULL, SCIP_OKAY, and SCIPheurGetName().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeInit )

static

destructor of primal heuristic to free user data (called when SCIP is exiting) ! [SnippetHeurFreeInit]

Definition at line 552 of file heur_init.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPheurGetData(), and SCIPheurSetData().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecInit )

static

! [SnippetHeurFreeInit] execution method of primal heuristic

Definition at line 568 of file heur_init.c.

References COLORprobAddNewStableSet(), COLORprobAddVarForStableSet(), COLORprobGetConstraints(), COLORprobGetGraph(), COLORprobGetNNodes(), COLORprobGetNStableSets(), COLORprobGetVarForStableSet(), FALSE, greedyInitialColoring(), nnodes, NULL, runTabuCol(), SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_FOUNDSOL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPaddCoefSetppc(), SCIPaddVar(), SCIPallocBufferArray, SCIPchgVarUbLazy(), SCIPcreateSol(), SCIPcreateVar(), SCIPfreeBufferArray, SCIPgetBoolParam(), SCIPheurGetData(), SCIPsetIntParam(), SCIPsetSolVal(), SCIPsortDownInt(), SCIPtrySolFree(), and TRUE.

◆ SCIPincludeHeurInit()

SCIP_RETCODE SCIPincludeHeurInit ( SCIP * scip )

creates the init primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 718 of file heur_init.c.

References DEFAULT_DISPFREQ, DEFAULT_MAXITER, DEFAULT_OUTPUT, DEFAULT_TABUBASE, DEFAULT_TABUGAMMA, DEFAULT_USETABU, FALSE, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocBlockMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurFree(), and TRUE.

Referenced by SCIPincludeColoringPlugins().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_USETABU

◆ DEFAULT_MAXITER

◆ DEFAULT_TABUBASE

◆ DEFAULT_TABUGAMMA

◆ DEFAULT_OUTPUT

◆ DEFAULT_DISPFREQ

Function Documentation

◆ hasUncoloredNode()

◆ greedyStableSet()

◆ greedyInitialColoring()

◆ getNViolatedEdges()

◆ runTabuCol()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEUREXEC()

◆ SCIPincludeHeurInit()