Scippy

SCIP

Solving Constraint Integer Programs

branch_coloring.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-2019 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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file branch_coloring.h
17  * @brief default branching rule for the vertex coloring problem
18  * @author Gerald Gamrath
19  *
20  * This file implements the standard branching rule for the coloring algorithm.
21  *
22  * As we use column generation, we may not branch on the variables themselves,
23  * but on some sort of constraints that we introduce in the pricing problem.
24  *
25  * In our case, we choose two nodes v and w, which are not adjacent in the current graph, and
26  * consider the following two constraints: SAME(v,w) and DIFFER(v,w). SAME(v,w) requires that both
27  * nodes v and w get the same color, whereas DIFFER(v,w) forbids this. For each pair of nodes, each
28  * feasible solution fulfills exactly one of these constraints. Hence, splitting the solution space
29  * into two parts, one fulfilling SAME(v,w) and the other DIFFER(v,w), does not cut off any feasible
30  * solution and can therefore be used as the branching rule.
31  *
32  * The branching is done as follows: Given the optimal (fractional) solution of the current
33  * branch-and-bound node, choose the most fractional variable and the corresponding stable set
34  * s1. Now choose two nodes v, w and another stable set s2, such that v is part of both stable sets,
35  * whereas w is part of exactly one of the stable sets. Create two children of the current node,
36  * one with the restriction SAME(v,w), the other one with restriction DIFFER(v,w). Therefore, each
37  * node gets a constraint of type @c cons_storeGraph, which enforces the branching decision and
38  * assures that each coloring of the nodes in the respective subgraph assigns to both nodes the same
39  * color/different colors by fixing stable sets to 0 that violate this constraint.
40  */
41 
42 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
43 
44 #ifndef __SCIP_BRANCH_COLORING_H__
45 #define __SCIP_BRANCH_COLORING_H__
46 
47 
48 #include "scip/scip.h"
49 #include "probdata_coloring.h"
50 #include "cons_storeGraph.h"
51 #include "scip/cons_setppc.h"
52 
53 #ifdef __cplusplus
54 extern "C" {
55 #endif
56 
57 /** creates the coloring branching rule and includes it in SCIP */
58 extern
60  SCIP* scip /**< SCIP data structure */
61  );
62 
63 #ifdef __cplusplus
64 }
65 #endif
66 
67 #endif
problem data for vertex coloring algorithm
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_RETCODE SCIPincludeBranchruleColoring(SCIP *scip)
constraint handler for storing the graph at each node of the tree
Constraint handler for the set partitioning / packing / covering constraints .
SCIP callable library.