62#define BRANCHRULE_NAME "strongcoloring"
63#define BRANCHRULE_DESC "branching rule template"
64#define BRANCHRULE_PRIORITY 15000
65#define BRANCHRULE_MAXDEPTH -1
66#define BRANCHRULE_MAXBOUNDDIST 1.0
69#define DEFAULT_BRANCHINGMODE 2
70#define DEFAULT_FIXINGSSCOREMODE 3
71#define DEFAULT_MAXPRICINGROUNDS -1
72#define DEFAULT_USETCLIQUE TRUE
73#define DEFAULT_LOOKAHEAD 10
82struct SCIP_BranchruleData
89 SCIP_Real* differvalue;
90 SCIP_Real* combinedvalue;
113 return 0.2 *
MAX( val1, val2 ) + 0.8 * MIN( val1, val2 );
120 SCIP_Real differvalue,
124 if ( branchruledata->fixingsscoremode == 1 )
126 return 3*samevalue+differvalue;
128 if ( branchruledata->fixingsscoremode == 2 )
130 return 2*samevalue+differvalue;
132 if ( branchruledata->fixingsscoremode == 3 )
134 return samevalue+10*differvalue;
136 if ( branchruledata->fixingsscoremode == 4 )
138 if ( samevalue == -1 && differvalue == -1 )
140 return samevalue*differvalue;
142 return samevalue*differvalue;
158 assert(node1 >= 0 && node2 >= 0);
170 for (
i = 0;
i < node1;
i++ )
172 ind += ( node2-node1-1);
194 while ( value +
nnodes - 1 - *node1 <= ind )
196 value += (
nnodes - 1 - *node1);
199 *node2 = *node1 + 1 + (ind - value);
237 for (
i = 0;
i < branchruledata->length;
i++ )
241 if ( tcliqueIsEdge(graph, node1, node2) )
243 branchruledata->samevalue[
i] = -1;
244 branchruledata->differvalue[
i] = -1;
247 branchruledata->samevalue[
i] = 0;
248 branchruledata->differvalue[
i] = 0;
259 for ( j = 0; j < setlength; j++ )
268 for ( node2 =
nnodes-1; node2 >= 0; node2-- )
276 if ( node2 == node1 )
286 if ( branchruledata->differvalue[
nodes2index(
scip, node1, node2)] == -1 )
291 if ( k < setlength && node2 ==
set[k] )
368 values = (SCIP_Real*)dataptr;
372 if ( values[ind1] > values[ind2] )
376 if ( values[ind1] < values[ind2] )
429 SCIP_Real bestdiffer;
453 if ( branchruledata->branchingmode == 2 )
457 for (
i = 0;
i < branchruledata->length;
i++ )
459 branchruledata->combinedvalue[
i] =
computeFixingsScore(branchruledata->samevalue[
i], branchruledata->differvalue[
i], branchruledata);
463 SCIPsort(branchruledata->permutation, consdataCompValues, branchruledata->combinedvalue, branchruledata->length);
471 for (
i = 0;
i < branchruledata->lookahead &&
i < branchruledata->length;
i++ )
478 if ( sameLb-currLb > 1000 )
480 sameLb = currLb + 1000;
485 if ( differLb-currLb > 1000 )
487 differLb = currLb + 1000;
490 score =
computeScore( sameLb - currLb, differLb-currLb );
494 if ( score > bestscore )
499 bestdiffer = differLb-currLb;
500 bestsame = sameLb-currLb;
502 if ( bestdiffer > 999 || bestsame > 999 )
511 assert(branchruledata->branchingmode == 0 || branchruledata->branchingmode == 1);
535 if ( wasnode1[node1] ==
TRUE )
541 wasnode1[node1] =
TRUE;
545 for ( j =
i+1; j <
nnodes; j++ )
548 if ( node2 == node1 || tcliqueIsEdge(graph, node1, node2) || node2 <
i )
555 if ( wasnode2[node2] ==
TRUE )
continue;
556 else wasnode2[node2] =
TRUE;
567 if ( sameLb-currLb > 1000 )
569 sameLb = currLb + 1000;
574 if ( differLb-currLb > 1000 )
576 differLb = currLb + 1000;
580 if ( score > bestscore )
585 bestdiffer = differLb-currLb;
586 bestsame = sameLb-currLb;
588 if ( (branchruledata->branchingmode == 1) && (bestdiffer > 999 || bestsame > 999) )
595 if ( (branchruledata->branchingmode == 1) && (bestdiffer > 999 || bestsame > 999) )
616 if ( branchruledata->branchingmode >= 1 && branchruledata->usetclique ==
TRUE )
621 if ( bestdiffer <= 999 )
638 if ( bestsame <= 999 )
769 "branching/strongcoloring/lookahead",
770 "number of candidates to be considered in branchingmode 2",
774 "branching/strongcoloring/usetclique",
775 "should the exact pricing with the tclique-algorithm be used for the strongbranchings?",
779 "branching/strongcoloring/maxpricingrounds",
780 "maximal number of pricing rounds used for each probing node in the strongbranching",
784 "branching/strongcoloring/branchingmode",
785 "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 */",
789 "branching/strongcoloring/fixingsscoremode",
790 "determines the weightings of the two factors for prior sorting by fractional LP value",
#define BRANCHRULE_PRIORITY
static double computeScore(SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE executeStrongBranching(SCIP *scip, COLOR_CONSTYPE constype, int node1, int node2, SCIP_BRANCHRULEDATA *branchruledata, SCIP_Real *newlb)
SCIP_RETCODE SCIPincludeBranchruleStrongcoloring(SCIP *scip)
static int nodes2index(SCIP *scip, int node1, int node2)
static void index2nodes(SCIP *scip, int ind, int *node1, int *node2)
#define DEFAULT_MAXPRICINGROUNDS
#define DEFAULT_USETCLIQUE
#define DEFAULT_BRANCHINGMODE
#define DEFAULT_LOOKAHEAD
static SCIP_Real computeFixingsScore(SCIP_Real samevalue, SCIP_Real differvalue, SCIP_BRANCHRULEDATA *branchruledata)
#define BRANCHRULE_MAXDEPTH
static SCIP_RETCODE computeBranchingPriorities(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
#define DEFAULT_FIXINGSSCOREMODE
#define BRANCHRULE_MAXBOUNDDIST
branching rule performing strong branching for the vertex coloring problem
TCLIQUE_GRAPH * COLORconsGetCurrentGraph(SCIP *scip)
SCIP_RETCODE COLORcreateConsStoreGraph(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONS *fatherconstraint, COLOR_CONSTYPE type, int node1, int node2, SCIP_NODE *stickingnode)
int COLORconsGetRepresentative(SCIP *scip, int node)
SCIP_CONS * COLORconsGetActiveStoreGraphCons(SCIP *scip)
enum COLOR_ConsType COLOR_CONSTYPE
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
SCIP_Real SCIPgetLocalTransEstimate(SCIP *scip)
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)
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)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_RETCODE SCIPsetBranchruleInit(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPsetBranchruleExit(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPincludeBranchruleBasic(SCIP *scip, SCIP_BRANCHRULE **branchruleptr, const char *name, const char *desc, int priority, int maxdepth, SCIP_Real maxbounddist, SCIP_BRANCHRULEDATA *branchruledata)
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
void SCIPbranchruleSetData(SCIP_BRANCHRULE *branchrule, SCIP_BRANCHRULEDATA *branchruledata)
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule,)
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
SCIP_Bool SCIPconsIsEnabled(SCIP_CONS *cons)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
SCIP_RETCODE SCIPsolveProbingLPWithPricing(SCIP *scip, SCIP_Bool pretendroot, SCIP_Bool displayinfo, int maxpricerounds, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_Bool SCIPisSumNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
int SCIPgetDepth(SCIP *scip)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_VARDATA * SCIPvarGetData(SCIP_VAR *var)
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
assert(minobj< SCIPgetCutoffbound(scip))
#define BMSclearMemoryArray(ptr, num)
variable pricer for the vertex coloring problem
void COLORprobGetStableSet(SCIP *scip, int setindex, int **stableset, int *nelements)
int COLORprobGetNNodes(SCIP *scip)
SCIP_CONS * COLORprobGetConstraint(SCIP *scip, int node)
SCIP_Bool COLORprobIsNodeInStableSet(SCIP *scip, int setindex, int node)
struct TCLIQUE_Graph TCLIQUE_GRAPH
#define SCIP_DECL_BRANCHEXECLP(x)
#define SCIP_DECL_BRANCHINIT(x)
#define SCIP_DECL_BRANCHCOPY(x)
#define SCIP_DECL_BRANCHEXIT(x)
#define SCIP_DECL_BRANCHFREE(x)
struct SCIP_BranchruleData SCIP_BRANCHRULEDATA
#define SCIP_DECL_SORTINDCOMP(x)
enum SCIP_Retcode SCIP_RETCODE