branch_gomory.c
Go to the documentation of this file.
36 * The Gomory cut branching rule selects a candidate integer variable $j$ with a fractional solution value.
37 * Each candidate variable must be a basic variable in the LP Tableau (if not then it would have to be at its bound
39 * This branching rule calculates the GMI cut for the aggregated row of the LP tableau associated with the
51/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
80#define DEFAULT_EFFICACYWEIGHT 1.0 /**< the weight of efficacy in weighted sum cut scoring rule */
81#define DEFAULT_OBJPARALLELWEIGHT 0.0 /**< the weight of objective parallelism in weighted sum scoring rule */
82#define DEFAULT_INTSUPPORTWEIGHT 0.0 /**< the weight of integer support in weighted sum cut scoring rule */
83#define DEFAULT_PERFORMRELPSCOST FALSE /**< if relpscost branching should be called without actual branching */
96 SCIP_Real objparallelweight; /**< the weight of objective parallelism in weighted sum scoring rule */
97 SCIP_Real intsupportweight; /**< the weight of integer support in weighted sum cut scoring rule */
98 SCIP_Bool performrelpscost; /**< if relpscost branching should be called without actual branching */
118 * to that form. Specifically, non-basic variables at their lower bound are shifted so that the lower
189 * In such a case it is very close to 0, so isZero will catch and we can ignore the coefficient */
246 /* If there is a >= constraint or ranged constraint at the lower bound, we have to flip the row element */
252 /* Take element if nonbasic at upper bound. Only non-positive slack variables can be nonbasic at upper,
258 /* Nonbasic free variable at zero or basic variable. Free variable should not happen here. Just skip if free */
267 * In such a case it is very close to 0, so isZero will catch and we can ignore the coefficient */
295 /* Cut is defined in original variables, so we replace slack variables by their original definition */
418 SCIPdebugMsg(scip, "Execlp method of Gomory branching in node %" SCIP_LONGINT_FORMAT "\n", SCIPnodeGetNumber(SCIPgetCurrentNode(scip)));
423 SCIPdebugMsg(scip, "Could not apply Gomory branching, as the current LP was not solved to optimality.\n");
429 SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, &lpcandsfrac, NULL, &nlpcands, NULL) );
441 /* We do not branch using this rule, but if enabled do take all the bound and conflict inferences made */
442 SCIP_CALL( SCIPexecRelpscostBranching(scip, lpcands, lpcandssol, lpcandsfrac, nlpcands, FALSE, result) );
446 /* Return SCIP_OKAY if relpscost has shown that this node can be cutoff or some variable domains have changed */
506 SCIP_CALL(SCIPgetLPBInvARow(scip, basicvarpos2tableaurow[lppos], binvrow, binvarow, inds, &ninds));
509 success = getGMIFromRow(scip, ncols, nrows, cols, rows, binvrow, binvarow, &lpcandssol[i], cutcoefs,
532 score += branchruledata->intsupportweight * SCIPgetRowNumIntCols(scip, cut) / (SCIP_Real) SCIProwGetNNonz(cut);
551 SCIPdebugMsg(scip, " -> %d candidates, selected candidate %d: variable <%s> (frac=%g, factor=%g, score=%g)\n",
579 SCIP_CALL( SCIPincludeBranchruleBasic(scip, &branchrule, BRANCHRULE_NAME, BRANCHRULE_DESC, BRANCHRULE_PRIORITY,
603 "whether relpscost branching should be called without branching (used for bound inferences and conflicts)",
static SCIP_Bool getGMIFromRow(SCIP *scip, int ncols, int nrows, SCIP_COL **cols, SCIP_ROW **rows, const SCIP_Real *binvrow, const SCIP_Real *binvarow, const SCIP_Real *lpval, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, SCIP_Bool useweakerscuts)
Definition: branch_gomory.c:121
static SCIP_DECL_BRANCHEXECLP(branchExeclpGomory)
Definition: branch_gomory.c:380
Gomory cut branching rule.
reliable pseudo costs branching rule
SCIP_RETCODE SCIPexecRelpscostBranching(SCIP *scip, SCIP_VAR **branchcands, SCIP_Real *branchcandssol, SCIP_Real *branchcandsfrac, int nbranchcands, SCIP_Bool executebranching, SCIP_RESULT *result)
Definition: branch_relpscost.c:2252
SCIP_RETCODE SCIPincludeBranchruleGomory(SCIP *scip)
Definition: branch_gomory.c:568
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:83
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
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:57
SCIP_RETCODE SCIPsetBranchruleExecLp(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHEXECLP((*branchexeclp)))
Definition: scip_branch.c:249
SCIP_RETCODE SCIPsetBranchruleCopy(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHCOPY((*branchcopy)))
Definition: scip_branch.c:153
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
const char * SCIPbranchruleGetName(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1971
SCIP_BRANCHRULEDATA * SCIPbranchruleGetData(SCIP_BRANCHRULE *branchrule)
Definition: branch.c:1849
SCIP_RETCODE SCIPsetBranchruleFree(SCIP *scip, SCIP_BRANCHRULE *branchrule, SCIP_DECL_BRANCHFREE((*branchfree)))
Definition: scip_branch.c:169
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
SCIP_RETCODE SCIPbranchVar(SCIP *scip, SCIP_VAR *var, SCIP_NODE **downchild, SCIP_NODE **eqchild, SCIP_NODE **upchild)
Definition: scip_branch.c:1050
SCIP_Real SCIPgetCutEfficacy(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip_cut.c:94
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
Definition: scip_lp.c:471
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition: scip_lp.c:570
SCIP_RETCODE SCIPgetLPBInvARow(SCIP *scip, int r, SCIP_Real *binvrow, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip_lp.c:785
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
Definition: scip_lp.c:714
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIP_RETCODE SCIPcreateEmptyRowUnspec(SCIP *scip, SCIP_ROW **row, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1482
SCIP_Real SCIPgetRowObjParallelism(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:2190
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:471
Definition: objbenders.h:44
public methods for branching rules
public methods for LP management
public methods for message output
public methods for branch and bound tree
public methods for problem variables
public methods for branching rule plugins and branching
public methods for cuts and aggregation rows
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for the branch-and-bound tree
Definition: struct_branch.h:79
Definition: struct_lp.h:136
Definition: struct_lp.h:202
Definition: struct_var.h:208
Definition: struct_scip.h:70