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 */