branch_ryanfoster.c
Go to the documentation of this file.
31 * This file implements the Ryan/Foster branching rule. For more details see \ref BINPACKING_BRANCHING page.
36 * standard variable branching has the disadvantage that the zero branch is more or less useless because
37 * we only forbid one packing out of exponential many. On the other hand, the branch fixing a packing reduces the problem since
42 * In Computer scheduling of public transport: Urban passenger vehicle and crew scheduling, A. Wren editor, North-Holland 1981, 269-280.
54 * To select a pair of items, we have to know for each packing the items which are contained. Since every packing is a
55 * variable and each item is a set covering constraint, we have to know for each variable in which set covering
56 * constraints it appears (this means, has a coefficient of 1.0). Since \SCIP is constraint based, it is in general
57 * not possible to get this information directly. To overcome this issue, we use the functionality to add
59 * variable. This variable data contains the constraints in which this variable appears (see vardata_binpacking.c for more details).
61 * information which items belong to which packing. Therefore, we can use the Ryan/Foster idea to select a pair of
66 * After having selected a pair of items to branch on, the question now is how to realize such a branching with \SCIP.
68 * constraint based, it is really easy to do that. We implement a constraint handler which handles the
70 * decisions. Furthermore, it also ensures that all packing which are not feasible at a particular node are
71 * locally fixed to zero. For more details, we refer to the \ref cons_samediff.c "source code of the constraint handler".
75 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
137 SCIPdebugMsg(scip, "start branching at node %"SCIP_LONGINT_FORMAT", depth %d\n", SCIPgetNNodes(scip), SCIPgetDepth(scip));
166 /* get variable data which contains the information to which constraints/items the variable belongs */
207 /* there is no variable with (fractional) LP value > 0 that contains exactly one of the items */
239 SCIP_CALL( SCIPcreateConsSamediff(scip, &consdiffer, "differ", id1, id2, DIFFER, childdiffer, TRUE) );
273 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY, BRANCHRULE_MAXDEPTH,
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:395
Definition: type_result.h:42
Ryan/Foster branching rule.
Definition: struct_scip.h:68
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
SCIP_Real SCIPgetLocalTransEstimate(SCIP *scip)
Definition: scip_prob.c:3554
Definition: struct_var.h:207
SCIP_RETCODE SCIPincludeBranchruleRyanFoster(SCIP *scip)
Definition: branch_ryanfoster.c:262
Constraint handler stores the local branching decision data.
SCIP_RETCODE SCIPcreateConsSamediff(SCIP *scip, SCIP_CONS **cons, const char *name, int itemid1, int itemid2, CONSTYPE type, SCIP_NODE *node, SCIP_Bool local)
Definition: cons_samediff.c:560
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:834
Variable data containing the ids of constraints in which the variable appears.
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:116
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:447
int * SCIPvardataGetConsids(SCIP_VARDATA *vardata)
Definition: vardata_binpacking.c:133
Definition: struct_tree.h:141
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
Definition: struct_cons.h:46
Definition: type_retcode.h:42
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1017
Definition: struct_branch.h:78
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip_prob.c:3331
int * SCIPprobdataGetIds(SCIP_PROBDATA *probdata)
Definition: probdata_binpacking.c:439
Definition: cons_samediff.h:46
Problem data for binpacking problem.
int SCIPprobdataGetNItems(SCIP_PROBDATA *probdata)
Definition: probdata_binpacking.c:455
Definition: cons_samediff.h:47
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1119
int SCIPvardataGetNConsids(SCIP_VARDATA *vardata)
Definition: vardata_binpacking.c:125
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
Definition: type_result.h:54
static SCIP_DECL_BRANCHEXECLP(branchExeclpRyanFoster)
Definition: branch_ryanfoster.c:105
Definition: objbenders.h:43