branching rule performing strong branching for the vertex coloring problem
This file implements an additional branching rule for the coloring algorithm.
We are looking for 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). More information about the meaning of these constraints can be found in the documentation of the branching rule in branch_coloring.c.
This branching rule puts some more effort into the choice of the two nodes and performs a strongbranching. This means that for every possible choice of two nodes, it solves the LPs of the created children and computes a score with respect to the increase of the lower bound in both nodes. After that, it takes the combination of nodes yielding the best score. The interesting point is that the strongbranching is not performed for each variable, as it is done in some default branching rules of SCIP and supported by the LP-solver, but is done for a constraint, since we are branching on constraints. Look at executeStrongBranching() to see how it is done. There are also some improvements, since testing all possible combination of nodes is very expensive. The first possibility to avoid this is to stop the computation of scores once a possible branching is found that has only one feasible child. This results in more restrictions in this child without increasing the number of unprocessed nodes.
The second improvement is to compute a priority for all possible combinations, w.r.t. the fractional values of the variables. Then, only the first best k combinations are investigated by strongbranching.
This code is not optimized and in most cases inferior to the standard branching rule. It is only a demonstration of how to perform strongbranching on constraints!
Definition in file branch_strongcoloring.c.
#include <assert.h>
#include <string.h>
#include "branch_strongcoloring.h"
#include "pricer_coloring.h"
Go to the source code of this file.
Macros | |
#define | BRANCHRULE_NAME "strongcoloring" |
#define | BRANCHRULE_DESC "branching rule template" |
#define | BRANCHRULE_PRIORITY 15000 |
#define | BRANCHRULE_MAXDEPTH -1 |
#define | BRANCHRULE_MAXBOUNDDIST 1.0 |
#define | DEFAULT_BRANCHINGMODE 2 |
#define | DEFAULT_FIXINGSSCOREMODE 3 |
#define | DEFAULT_MAXPRICINGROUNDS -1 |
#define | DEFAULT_USETCLIQUE TRUE |
#define | DEFAULT_LOOKAHEAD 10 |
Functions | |
static double | computeScore (SCIP_Real val1, SCIP_Real val2) |
static SCIP_Real | computeFixingsScore (SCIP_Real samevalue, SCIP_Real differvalue, SCIP_BRANCHRULEDATA *branchruledata) |
static int | nodes2index (SCIP *scip, int node1, int node2) |
static void | index2nodes (SCIP *scip, int ind, int *node1, int *node2) |
static SCIP_RETCODE | computeBranchingPriorities (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata) |
static SCIP_RETCODE | executeStrongBranching (SCIP *scip, COLOR_CONSTYPE constype, int node1, int node2, SCIP_BRANCHRULEDATA *branchruledata, SCIP_Real *newlb) |
static | SCIP_DECL_SORTINDCOMP (consdataCompValues) |
static | SCIP_DECL_BRANCHCOPY (branchCopyStrongcoloring) |
static | SCIP_DECL_BRANCHEXECLP (branchExeclpStrongcoloring) |
static | SCIP_DECL_BRANCHFREE (branchFreeStrongcoloring) |
static | SCIP_DECL_BRANCHINIT (branchInitStrongcoloring) |
static | SCIP_DECL_BRANCHEXIT (branchExitStrongcoloring) |
SCIP_RETCODE | SCIPincludeBranchruleStrongcoloring (SCIP *scip) |
#define BRANCHRULE_NAME "strongcoloring" |
Definition at line 62 of file branch_strongcoloring.c.
#define BRANCHRULE_DESC "branching rule template" |
Definition at line 63 of file branch_strongcoloring.c.
#define BRANCHRULE_PRIORITY 15000 |
Definition at line 64 of file branch_strongcoloring.c.
#define BRANCHRULE_MAXDEPTH -1 |
Definition at line 65 of file branch_strongcoloring.c.
#define BRANCHRULE_MAXBOUNDDIST 1.0 |
Definition at line 66 of file branch_strongcoloring.c.
#define DEFAULT_BRANCHINGMODE 2 |
Definition at line 69 of file branch_strongcoloring.c.
Referenced by SCIPincludeBranchruleStrongcoloring().
#define DEFAULT_FIXINGSSCOREMODE 3 |
Definition at line 70 of file branch_strongcoloring.c.
Referenced by SCIPincludeBranchruleStrongcoloring().
#define DEFAULT_MAXPRICINGROUNDS -1 |
Definition at line 71 of file branch_strongcoloring.c.
Referenced by SCIPincludeBranchruleStrongcoloring().
#define DEFAULT_USETCLIQUE TRUE |
Definition at line 72 of file branch_strongcoloring.c.
Referenced by SCIPincludeBranchruleStrongcoloring(), and SCIPincludePricerColoring().
#define DEFAULT_LOOKAHEAD 10 |
Definition at line 73 of file branch_strongcoloring.c.
Referenced by SCIPincludeBranchruleStrongcoloring().
computes a score for the two improvements that are achieved in the two sons for a branching decision
val1 | the first value |
val2 | the second value |
Definition at line 108 of file branch_strongcoloring.c.
References MAX, MIN, and SCIP_Real.
Referenced by SCIP_DECL_BRANCHEXECLP().
|
static |
computes a score for the fractional values of the variables that would be fixed to zero for a same- or differ-branching
samevalue | value of the fractional variables fixed to 0 for a same-branching |
differvalue | value of the fractional variables fixed to 0 for a differ-branching |
branchruledata | branching rule data |
Definition at line 118 of file branch_strongcoloring.c.
References SCIP_Real.
Referenced by SCIP_DECL_BRANCHEXECLP().
|
static |
for given nodes node1, node2, compute the corresponding index in the arrays branchruledata->same-/differvalue
scip | SCIP data structure |
node1 | the first node |
node2 | the second node |
Definition at line 147 of file branch_strongcoloring.c.
References assert(), COLORprobGetNNodes(), i, nnodes, and NULL.
Referenced by computeBranchingPriorities().
|
static |
for given index of the arrays branchruledata->same-/differvalue, compute the two nodes, the index represents
scip | SCIP data structure |
ind | the given index in the arrays |
node1 | return value: the first node |
node2 | return value: the second node |
Definition at line 178 of file branch_strongcoloring.c.
References assert(), COLORprobGetNNodes(), nnodes, and NULL.
Referenced by computeBranchingPriorities(), and SCIP_DECL_BRANCHEXECLP().
|
static |
computes for each pair of nodes (i,j) two values, one for same (i,j), the other for differ(i,j) which are the sum of the values of variables with fractional parts, that would be fixed for this decision asd
scip | SCIP data structure |
branchruledata | the data of the branching rule |
Definition at line 206 of file branch_strongcoloring.c.
References assert(), COLORconsGetCurrentGraph(), COLORconsGetRepresentative(), COLORprobGetNNodes(), COLORprobGetStableSet(), COLORprobIsNodeInStableSet(), i, index2nodes(), lpcands, lpcandsfrac, nlpcands, nnodes, nodes2index(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetLPBranchCands(), SCIPisFeasPositive(), SCIPvarGetData(), and var.
Referenced by SCIP_DECL_BRANCHEXECLP().
|
static |
computes the lower bound that would a child node with the given branching decision would have
scip | SCIP data structure |
constype | the type of the contraint: SAME or DIFFER |
node1 | the first node for the branching constraint |
node2 | the second node for the branching constraint |
branchruledata | the data of the branching rule |
newlb | pointer to store the resulting value |
Definition at line 316 of file branch_strongcoloring.c.
References assert(), COLORconsGetActiveStoreGraphCons(), COLORcreateConsStoreGraph(), cutoff, FALSE, lperror, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddConsNode(), SCIPdelCons(), SCIPendProbing(), SCIPgetCurrentNode(), SCIPgetLPObjval(), SCIPnewProbingNode(), SCIPpropagateProbing(), SCIPreleaseCons(), SCIPsolveProbingLPWithPricing(), and SCIPstartProbing().
Referenced by SCIP_DECL_BRANCHEXECLP().
|
static |
index comparison method two values in a real array
Definition at line 364 of file branch_strongcoloring.c.
|
static |
copy method for branchrule plugins (called when SCIP copies plugins)
Definition at line 390 of file branch_strongcoloring.c.
References assert(), BRANCHRULE_NAME, NULL, SCIP_OKAY, and SCIPbranchruleGetName().
|
static |
branching execution method for fractional LP solutions
Definition at line 402 of file branch_strongcoloring.c.
References assert(), BMSclearMemoryArray, BRANCHRULE_NAME, COLOR_CONSTYPE_DIFFER, COLOR_CONSTYPE_SAME, COLORconsGetActiveStoreGraphCons(), COLORconsGetCurrentGraph(), COLORconsGetRepresentative(), COLORcreateConsStoreGraph(), COLORprobGetConstraint(), COLORprobGetNNodes(), computeBranchingPriorities(), computeFixingsScore(), computeScore(), executeStrongBranching(), FALSE, i, index2nodes(), nnodes, NULL, result, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIPaddConsNode(), SCIPallocBufferArray, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPconsIsEnabled(), SCIPcreateChild(), SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLocalTransEstimate(), SCIPgetLPObjval(), SCIPisFeasZero(), SCIPisSumNegative(), SCIPreleaseCons(), SCIPsetBoolParam(), SCIPsort(), and TRUE.
|
static |
destructor of branching rule to free user data (called when SCIP is exiting)
Definition at line 687 of file branch_strongcoloring.c.
References NULL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleSetData(), and SCIPfreeBlockMemory.
|
static |
initialization method of branching rule (called after problem was transformed)
Definition at line 701 of file branch_strongcoloring.c.
References assert(), COLORprobGetNNodes(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, and SCIPbranchruleGetData().
|
static |
deinitialization method of branching rule (called before transformed problem is freed)
Definition at line 721 of file branch_strongcoloring.c.
References assert(), NULL, SCIP_OKAY, SCIPbranchruleGetData(), and SCIPfreeBlockMemoryArray.
SCIP_RETCODE SCIPincludeBranchruleStrongcoloring | ( | SCIP * | scip | ) |
creates the coloring branching rule and includes it in SCIP
scip | SCIP data structure |
Definition at line 743 of file branch_strongcoloring.c.
References assert(), BRANCHRULE_DESC, BRANCHRULE_MAXBOUNDDIST, BRANCHRULE_MAXDEPTH, BRANCHRULE_NAME, BRANCHRULE_PRIORITY, DEFAULT_BRANCHINGMODE, DEFAULT_FIXINGSSCOREMODE, DEFAULT_LOOKAHEAD, DEFAULT_MAXPRICINGROUNDS, DEFAULT_USETCLIQUE, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPallocBlockMemory, SCIPincludeBranchruleBasic(), SCIPsetBranchruleCopy(), SCIPsetBranchruleExecLp(), SCIPsetBranchruleExit(), SCIPsetBranchruleFree(), SCIPsetBranchruleInit(), and TRUE.
Referenced by SCIPincludeColoringPlugins().