branch_coloring.c
Go to the documentation of this file.
35 * consider the following two constraints: SAME(v,w) and DIFFER(v,w). SAME(v,w) requires that both
36 * nodes v and w get the same color, whereas DIFFER(v,w) forbids this. For each pair of nodes, each
37 * feasible solution fulfills exactly one of these constraints. Hence, splitting the solution space
38 * into two parts, one fulfilling SAME(v,w) and the other DIFFER(v,w), does not cut off any feasible
43 * s1. Now choose two nodes v, w and another stable set s2, such that v is part of both stable sets,
45 * one with the restriction SAME(v,w), the other one with restriction DIFFER(v,w). Therefore, each
47 * assures that each coloring of the nodes in the respective subgraph assigns to both nodes the same
51/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
260 SCIP_CALL( COLORcreateConsStoreGraph(scip, &conssame, "same", currentcons, COLOR_CONSTYPE_SAME, node1, node2, childsame) );
261 SCIP_CALL( COLORcreateConsStoreGraph(scip, &consdiffer, "differ", currentcons, COLOR_CONSTYPE_DIFFER, node1, node2, childdiffer) );
322 SCIP_CALL( COLORcreateConsStoreGraph(scip, &conssame, "same", currentcons, COLOR_CONSTYPE_SAME, node1, node2, childsame) );
323 SCIP_CALL( COLORcreateConsStoreGraph(scip, &consdiffer, "differ", currentcons, COLOR_CONSTYPE_DIFFER, node1, node2, childdiffer) );
364 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY, BRANCHRULE_MAXDEPTH,
static SCIP_DECL_BRANCHEXECLP(branchExeclpColoring)
Definition: branch_coloring.c:80
SCIP_RETCODE SCIPincludeBranchruleColoring(SCIP *scip)
Definition: branch_coloring.c:351
static SCIP_DECL_BRANCHEXECPS(branchExecpsColoring)
Definition: branch_coloring.c:279
default branching rule for the vertex coloring problem
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
Definition: cons_storeGraph.c:893
SCIP_RETCODE COLORcreateConsStoreGraph(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONS *fatherconstraint, COLOR_CONSTYPE type, int node1, int node2, SCIP_NODE *stickingnode)
Definition: cons_storeGraph.c:792
int COLORconsGetRepresentative(SCIP *scip, int node)
Definition: cons_storeGraph.c:980
SCIP_CONS * COLORconsGetActiveStoreGraphCons(SCIP *scip)
Definition: cons_storeGraph.c:869
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9568
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip_prob.c:3323
SCIP_Real SCIPgetLocalTransEstimate(SCIP *scip)
Definition: scip_prob.c:3546
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:153
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
Definition: scip_branch.c:116
SCIP_RETCODE SCIPsetBranchruleExecPs(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECPS((*branchexecps)))
Definition: scip_branch.c:281
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:395
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1017
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:857
Definition: objbenders.h:44
void COLORprobGetStableSet(SCIP *scip, int setindex, int **stableset, int *nelements)
Definition: probdata_coloring.c:1032
SCIP_CONS * COLORprobGetConstraint(SCIP *scip, int node)
Definition: probdata_coloring.c:1205
Definition: struct_branch.h:79
Definition: struct_cons.h:47
Definition: struct_tree.h:142
Definition: struct_var.h:208
Definition: struct_scip.h:70