Scippy

SCIP

Solving Constraint Integer Programs

heur_init.c File Reference

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.

◆ HEUR_DESC

#define HEUR_DESC   "initial primal heuristic for coloring"

Definition at line 84 of file heur_init.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   't'

Definition at line 85 of file heur_init.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   1

Definition at line 86 of file heur_init.c.

◆ HEUR_FREQ

#define HEUR_FREQ   1

Definition at line 87 of file heur_init.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 88 of file heur_init.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   0

Definition at line 89 of file heur_init.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE

Definition at line 90 of file heur_init.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 91 of file heur_init.c.

◆ DEFAULT_USETABU

#define DEFAULT_USETABU   TRUE

Definition at line 95 of file heur_init.c.

◆ DEFAULT_MAXITER

#define DEFAULT_MAXITER   100000

Definition at line 96 of file heur_init.c.

◆ DEFAULT_TABUBASE

#define DEFAULT_TABUBASE   50

Definition at line 97 of file heur_init.c.

◆ DEFAULT_TABUGAMMA

#define DEFAULT_TABUGAMMA   0.9

Definition at line 98 of file heur_init.c.

◆ DEFAULT_OUTPUT

#define DEFAULT_OUTPUT   1

Definition at line 99 of file heur_init.c.

◆ DEFAULT_DISPFREQ

#define DEFAULT_DISPFREQ   10000

Definition at line 100 of file heur_init.c.

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
nnodesthe graph that should be colored
colorsarray 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
scipSCIP data structure
graphpointer to graph data structure
colorsarray of ints representing the different colors, -1 means uncolored
nextcolorcolor 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
scipSCIP data structure
graphpointer to graph data structure
colorsarray of ints representing the different colors
ncolorsnumber 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
graphthe graph
colorscolors 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
graphthe graph, that should be colored
seedseed for the first random coloring
maxcolorsnumber of colors, which are allowed
colorsoutput: the computed coloring
heurdatadata of the heuristic
successpointer 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()

◆ SCIPincludeHeurInit()