Detailed Description
default branching rule for the vertex coloring problem
This file implements the standard branching rule for the coloring algorithm.
As we use column generation, we may not branch on the variables themselves, but on some sort of constraints that we introduce in the pricing problem.
In our case, we choose two nodes v and w, which are not adjacent in the current graph, and consider the following two constraints: SAME(v,w) and DIFFER(v,w). SAME(v,w) requires that both nodes v and w get the same color, whereas DIFFER(v,w) forbids this. For each pair of nodes, each feasible solution fulfills exactly one of these constraints. Hence, splitting the solution space into two parts, one fulfilling SAME(v,w) and the other DIFFER(v,w), does not cut off any feasible solution and can therefore be used as the branching rule.
The branching is done as follows: Given the optimal (fractional) solution of the current branch-and-bound node, choose the most fractional variable and the corresponding stable set s1. Now choose two nodes v, w and another stable set s2, such that v is part of both stable sets, whereas w is part of exactly one of the stable sets. Create two children of the current node, one with the restriction SAME(v,w), the other one with restriction DIFFER(v,w). Therefore, each node gets a constraint of type cons_storeGraph
, which enforces the branching decision and assures that each coloring of the nodes in the respective subgraph assigns to both nodes the same color/different colors by fixing stable sets to 0 that violate this constraint.
Definition in file branch_coloring.c.
Go to the source code of this file.
Macros | |
#define | BRANCHRULE_NAME "coloring" |
#define | BRANCHRULE_DESC "branching rule template" |
#define | BRANCHRULE_PRIORITY 50000 |
#define | BRANCHRULE_MAXDEPTH -1 |
#define | BRANCHRULE_MAXBOUNDDIST 1.0 |
Functions | |
static | SCIP_DECL_BRANCHCOPY (branchCopyColoring) |
static | SCIP_DECL_BRANCHEXECLP (branchExeclpColoring) |
static | SCIP_DECL_BRANCHEXECPS (branchExecpsColoring) |
SCIP_RETCODE | SCIPincludeBranchruleColoring (SCIP *scip) |
Macro Definition Documentation
◆ BRANCHRULE_NAME
#define BRANCHRULE_NAME "coloring" |
Definition at line 57 of file branch_coloring.c.
Referenced by SCIP_DECL_BRANCHCOPY(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_BRANCHEXECPS(), and SCIPincludeBranchruleColoring().
◆ BRANCHRULE_DESC
#define BRANCHRULE_DESC "branching rule template" |
Definition at line 58 of file branch_coloring.c.
Referenced by SCIPincludeBranchruleColoring().
◆ BRANCHRULE_PRIORITY
#define BRANCHRULE_PRIORITY 50000 |
Definition at line 59 of file branch_coloring.c.
Referenced by SCIPincludeBranchruleColoring().
◆ BRANCHRULE_MAXDEPTH
#define BRANCHRULE_MAXDEPTH -1 |
Definition at line 60 of file branch_coloring.c.
Referenced by SCIPincludeBranchruleColoring().
◆ BRANCHRULE_MAXBOUNDDIST
#define BRANCHRULE_MAXBOUNDDIST 1.0 |
Definition at line 61 of file branch_coloring.c.
Referenced by SCIPincludeBranchruleColoring().
Function Documentation
◆ SCIP_DECL_BRANCHCOPY()
|
static |
copy method for branchrule plugins (called when SCIP copies plugins)
Definition at line 69 of file branch_coloring.c.
References BRANCHRULE_NAME, NULL, SCIP_OKAY, and SCIPbranchruleGetName().
◆ SCIP_DECL_BRANCHEXECLP()
|
static |
branching execution method for fractional LP solutions
Definition at line 80 of file branch_coloring.c.
References BRANCHRULE_NAME, COLOR_CONSTYPE_DIFFER, COLOR_CONSTYPE_SAME, COLORconsGetActiveStoreGraphCons(), COLORconsGetCurrentGraph(), COLORconsGetRepresentative(), COLORcreateConsStoreGraph(), COLORprobGetConstraint(), COLORprobGetStableSet(), NULL, SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIPaddConsNode(), SCIPbranchruleGetName(), SCIPconsIsEnabled(), SCIPcreateChild(), SCIPgetLocalTransEstimate(), SCIPgetLPBranchCands(), SCIPgetNVarsSetppc(), SCIPgetVarsSetppc(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPreleaseCons(), SCIPvarGetData(), and SCIPvarGetUbLocal().
◆ SCIP_DECL_BRANCHEXECPS()
|
static |
branching execution method for not completely fixed pseudo solutions
Definition at line 279 of file branch_coloring.c.
References BRANCHRULE_NAME, COLOR_CONSTYPE_DIFFER, COLOR_CONSTYPE_SAME, COLORconsGetActiveStoreGraphCons(), COLORconsGetCurrentGraph(), COLORconsGetRepresentative(), COLORcreateConsStoreGraph(), COLORprobGetNNodes(), NULL, SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPaddConsNode(), SCIPbranchruleGetName(), SCIPcreateChild(), SCIPgetLocalTransEstimate(), and SCIPreleaseCons().
◆ SCIPincludeBranchruleColoring()
SCIP_RETCODE SCIPincludeBranchruleColoring | ( | SCIP * | scip | ) |
creates the coloring branching rule and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 351 of file branch_coloring.c.
References BRANCHRULE_DESC, BRANCHRULE_MAXBOUNDDIST, BRANCHRULE_MAXDEPTH, BRANCHRULE_NAME, BRANCHRULE_PRIORITY, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeBranchruleBasic(), SCIPsetBranchruleCopy(), SCIPsetBranchruleExecLp(), and SCIPsetBranchruleExecPs().
Referenced by SCIPincludeColoringPlugins().