SCIP Doxygen Documentation
Loading...
Searching...
No Matches
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-2024 Zuse Institute Berlin (ZIB) */
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 */
83
SCIP_RETCODE
SCIPincludeHeurInit
(
84
SCIP
*
scip
/**< SCIP data structure */
85
);
86
87
#ifdef __cplusplus
88
}
89
#endif
90
91
#endif
SCIPincludeHeurInit
SCIP_RETCODE SCIPincludeHeurInit(SCIP *scip)
Definition
heur_init.c:718
scip
Definition
objbenders.h:44
scip.h
SCIP callable library.
Scip
Definition
struct_scip.h:70
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition
type_retcode.h:63
applications
Coloring
src
heur_init.h
© 2002-2024 by Zuse Institute Berlin (ZIB),
Imprint
Generated by
1.12.0