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 2002-2022 Zuse Institute Berlin */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file heur_init.h
26  * @brief initial primal heuristic for the vertex coloring problem
27  * @author Gerald Gamrath
28  *
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
31  * LP.
32  *
33  * The heuristic is called only one time: before solving the root node.
34  *
35  * It checks, whether a solution-file was read in and there already is a starting solution. If this
36  * is not the case, an initial possible coloring is computed by a greedy method. After that, a
37  * tabu-search is called, which tries to reduce the number of colors needed. The tabu-search algorithm
38  * follows the description in
39  *
40  * "A Survey of Local Search Methods for Graph Coloring"@n
41  * by P. Galinier and A. Hertz@n
42  * Computers & Operations Research, 33 (2006)
43  *
44  * The tabu-search works as follows: given the graph and a number of colors it tries to color the
45  * nodes of the graph with at most the given number of colors. It starts with a random coloring. In
46  * each iteration, it counts the number of violated edges, that is, edges for which both incident
47  * nodes have the same color. It now switches one node to another color in each iteration, taking
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
51  * to leave a local minimum.
52  *
53  * As long as the tabu-search finds a solution with the given number of colors, this number is reduced
54  * by 1 and the tabu-search is called another time. If no coloring was found after a given number
55  * of iterations, the tabu-search is stopped and variables for all sets of the last feasible coloring
56  * are created and added to the LP (after possible extension to maximal stable sets).
57  *
58  * The variables of these sets result in a feasible starting solution of the coloring problem.
59  *
60  * The tabu-search can be deactivated by setting the parameter <heuristics/initcol/usetabu> to
61  * FALSE. The number of iterations after which the tabu-search stops if no solution was yet found
62  * can be changed by the param <heuristics/initcol/maxiter>. A great effect is also obtained by
63  * changing the parameters <heuristics/initcol/tabubase> and <heuristics/initcol/tabugamma>, which
64  * distinguish the number of iterations for which the former color of a node is forbidden; more
65  * precisely, this number is <tabubase> + ncritical * <tabugamma>, where ncritical is the number
66  * of nodes, which are incident to violated edges. Finally, the level of output and the frequency of
67  * status lines can be changed by <heuristics/initcol/output> and <heuristics/initcol/dispfreq>.
68  */
69 
70 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
71 
72 #ifndef __SCIP_HEUR_INIT_H__
73 #define __SCIP_HEUR_INIT_H__
74 
75 
76 #include "scip/scip.h"
77 
78 #ifdef __cplusplus
79 extern "C" {
80 #endif
81 
82 /** creates the initial primal heuristic for coloring and includes it in SCIP */
84  SCIP* scip /**< SCIP data structure */
85  );
86 
87 #ifdef __cplusplus
88 }
89 #endif
90 
91 #endif
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_RETCODE SCIPincludeHeurInit(SCIP *scip)
Definition: heur_init.c:718
SCIP callable library.