Scippy

SCIP

Solving Constraint Integer Programs

heur_init.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_init.h
17  * @brief initial primal heuristic for the vertex coloring problem
18  * @author Gerald Gamrath
19  *
20  * This file implements a heuristic which computes a starting solution for the coloring problem. It
21  * therefore computes maximal stable sets and creates one variable for each set, which is added to the
22  * LP.
23  *
24  * The heuristic is called only one time: before solving the root node.
25  *
26  * It checks, whether a solution-file was read in and there already is a starting solution. If this
27  * is not the case, an initial possible coloring is computed by a greedy method. After that, a
28  * tabu-search is called, which tries to reduce the number of colors needed. The tabu-search algorithm
29  * follows the description in
30  *
31  * "A Survey of Local Search Methods for Graph Coloring"@n
32  * by P. Galinier and A. Hertz@n
33  * Computers & Operations Research, 33 (2006)
34  *
35  * The tabu-search works as follows: given the graph and a number of colors it tries to color the
36  * nodes of the graph with at most the given number of colors. It starts with a random coloring. In
37  * each iteration, it counts the number of violated edges, that is, edges for which both incident
38  * nodes have the same color. It now switches one node to another color in each iteration, taking
39  * the node and color, that cause the greatest reduction of the number of violated edges, or if no
40  * such combination exists, the node and color that cause the smallest increase of that number. The
41  * former color of the node is forbidden for a couple of iterations in order to give the possibility
42  * to leave a local minimum.
43  *
44  * As long as the tabu-search finds a solution with the given number of colors, this number is reduced
45  * by 1 and the tabu-search is called another time. If no coloring was found after a given number
46  * of iterations, the tabu-search is stopped and variables for all sets of the last feasible coloring
47  * are created and added to the LP (after possible extension to maximal stable sets).
48  *
49  * The variables of these sets result in a feasible starting solution of the coloring problem.
50  *
51  * The tabu-search can be deactivated by setting the parameter <heuristics/initcol/usetabu> to
52  * FALSE. The number of iterations after which the tabu-search stops if no solution was yet found
53  * can be changed by the param <heuristics/initcol/maxiter>. A great effect is also obtained by
54  * changing the parameters <heuristics/initcol/tabubase> and <heuristics/initcol/tabugamma>, which
55  * distinguish the number of iterations for which the former color of a node is forbidden; more
56  * precisely, this number is <tabubase> + ncritical * <tabugamma>, where ncritical is the number
57  * of nodes, which are incident to violated edges. Finally, the level of output and the frequency of
58  * status lines can be changed by <heuristics/initcol/output> and <heuristics/initcol/dispfreq>.
59  */
60 
61 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
62 
63 #ifndef __SCIP_HEUR_INIT_H__
64 #define __SCIP_HEUR_INIT_H__
65 
66 
67 #include "scip/scip.h"
68 
69 #ifdef __cplusplus
70 extern "C" {
71 #endif
72 
73 /** creates the initial primal heuristic for coloring and includes it in SCIP */
75  SCIP* scip /**< SCIP data structure */
76  );
77 
78 #ifdef __cplusplus
79 }
80 #endif
81 
82 #endif
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPincludeHeurInit(SCIP *scip)
Definition: heur_init.c:698
SCIP callable library.