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