branch_bpstrong.c
Go to the documentation of this file.
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
59 #define BRANCHRULE_DESC "strong branching for branch-and-price" /**< short description of branching rule */
138 SCIP_Real *strongbranchscore; /**< the candidates' last scores from strong branching with column
140 SCIP_Bool *sbscoreisrecent; /**< was the score saved in strongbranchscore computed in a parent of
147 SCIP_Longint nsblpiterations; /**< total number of strong branching lp iterations during phase 1 */
152 SCIP_BRANCHRULE* initiatorbranchrule; /**< the branching rule that initiated strong branching */
164 SCIP_Longint maxsblpiters; /**< maximum number of strong branching lp iterations, set to 2*avg lp
183 SCIP_Real maxphase0outcandsfrac; /**< maximum number of output candidates from phase 0 as fraction of
190 SCIP_Real maxphase1outcandsfrac; /**< maximum number of output candidates from phase 0 as fraction of
196 SCIP_Real lookaheadscales; /**< how much should the look ahead scale with the overall evaluation
213 SCIP_Real sbpseudocostweight; /**< with how much weight should strong branching scores be considered
295 hashvalue = SCIPhashTwo( MIN( SCIPvarGetIndex(var1), SCIPvarGetIndex(var2) ), MAX( SCIPvarGetIndex(var1), SCIPvarGetIndex(var2) ) );
300 /* calculates the number of needed candidates based on the min and max number of candidates as well as the node gap */
364 if ( !GCGoriginalVarIsLinking(branchcand) && GCGgetNIdenticalBlocks(scip, GCGvarGetBlock(branchcand)) != 1 )
432 /* if variable is not in hashmtable insert it, initialize its array entries, and increase array sizes */
445 SCIP_CALL( SCIPreallocBlockMemoryArray(masterscip, &branchruledata->lastevalnode, branchruledata->maxvars,
461 assert(SCIPhashtableExists(branchruledata->candhashtable, (void*) branchruledata->vartuples[nvars])
476 /* compare two indices corresponding to entries in branchruledata->score, returns TRUE iff the first elements score is
484 return this_branchruledata->score[*(int *)index1] > this_branchruledata->score[*(int *)index2]? -1 : 1;
487 /* compare two indices based on descending numerical order, returns TRUE iff the first index is smaller */
496 /* creates a probing node that is "equal" to the same or differ branch of a given Ryan-Foster candidate, mostly copied
547 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s(%s,%s)", same? "same" : "differ", SCIPvarGetName(branchdata->var1),
590 SCIP_CALL( GCGrelaxNewProbingnodeMasterCons(scip, branchrule, branchdata, origbranchconss, norigvars,
664 SCIP_CALL( newProbingNodeRyanfosterMaster(scip, branchruledata->initiatorbranchrule, branchvar1,
676 SCIP_CALL( GCGrelaxPerformProbingWithPricing(scip, branchruledata->maxsbpricerounds, NULL, &npricerounds,
708 /* Returns true iff the second node is a k-successor of the to the first number corresponding node
736 /* Evaluates the given variable based on a score function of choice. Higher scores are given to better variables. */
760 /* define score functions and calculate score for all variables for sorting dependent on used heuristic */
769 hashindex = ((VarTuple *) SCIPhashtableRetrieve(branchruledata->candhashtable, (void *) &vartuple))->index;
819 hashindex = ((VarTuple *) SCIPhashtableRetrieve(branchruledata->candhashtable, (void *) &vartuple))->index;
833 SCIP_CALL( executeStrongBranching(scip, branchrule, var1, var2, solval1, solval2, candinfo, usecolgen, -1,
894 SCIP_Bool* bestdowninf, /**< pointer to store whether strong branching detected infeasibility in
976 else if( branchruledata->initiator == RYANFOSTER && (branchruledata->usepseudocosts || branchruledata->mostfrac ) )
996 /* set maximum strong branching lp iterations and pricing rounds to 2 times the average unless the value is
999 SCIP_CALL( SCIPgetLongintParam(scip, "branching/bp_strong/maxsblpiters", &branchruledata->maxsblpiters) );
1024 SCIP_CALL( SCIPgetIntParam(scip, "branching/bp_strong/maxsbpricerounds", &branchruledata->maxsbpricerounds) );
1051 nodegap = ((upperbound >= 0) == (nodelowerbound >= 0) && MIN( ABS( upperbound ), ABS( nodelowerbound ) ) != 0)?
1052 MIN( ABS( (upperbound-nodelowerbound) / MIN( ABS( upperbound ), ABS( nodelowerbound ) ) ), 1 ) : 1;
1055 /* number of candidates we evaluate precisely should be based on the likely relevance of this branching decision
1067 hashindex = ((VarTuple *) SCIPhashtableRetrieve(branchruledata->candhashtable, (void *) &vartuple))->index;
1083 * iter = 1: we did not find enough variables to branch on so far, so we look for integer variables that belong
1084 * to no block but were directly transferred to the master problem and which have a fractional value in the
1094 hashindex = ((VarTuple *) SCIPhashtableRetrieve(branchruledata->candhashtable, (void *) &vartuple))->index;
1154 /* the number of candidates we select based on historical strong branching scores needs to depend on the number of
1155 * candidates for which we have historical scores, otherwise some candidates would be selected simply because they
1158 nneededhistcands = (int) SCIPfloor(scip, MIN( (SCIP_Real)nvalidhistcands / (SCIP_Real)(nvalidcands+nvalidhistcands),
1164 * - phase 0: select a first selection of candidates based on some traditional variable selection
1165 * heuristic, some (half) of the candidates are new, and some are selected based on previous calls
1166 * - phase 1: filter the best candidates by evaluating the Master LP, w/o column and cut generation
1167 * - phase 2: select the best of the candidates from phase 1 by solving the Master LP with column and cut generation
1201 /* we only want to skip phase 1, so we need to set nneededcands to the number of output candidates
1262 SCIP_CALL( score_function(scip, branchrule, cand1s[indices[c]], NULL, branchcandssol[indices[c]], 0, 0,
1280 /* variable pointers for orig candidates sometimes change during probing in strong branching */
1288 if( phase == 2 && !branchruledata->usestronglite && branchruledata->immediateinf && (upinf || downinf) )
1358 /* swap out the worst performing "new" candidates with the best performing historical candidates */
1431 if( branchruledata->initiator == RYANFOSTER && (branchruledata->usepseudocosts || branchruledata->mostfrac) )
1541 /* free data if we already solved another instance but branchFreeBPStrong was not called inbetween */
1580 SCIP_CALL( SCIPgetRealParam(origprob, "branching/bp_strong/depthlogphase0frac", &phase0frac) );
1581 SCIP_CALL( SCIPgetRealParam(origprob, "branching/bp_strong/depthlogphase2frac", &phase2frac) );
1586 branchruledata->minphase0depth = (int) SCIPround(origprob, (1-logweight) * branchruledata->minphase0depth
1588 branchruledata->maxphase1depth = (int) SCIPround(origprob, (1-logweight) * branchruledata->maxphase1depth
1590 branchruledata->maxphase2depth = (int) SCIPround(origprob, (1-logweight) * branchruledata->maxphase2depth
1605 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->uniqueblockflags, branchruledata->maxvars) );
1606 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->strongbranchscore, branchruledata->maxvars) );
1607 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->sbscoreisrecent, branchruledata->maxvars) );
1608 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->lastevalnode, branchruledata->maxvars) );
1609 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &branchruledata->vartuples, branchruledata->maxvars) );
1637 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
1653 "should strong branching run as precise as possible (to generate more valuable training data)?",
1657 "should infeasibility detected during strong branching be handled immediately, or only if the candidate is selected?",
1661 "how many times can bounds be changed due to infeasibility during strong branching until an already evaluated variable needs to be reevaluated?",
1665 "minimum number of variables for phase 2 to be executed, otherwise the best candidate from phase 1 will be chosen",
1669 "how many candidates should be chosen based on historical strong branching scores as opposed to current heuristic scores in phase 0 (e.g. 0.5 = 50%)?",
1685 "how much should the lookahead scale with the overall evaluation effort? (0 = not at all, 1 = fully)",
1689 "minimum tree depth from which on phase 0 is performed (intended for heuristics like pseudocost branching)",
1693 "maximum tree depth up to which phase 1 is performed (intended for heuristics like pseudocost branching)",
1697 "maximum tree depth up to which phase 2 is performed (intended for heuristics like pseudocost branching)",
1701 "how much should the logarithm of the number of variables influence the depth for hybrid branching? (0 = not at all, 1 = fully)",
1705 "what should be the base of the logarithm that is used to compute the depth of hybrid branching?",
1709 "if using a logarithm to compute the depth of hybrid branching, what should be the fraction of the depth assigned to phase 1 that is assigned to phase 0?",
1713 "if using a logarithm to compute the depth of hybrid branching, what should be the fraction of the depth assigned to phase 1 that is assigned to phase 2?",
1717 "what percentage of the strong branching score of the candidate that was selected does the heuristic's incumbent need to be considered close (e.g. 0.5 = 50%)?",
1722 &branchruledata->maxconsecheurclose, FALSE, DEFAULT_MAXCONSECHEURCLOSE, -1, INT_MAX, NULL, NULL) );
1737 "should phase 0 be performed even if the number of input candidates is already lower or equal to the number of output candidates?",
1742 "should single-variable-pseudocosts be used as a heuristic for strong branching for Ryan-Foster branching?",
1746 "should single-variable-fractionality be used as a heuristic for strong branching for Ryan-Foster branching?",
1766 SCIP_Bool *stillusestrong /**< pointer to store whether strong branching has reached a permanent
1784 SCIP_CALL( SCIPgetBoolParam(scip, "branching/orig/usepseudocosts", &branchruledata->usepseudocosts) );
1787 SCIP_CALL( SCIPgetIntParam(scip, "branching/orig/minphase0outcands", &branchruledata->minphase0outcands) );
1788 SCIP_CALL( SCIPgetIntParam(scip, "branching/orig/maxphase0outcands", &branchruledata->maxphase0outcands) );
1791 SCIP_CALL( SCIPgetRealParam(scip, "branching/orig/phase1gapweight", &branchruledata->phase1gapweight) );
1793 SCIP_CALL( SCIPgetIntParam(scip, "branching/orig/minphase1outcands", &branchruledata->minphase1outcands) );
1794 SCIP_CALL( SCIPgetIntParam(scip, "branching/orig/maxphase1outcands", &branchruledata->maxphase1outcands) );
1797 SCIP_CALL( SCIPgetRealParam(scip, "branching/orig/phase2gapweight", &branchruledata->phase2gapweight) );
1803 selectCandidate(scip, branchrule, NULL, NULL, NULL, 0, branchvar, NULL, NULL, upinf, downinf, result);
1827 SCIP_Bool *stillusestrong /**< pointer to store whether strong branching has reached a permanent
type definitions for branching rules in GCG projects
static SCIP_Bool isKAncestor(SCIP *scip, int ancestornodenr, SCIP_NODE *successornode, int k)
Definition: branch_bpstrong.c:712
GCG interface methods.
SCIP_RETCODE GCGrelaxNewProbingnodeMasterCons(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_CONS **origbranchconss, int norigbranchconss, int maxorigbranchconss)
Definition: relax_gcg.c:4430
static SCIP_RETCODE newProbingNodeRyanfosterMaster(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *ovar1, SCIP_VAR *ovar2, int blocknr, SCIP_Bool same)
Definition: branch_bpstrong.c:500
SCIP_RETCODE GCGrelaxPerformProbing(SCIP *scip, int maxlpiterations, SCIP_Longint *nlpiterations, SCIP_Real *lpobjvalue, SCIP_Bool *lpsolved, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: relax_gcg.c:4620
SCIP_RETCODE GCGrelaxNewProbingnodeMaster(SCIP *scip)
Definition: relax_gcg.c:4378
static SCIP_RETCODE executeStrongBranching(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *branchvar1, SCIP_VAR *branchvar2, SCIP_Real solval1, SCIP_Real solval2, int candinfo, SCIP_Bool pricing, int maxpricingrounds, SCIP_Real *up, SCIP_Real *down, SCIP_Bool *upvalid, SCIP_Bool *downvalid, SCIP_Bool *upinf, SCIP_Bool *downinf)
Definition: branch_bpstrong.c:598
SCIP_Real maxphase0outcandsfrac
Definition: branch_bpstrong.c:183
struct VarTuple VarTuple
SCIP_VAR * GCGoriginalVarGetPricingVar(SCIP_VAR *var)
Definition: gcgvar.c:216
static int score_compare_function(const void *index1, const void *index2)
Definition: branch_bpstrong.c:479
branching rule for original problem in GCG
GCG variable pricer.
Definition: branch_bpstrong.c:127
SCIP_RETCODE SCIPincludeBranchruleBPStrong(SCIP *scip)
Definition: branch_bpstrong.c:1619
constraint handler for the integrality constraint
constraint handler for storing the branching decisions at each node of the tree
constraint handler for storing the branching decisions at each node of the tree
Definition: branch_bpstrong.c:120
SCIP_Real sbpseudocostweight
Definition: branch_bpstrong.c:213
int GCGgetNIdenticalBlocks(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:4053
SCIP_RETCODE GCGrelaxStartProbing(SCIP *scip, SCIP_HEUR *probingheur)
Definition: relax_gcg.c:4264
SCIP_Real * strongbranchscore
Definition: branch_bpstrong.c:138
SCIP_RETCODE GCGrelaxNewProbingnodeOrig(SCIP *scip)
Definition: relax_gcg.c:4331
static int calculateNCands(SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_Real nodegap, int phase, int ncands)
Definition: branch_bpstrong.c:302
GCG relaxator.
static SCIP_DECL_BRANCHFREE(branchFreeBPStrong)
Definition: branch_bpstrong.c:1475
SCIP_VAR ** GCGpricingVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:1015
static SCIP_RETCODE addBranchcandsToData(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR **var1s, SCIP_VAR **var2s, int ncands)
Definition: branch_bpstrong.c:406
Definition: branch_bpstrong.c:109
SCIP_RETCODE GCGrelaxPerformProbingWithPricing(SCIP *scip, int maxpricerounds, SCIP_Longint *nlpiterations, int *npricerounds, SCIP_Real *lpobjvalue, SCIP_Bool *lpsolved, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition: relax_gcg.c:4639
static SCIP_Real score_function(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real solval1, SCIP_Real solval2, int candinfo, SCIP_Bool useheuristic, SCIP_Bool usehistorical, SCIP_Bool usecolgen, SCIP_Real *score, SCIP_Bool *upinf, SCIP_Bool *downinf)
Definition: branch_bpstrong.c:738
static int assignUniqueBlockFlags(SCIP *scip, SCIP_VAR *branchcand)
Definition: branch_bpstrong.c:347
static SCIP_DECL_BRANCHINIT(branchInitBPStrong)
Definition: branch_bpstrong.c:1513
SCIP_BRANCHRULE * initiatorbranchrule
Definition: branch_bpstrong.c:152
generic branch and price strong branching as described in Pecin, D., Pessoa, A., Poggi,...
SCIP_RETCODE GCGbranchSelectCandidateStrongBranchingRyanfoster(SCIP *scip, SCIP_BRANCHRULE *rfbranchrule, SCIP_VAR **ovar1s, SCIP_VAR **ovar2s, int *nspricingblock, int npairs, SCIP_VAR **ovar1, SCIP_VAR **ovar2, int *pricingblock, SCIP_Bool *sameinf, SCIP_Bool *differinf, SCIP_RESULT *result, SCIP_Bool *stillusestrong)
Definition: branch_bpstrong.c:1812
SCIP_Real maxphase1outcandsfrac
Definition: branch_bpstrong.c:190
static SCIP_RETCODE selectCandidate(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR **cand1s, SCIP_VAR **cand2s, int *candinfos, int ncands, SCIP_VAR **outcand1, SCIP_VAR **outcand2, int *outcandinfo, SCIP_Bool *bestupinf, SCIP_Bool *bestdowninf, SCIP_RESULT *result)
Definition: branch_bpstrong.c:880
static int geq_compare_function(const void *index1, const void *index2)
Definition: branch_bpstrong.c:488
SCIP_RETCODE GCGbranchSelectCandidateStrongBranchingOrig(SCIP *scip, SCIP_BRANCHRULE *origbranchrule, SCIP_VAR **branchvar, SCIP_Bool *upinf, SCIP_Bool *downinf, SCIP_RESULT *result, SCIP_Bool *stillusestrong)
Definition: branch_bpstrong.c:1757
reliable pseudo costs branching rule
SCIP_RETCODE GCGrelaxIncludeBranchrule(SCIP *scip, SCIP_BRANCHRULE *branchrule, GCG_DECL_BRANCHACTIVEMASTER((*branchactivemaster)), GCG_DECL_BRANCHDEACTIVEMASTER((*branchdeactivemaster)), GCG_DECL_BRANCHPROPMASTER((*branchpropmaster)), GCG_DECL_BRANCHMASTERSOLVED((*branchmastersolved)), GCG_DECL_BRANCHDATADELETE((*branchdatadelete)))
Definition: relax_gcg.c:3545
SCIP_RETCODE GCGlinkingVarGetBlocks(SCIP_VAR *var, int nblocks, int *blocks)
Definition: gcgvar.c:450
SCIP_RETCODE GCGconsIntegralorigAddBranchrule(SCIP *scip, SCIP_BRANCHRULE *branchrule)
Definition: cons_integralorig.c:67