Scippy

SCIP

Solving Constraint Integer Programs

branch_strongcoloring.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_strongcoloring.h
17  * @brief branching rule performing strong branching for the vertex coloring problem
18  * @author Gerald Gamrath
19  *
20  * This file implements an additional branching rule for the coloring algorithm.
21  *
22  * We are looking for two nodes v and w, which are not adjacent in the current graph, and consider
23  * the following two constraints: SAME(v,w) and DIFFER(v,w). More information about the meaning of
24  * these constraints can be found in the documentation of the branching rule in branch_coloring.c.
25  *
26  * This branching rule puts some more effort into the choice of the two nodes and performs a
27  * strongbranching. This means that for every possible choice of two nodes, it solves the LPs of the
28  * created children and computes a score with respect to the increase of the lower bound in both
29  * nodes. After that, it takes the combination of nodes yielding the best score. The interesting
30  * point is that the strongbranching is not performed for each variable, as it is done in some
31  * default branching rules of SCIP and supported by the LP-solver, but is done for a constraint,
32  * since we are branching on constraints. Look at executeStrongBranching() to see how it is
33  * done. There are also some improvements, since testing all possible combination of nodes is very
34  * expensive. The first possibility to avoid this is to stop the computation of scores once a
35  * possible branching is found that has only one feasible child. This results in more restrictions
36  * in this child without increasing the number of unprocessed nodes.
37  *
38  * The second improvement is to compute a priority for all possible combinations, w.r.t. the
39  * fractional values of the variables. Then, only the first best k combinations are investigated by
40  * strongbranching.
41  *
42  * This code is not optimized and in most cases inferior to the standard branching rule. It is only
43  * a demonstration of how to perform strongbranching on constraints!
44  */
45 
46 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
47 
48 #ifndef __SCIP_BRANCH_STRONGCOLORING_H__
49 #define __SCIP_BRANCH_STRONGCOLORING_H__
50 
51 
52 #include "scip/scip.h"
53 #include "probdata_coloring.h"
54 #include "cons_storeGraph.h"
55 #include "scip/cons_linear.h"
56 
57 #ifdef __cplusplus
58 extern "C" {
59 #endif
60 
61 /** creates the coloring branching rule and includes it in SCIP */
63  SCIP* scip /**< SCIP data structure */
64  );
65 
66 #ifdef __cplusplus
67 }
68 #endif
69 
70 #endif
problem data for vertex coloring algorithm
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
constraint handler for storing the graph at each node of the tree
SCIP_RETCODE SCIPincludeBranchruleStrongcoloring(SCIP *scip)
Constraint handler for linear constraints in their most general form, .
SCIP callable library.