branch_strongcoloring.c
Go to the documentation of this file.
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.
27 * strongbranching. This means that for every possible choice of two nodes, it solves the LPs of the
33 * done. There are also some improvements, since testing all possible combination of nodes is very
35 * possible branching is found that has only one feasible child. This results in more restrictions
39 * fractional values of the variables. Then, only the first best k combinations are investigated by
42 * This code is not optimized and in most cases inferior to the standard branching rule. It is only
46 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
77 2: strong branching with prior sorting of candidates w.r.t. the fractional value of concerned sets */
78 int length; /* length of the arrays samevalue and differvalue, length = n*(n-1)/2 with n = NNodes*/
79 SCIP_Real* samevalue; /* value of variables, that would be fixed to 0 for same(i,j), index = nodes2index(i,j) */
80 SCIP_Real* differvalue; /* value of variables, that would be fixed to 0 for differ(i,j), index = nodes2index(i,j) */
81 SCIP_Real* combinedvalue; /* combination of samevalue and differvalue, computed by computeScore*/
83 SCIP_Bool usetclique; /* should the exact pricing with the tclique-algorithm be used for the strongbranchings? */
84 int maxpricingrounds; /* maximal number of pricing rounds used for each probing node in the strongbranching */
86 int fixingsscoremode; /* determines the weightings of the two factors for prior sorting by fractional LP value */
97 /** computes a score for the two improvements that are achieved in the two sons for a branching decision */
107 /** computes a score for the fractional values of the variables that would be fixed to zero for a same- or differ-branching */
111 SCIP_Real differvalue, /**< value of the fractional variables fixed to 0 for a differ-branching*/
136 /** for given nodes node1, node2, compute the corresponding index in the arrays branchruledata->same-/differvalue */
167 /** for given index of the arrays branchruledata->same-/differvalue, compute the two nodes, the index represents */
193 /** 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
242 /* for all branching candidates (variables with fractional value) check for which branching decisions they would be
243 fixed to 0 and add the fractional part to the related entry in the array samevalue or differvalue */
285 assert(COLORprobIsNodeInStableSet(scip, setindex, node1) && COLORprobIsNodeInStableSet(scip, setindex, node2));
292 assert(COLORprobIsNodeInStableSet(scip, setindex, node1) && !COLORprobIsNodeInStableSet(scip, setindex, node2));
305 /** computes the lower bound that would a child node with the given branching decision would have */
334 SCIP_CALL( COLORcreateConsStoreGraph(scip, &cons, "probingcons", currentcons, constype, node1, node2, newnode) );
339 SCIP_CALL( SCIPsolveProbingLPWithPricing(scip, FALSE, FALSE, branchruledata->maxpricingrounds, &lperror, &cutoff) );
450 branchruledata->combinedvalue[i] = computeFixingsScore(branchruledata->samevalue[i], branchruledata->differvalue[i], branchruledata);
454 SCIPsort(branchruledata->permutation, consdataCompValues, branchruledata->combinedvalue, branchruledata->length);
468 SCIP_CALL( executeStrongBranching(scip, COLOR_CONSTYPE_SAME, node1, node2, branchruledata, &sameLb) );
475 SCIP_CALL( executeStrongBranching(scip, COLOR_CONSTYPE_DIFFER, node1, node2, branchruledata, &differLb) );
482 assert( !SCIPisFeasZero(scip, score) || (SCIPisFeasZero(scip, 0.2 * (sameLb-currLb)) && SCIPisFeasZero(scip, 0.2 * (differLb-currLb))
521 for ( i = SCIPgetDepth(scip)%nnodes; (start || (i != SCIPgetDepth(scip)%nnodes)); i=((i+1)%nnodes) )
557 SCIP_CALL( executeStrongBranching(scip, COLOR_CONSTYPE_SAME, node1, node2, branchruledata, &sameLb) );
564 SCIP_CALL( executeStrongBranching(scip, COLOR_CONSTYPE_DIFFER, node1, node2, branchruledata, &differLb) );
606 /* branchingmode >= 1 --> only create nodes, that do not have a LP solution that is much bigger than the lower bound */
618 SCIP_CALL( COLORcreateConsStoreGraph(scip, &consdiffer, "differ", currentcons, COLOR_CONSTYPE_DIFFER, node1, node2, childdiffer) );
635 SCIP_CALL( COLORcreateConsStoreGraph(scip, &conssame, "same", currentcons, COLOR_CONSTYPE_SAME, node1, node2, childsame) );
655 SCIP_CALL( COLORcreateConsStoreGraph(scip, &conssame, "same", currentcons, COLOR_CONSTYPE_SAME, node1, node2, childsame) );
656 SCIP_CALL( COLORcreateConsStoreGraph(scip, &consdiffer, "differ", currentcons, COLOR_CONSTYPE_DIFFER, node1, node2, childdiffer) );
699 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchruledata->samevalue), branchruledata->length) );
700 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchruledata->differvalue), branchruledata->length) );
701 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchruledata->combinedvalue), branchruledata->length) );
702 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(branchruledata->permutation), branchruledata->length) );
745 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY, BRANCHRULE_MAXDEPTH,
773 "determines the branchingmode, 0: fullstrong branching, 1: strong branching, take first possible branching with only one child-node, 2: strong branching with prior sorting of candidates w.r.t. the fractional value of concerned sets */",
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:240
Definition: type_result.h:33
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1008
Definition: cons_storeGraph.h:73
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:160
Definition: struct_scip.h:59
SCIP_RETCODE SCIPincludeBranchruleStrongcoloring(SCIP *scip)
Definition: branch_strongcoloring.c:731
static SCIP_DECL_SORTINDCOMP(consdataCompValues)
Definition: branch_strongcoloring.c:355
static SCIP_DECL_BRANCHCOPY(branchCopyStrongcoloring)
Definition: branch_strongcoloring.c:381
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_CONS * COLORconsGetActiveStoreGraphCons(SCIP *scip)
Definition: cons_storeGraph.c:858
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
Definition: struct_var.h:198
static SCIP_RETCODE computeBranchingPriorities(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch_strongcoloring.c:197
Definition: cons_storeGraph.h:72
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:144
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
SCIP_RETCODE SCIPsolveProbingLPWithPricing(SCIP *scip, SCIP_Bool pretendroot, SCIP_Bool displayinfo, int maxpricerounds, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: scip_probing.c:834
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:107
static int nodes2index(SCIP *scip, int node1, int node2)
Definition: branch_strongcoloring.c:138
static SCIP_Real computeFixingsScore(SCIP_Real samevalue, SCIP_Real differvalue, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch_strongcoloring.c:109
Definition: struct_tree.h:132
Definition: struct_cons.h:37
int COLORconsGetRepresentative(SCIP *scip, int node)
Definition: cons_storeGraph.c:969
void COLORprobGetStableSet(SCIP *scip, int setindex, int **stableset, int *nelements)
Definition: probdata_coloring.c:1023
static void index2nodes(SCIP *scip, int ind, int *node1, int *node2)
Definition: branch_strongcoloring.c:169
variable pricer for the vertex coloring problem
static SCIP_DECL_BRANCHINIT(branchInitStrongcoloring)
Definition: branch_strongcoloring.c:689
Definition: type_retcode.h:33
Definition: struct_branch.h:69
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip_prob.c:3317
static SCIP_DECL_BRANCHFREE(branchFreeStrongcoloring)
Definition: branch_strongcoloring.c:675
static double computeScore(SCIP_Real val1, SCIP_Real val2)
Definition: branch_strongcoloring.c:99
SCIP_Bool SCIPisSumNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:761
SCIP_Bool COLORprobIsNodeInStableSet(SCIP *scip, int setindex, int node)
Definition: probdata_coloring.c:864
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:571
static SCIP_RETCODE executeStrongBranching(SCIP *scip, COLOR_CONSTYPE constype, int node1, int node2, SCIP_BRANCHRULEDATA *branchruledata, SCIP_Real *newlb)
Definition: branch_strongcoloring.c:307
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5440
static SCIP_DECL_BRANCHEXIT(branchExitStrongcoloring)
Definition: branch_strongcoloring.c:709
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHINIT((*branchinit)))
Definition: scip_branch.c:176
static SCIP_DECL_BRANCHEXECLP(branchExeclpStrongcoloring)
Definition: branch_strongcoloring.c:393
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:386
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:445
branching rule performing strong branching for the vertex coloring problem
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:781
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXIT((*branchexit)))
Definition: scip_branch.c:192
Definition: type_result.h:45
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
Definition: cons_storeGraph.c:882
SCIP_Real SCIPgetLocalTransEstimate(SCIP *scip)
Definition: scip_prob.c:3540
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
Definition: objbenders.h:33
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
Definition: branch.c:1859
Definition: type_result.h:39
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:850