SCIP Doxygen Documentation
Loading...
Searching...
No Matches
xternal_coloring.c
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 xternal_coloring.c
26
* @brief main document page
27
* @author Gerald Gamrath
28
*/
29
30
/*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31
32
/**@page COLORING_MAIN Coloring
33
* @version 0.1
34
* @author Gerald Gamrath
35
*
36
* This branch-and-price graph coloring code gives an example for
37
* a pricer and associated modules.
38
*
39
* It implements the approach described in
40
*
41
* "A column generation approach for graph coloring"@n
42
* by Anuj Mehrotra and Micheal A. Trick,@n
43
* INFORMS J. Comput. 8, no. 4, 1995, pp. 344-354.
44
*
45
* The input format for the graph files is the DIMACS standard format; the name of the file must end with ".col".
46
*
47
* The graph coloring problem is the following:
48
*
49
* Given a graph \f$G = (V,E)\f$, the goal is to assign a color to each vertex, such that no
50
* adjacent vertices have the same color; the number of colors needed should be minimized.
51
*
52
* We use the following integer programming model: We have binary
53
* variables \f$ x_{s}, s \in \mathcal{S}\f$ where \f$\mathcal{S}\f$
54
* is the set of all stable sets in the graph \f$G\f$.
55
*
56
* The basic model is then:
57
* \f[
58
* \begin{array}[t]{rl}
59
* \min & \displaystyle \sum_{s \in \mathcal{S}} x_{s} \\
60
* & \\
61
* s.t. & \displaystyle \sum_{s \in \mathcal{S}, v \in s} x_{s} \ge 1 \quad \forall v \in V \\
62
* \end{array}
63
* \f]
64
*
65
* Since the number of stable sets can be exponential in the size of the graph, the algorithm starts
66
* with some subset \f$ \bar{\mathcal{S}} \subseteq \mathcal{S}\f$ of the stable sets and adds
67
* further stable sets during the solution process. This way it tries to improve the current LP
68
* solution.
69
*
70
* Further information about particular modules like the pricing routine and the
71
* branching rule can be found in the documentation of the corresponding files.
72
*
73
* The pricer pricer_coloring.c shows how to perform column generation in SCIP. The constraint
74
* handler cons_storeGraph.c demonstrates how to store branching decisions at nodes und enforce them
75
* by propagation. The default branching rule branch_coloring.c describes how these constraints are
76
* added to the branch-and-bound nodes. Some more sophisticated approaches for the branching,
77
* especially a strongbranching on these constraints, can be found in the second branching rule
78
* branch_strongcoloring.c. An initial solution is computed by a start heuristic which is
79
* described in heur_init.c. The organization of the data for the problem is described in the
80
* problem data file (probdata_coloring.c). The file readers are described in reader_col.c and
81
* reader_csol.c.
82
*
83
* Installation
84
* ------------
85
*
86
* See the @ref INSTALL_APPLICATIONS_EXAMPLES "Install file"
87
*
88
*
89
*/
applications
Coloring
doc
xternal_coloring.c
© 2002-2024 by Zuse Institute Berlin (ZIB),
Imprint
Generated by
1.12.0