heur_init.h 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 there already is a starting solution. 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 distinguish 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.h.

#include "scip/scip.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	SCIPincludeHeurInit (SCIP *scip)

Function Documentation

SCIPincludeHeurInit()

SCIP_RETCODE SCIPincludeHeurInit

(

SCIP *

scip

)

creates the initial primal heuristic for coloring and includes it in 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().