branch_ryanfoster.c
Go to the documentation of this file.
29 * @brief branching rule for original problem in GCG implementing the Ryan and Foster branching scheme
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
90 SCIP_CONS* pricecons; /**< constraint enforcing the branching restriction in the pricing problem */
130 SCIPdebugMessage("branchActiveMasterRyanfoster: %s(%s, %s)\n", ( branchdata->same ? "same" : "differ" ),
147 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "same(%s,%s)", SCIPvarGetName(branchdata->var1), SCIPvarGetName(branchdata->var2));
156 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "differ(%s,%s)", SCIPvarGetName(branchdata->var1), SCIPvarGetName(branchdata->var2));
189 SCIPdebugMessage("branchDeactiveMasterRyanfoster: %s(%s, %s)\n", ( branchdata->same ? "same" : "differ" ),
219 SCIPdebugMessage("branchPropMasterRyanfoster: %s(%s, %s)\n", ( branchdata->same ? "same" : "differ" ),
245 /* if variable belongs to a different block than the branching restriction, we do not have to look at it */
265 /* if branching enforces that both original vars are either both contained or none of them is contained
266 * and the current master variable has different values for both of them, fix the variable to 0 */
282 SCIPdebugMessage("Finished propagation of branching decision constraint: %s(%s, %s), %d vars fixed.\n",
283 ( branchdata->same ? "same" : "differ" ), SCIPvarGetName(branchdata->var1), SCIPvarGetName(branchdata->var2), propcount);
300 SCIPdebugMessage("branchDataDeleteRyanfoster: %s(%s, %s)\n", ( (*branchdata)->same ? "same" : "differ" ),
320 /** for the two given original variables, create two Ryan&Foster branching nodes, one for same, one for differ */
386 (void) SCIPsnprintf(samename, SCIP_MAXSTRLEN, "same(%s,%s)", SCIPvarGetName(branchsamedata->var1),
404 (void) SCIPsnprintf(differname, SCIP_MAXSTRLEN, "differ(%s,%s)", SCIPvarGetName(branchsamedata->var1),
408 pricingvar1 = GCGoriginalVarGetPricingVar( !differinf? branchdifferdata->var1 : branchsamedata->var1 );
409 pricingvar2 = GCGoriginalVarGetPricingVar( !differinf? branchdifferdata->var2 : branchsamedata->var2 );
457 1.0, -SCIPinfinity(scip), 1.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
467 GCGconsMasterbranchGetActiveCons(masterscip), branchrule, branchsamedata, origbranchconss1, norigvars1,
480 GCGconsMasterbranchGetActiveCons(masterscip), branchrule, branchdifferdata, origbranchconss2, norigvars1,
535 /* do not perform Ryan & Foster branching if we have neither a set partitioning nor a set covering structure */
538 SCIPdebugMessage("Not executing Ryan&Foster branching, master is neither set covering nor set partitioning\n");
544 SCIPdebugMessage("Not executing Ryan&Foster branching, node was branched by generic branchrule\n");
573 /* now search for two (fractional) columns mvar1, mvar2 in the master and 2 original variables ovar1, ovar2
604 if( SCIPisZero(origscip, GCGmasterVarGetOrigvals(mvar1)[o1]) || GCGoriginalVarGetNCoefs(ovar1) == 0 )
786 GCGbranchSelectCandidateStrongBranchingRyanfoster(origscip, branchrule, ovar1s, ovar2s, nspricingblock,
807 SCIP_CALL( createChildNodesRyanfoster(origscip, branchrule, ovar1, ovar2, GCGvarGetBlock(mvar1), sameinf,
857 /* do not perform Ryan & Foster branching if we have neither a set partitioning nor a set covering structure */
860 SCIPdebugMessage("Not executing Ryanfoster branching, master is neither set covering nor set partitioning\n");
866 SCIPdebugMessage("Not executing Ryanfoster branching, node was branched by generic branchrule\n");
921 SCIP_CALL( createChildNodesRyanfoster(origscip, branchrule, ovar1, ovar2, GCGvarGetBlock(ovar1), FALSE, FALSE) );
939 branchDeactiveMasterRyanfoster, branchPropMasterRyanfoster, NULL, branchDataDeleteRyanfoster) );
971 branchExitsolRyanfoster, branchExeclpRyanfoster, branchExecextRyanfoster, branchExecpsRyanfoster,
975 "should strong branching be used to determine the variables on which the branching is performed?",
979 SCIP_CALL( SCIPaddIntParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/minphase0outcands",
983 SCIP_CALL( SCIPaddIntParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/maxphase0outcands",
987 SCIP_CALL( SCIPaddRealParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/maxphase0outcandsfrac",
988 "maximum number of output candidates from phase 0 as fraction of total cands during strong branching",
992 "how much impact should the node gap have on the number of precisely evaluated candidates in phase 1 during strong branching?",
995 SCIP_CALL( SCIPaddIntParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/minphase1outcands",
999 SCIP_CALL( SCIPaddIntParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/maxphase1outcands",
1003 SCIP_CALL( SCIPaddRealParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/maxphase1outcandsfrac",
1004 "maximum number of output candidates from phase 1 as fraction of phase 1 cands during strong branching",
1007 SCIP_CALL( SCIPaddRealParam(GCGmasterGetOrigprob(scip), "branching/ryanfoster/phase2gapweight",
type definitions for branching rules in GCG projects
GCG interface methods.
GCG_BRANCHDATA * GCGconsOrigbranchGetBranchdata(SCIP_CONS *cons)
Definition: cons_origbranch.c:585
SCIP_Bool GCGrelaxIsOrigSolFeasible(SCIP *scip)
Definition: relax_gcg.c:4202
static SCIP_DECL_BRANCHEXECPS(branchExecpsRyanfoster)
Definition: branch_ryanfoster.c:828
static SCIP_RETCODE createChildNodesRyanfoster(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_VAR *ovar1, SCIP_VAR *ovar2, int blocknr, SCIP_Bool sameinf, SCIP_Bool differinf)
Definition: branch_ryanfoster.c:322
SCIP_RETCODE GCGcreateConsMasterbranch(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_NODE *node, SCIP_CONS *parentcons, SCIP_BRANCHRULE *branchrule, GCG_BRANCHDATA *branchdata, SCIP_CONS **origbranchconss, int norigbranchconss, int maxorigbranchconss)
Definition: cons_masterbranch.c:2278
branching rule for original problem in GCG implementing the Ryan and Foster branching scheme
SCIP * GCGgetPricingprob(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:3939
SCIP_VAR * GCGoriginalVarGetPricingVar(SCIP_VAR *var)
Definition: gcgvar.c:216
GCG variable pricer.
#define DEFAULT_MAXPHASE0OUTCANDSFRAC
Definition: branch_ryanfoster.c:73
static SCIP_DECL_BRANCHEXECLP(branchExeclpRyanfoster)
Definition: branch_ryanfoster.c:493
static GCG_DECL_BRANCHDATADELETE(branchDataDeleteRyanfoster)
Definition: branch_ryanfoster.c:295
#define DEFAULT_MAXPHASE1OUTCANDSFRAC
Definition: branch_ryanfoster.c:78
SCIP_BRANCHRULE * GCGconsOrigbranchGetBranchrule(SCIP_CONS *cons)
Definition: cons_origbranch.c:598
constraint handler for storing the branching decisions at each node of the tree
static SCIP_DECL_BRANCHINIT(branchInitRyanfoster)
Definition: branch_ryanfoster.c:930
SCIP_Bool GCGcurrentNodeIsGeneric(SCIP *scip)
Definition: cons_masterbranch.c:2722
static GCG_DECL_BRANCHACTIVEMASTER(branchActiveMasterRyanfoster)
Definition: branch_ryanfoster.c:114
constraint handler for storing the branching decisions at each node of the tree
static SCIP_DECL_BRANCHEXECEXT(branchExecextRyanfoster)
Definition: branch_ryanfoster.c:817
SCIP_SOL * GCGrelaxGetCurrentOrigSol(SCIP *scip)
Definition: relax_gcg.c:4183
void GCGconsOrigbranchGetStack(SCIP *scip, SCIP_CONS ***stack, int *nstackelements)
Definition: cons_origbranch.c:549
GCG relaxator.
SCIP_CONS * GCGconsMasterbranchGetActiveCons(SCIP *scip)
Definition: cons_masterbranch.c:2628
SCIP_VAR ** GCGpricingVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:1015
static GCG_DECL_BRANCHPROPMASTER(branchPropMasterRyanfoster)
Definition: branch_ryanfoster.c:201
Definition: branch_bpstrong.c:109
static SCIP_DECL_BRANCHCOPY(branchCopyRyanfoster)
Definition: branch_ryanfoster.c:102
generic branch and price strong branching as described in Pecin, D., Pessoa, A., Poggi,...
SCIP_Bool GCGisMasterSetPartitioning(SCIP *scip)
Definition: relax_gcg.c:4240
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
static GCG_DECL_BRANCHDEACTIVEMASTER(branchDeactiveMasterRyanfoster)
Definition: branch_ryanfoster.c:172
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 SCIPincludeBranchruleRyanfoster(SCIP *scip)
Definition: branch_ryanfoster.c:958