heur_zirounding.c
Go to the documentation of this file.
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
42 #define HEUR_DESC "LP rounding heuristic as suggested by C. Wallace taking row slacks and bounds into account"
51 #define DEFAULT_MAXROUNDINGLOOPS 2 /**< delimits the number of main loops, can be set to -1 for no limit */
53 #define DEFAULT_STOPPERCENTAGE 0.02 /**< the tolerance percentage after which zirounding will not be executed anymore */
84 /** returns the fractionality of a value x, which is calculated as zivalue(x) = min(x-floor(x), ceil(x)-x) */
108 SCIP_Real* upperbound, /**< pointer to store the calculated upper bound on the variable shift */
109 SCIP_Real* lowerbound, /**< pointer to store the calculated lower bound on the variable shift */
110 SCIP_Real* upslacks, /**< array that contains the slacks between row activities and the right hand sides of the rows */
142 /* initialize the bounds on the shift to be the gap of the current solution value to the bounds of the variable */
153 /* go through every nonzero row coefficient corresponding to var to determine bounds for shifting
156 * if one of these values is significantly < 0.0, this will cause the abort of execution of the heuristic so that
173 /* all bounds and slacks as they are calculated in zirounding always have to be greater equal zero.
174 * It might however be due to numerical issues, e.g. with scaling, that they are not. Better abort in this case.
183 SCIPdebugMsg(scip, "colval: %15.8g, downslack: %15.8g, upslack: %5.2g, lb: %5.2g, ub: %5.2g\n", colvals[i], downslacks[rowpos], upslacks[rowpos],
186 /* if coefficient > 0, rounding up might violate up slack and rounding down might violate down slack
194 upslack = MAX(upslacks[rowpos], 0.0); /* avoid errors due to numerically slightly infeasible rows */
201 downslack = MAX(downslacks[rowpos], 0.0); /* avoid errors due to numerically slightly infeasible rows */
212 upslack = MAX(upslacks[rowpos], 0.0); /* avoid errors due to numerically slightly infeasible rows */
219 downslack = MAX(downslacks[rowpos], 0.0); /* avoid errors due to numerically slightly infeasible rows */
226 /** when a variable is shifted, the activities and slacks of all rows it appears in have to be updated */
296 assert(SCIPisFeasGE(scip, slackvarsolval + slackvarshiftval, SCIPvarGetLbGlobal(slackvars[rowpos])));
297 assert(SCIPisFeasLE(scip, slackvarsolval + slackvarshiftval, SCIPvarGetUbGlobal(slackvars[rowpos])));
342 /* iterate over the row variables. Stop after the first unfixed continuous variable was found. */
357 SCIPdebugMsg(scip, " slack variable for row %s found: %s\n", SCIProwGetName(row), SCIPvarGetName(colvar));
442 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
513 /* Do not call heuristic if deactivation check is enabled and percentage of found solutions in relation
527 SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, &nimplfracs) );
581 /* loop over fractional variables and involved LP rows to find all rows which require a slack variable */
609 SCIPdebugMsg(scip, " Row %s needs slack variable for variable %s\n", SCIProwGetName(candrows[r]), SCIPvarGetName(cand));
614 /* calculate row slacks for every every row that belongs to the current LP and ensure, that the current solution
615 * has no violated constraint -- if any constraint is violated, i.e. a slack is significantly smaller than zero,
616 * this will cause the termination of the heuristic because Zirounding does not provide feasibility recovering
646 SCIPdebugMsg(scip, "lhs:%5.2f <= act:%5.2g <= rhs:%5.2g --> down: %5.2g, up:%5.2g\n", lhs, activities[i], rhs, downslacks[i], upslacks[i]);
659 SCIPdebugMsg(scip, "No slack variable found for equation %s, terminating ZI Round heuristic\n", SCIProwGetName(row));
704 SCIPdebugMsg(scip, " Slack variable for row %s at pos %d: %g <= %s = %g <= %g; Coeff %g, upslack = %g, downslack = %g \n",
705 SCIProwGetName(row), SCIProwGetLPPos(row), lbslackvar, SCIPvarGetName(slackvars[i]), solvalslackvar, ubslackvar, coeffslackvar,
723 while( currentlpcands > 0 && improvementfound && (heurdata->maxroundingloops == -1 || nroundings < heurdata->maxroundingloops) )
727 SCIPdebugMsg(scip, "zirounding enters while loop for %d time with %d candidates left. \n", nroundings, currentlpcands);
729 /* check for every remaining fractional variable if a shifting decreases ZI-value of the variable */
755 calculateBounds(scip, var, oldsolval, &upperbound, &lowerbound, upslacks, downslacks, nslacks, &numericalerror);
774 /* if the variable is integer or implicit binary, do not shift further than the nearest integer */
821 /* since at least one improvement has been found, heuristic will enter main loop for another time because the improvement
822 * might affect many LP rows and their current slacks and thus make further rounding steps possible */
827 * variable is put at the end of remaining candidates array so as not to be considered in future loops
911 "flag to determine if Zirounding is deactivated after a certain percentage of unsuccessful calls",
917 "determines the minimum number of calls before percentage-based deactivation of Zirounding is applied",
static void calculateBounds(SCIP *scip, SCIP_VAR *var, SCIP_Real currentvalue, SCIP_Real *upperbound, SCIP_Real *lowerbound, SCIP_Real *upslacks, SCIP_Real *downslacks, int nslacks, SCIP_Bool *numericalerror)
Definition: heur_zirounding.c:104
Definition: type_result.h:33
Definition: type_result.h:47
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1213
public methods for SCIP parameter handling
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
Definition: struct_scip.h:59
public methods for memory management
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
Definition: struct_var.h:198
Definition: heur_zirounding.c:75
Definition: type_var.h:53
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:799
public methods for problem variables
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:48
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3125
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:874
public methods for numerical tolerances
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:320
Definition: struct_lp.h:126
public methods for querying solving statistics
Definition: struct_sol.h:64
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
Definition: type_result.h:35
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:773
Definition: type_var.h:42
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
Definition: type_retcode.h:33
Definition: struct_heur.h:88
Definition: heur_zirounding.c:76
Definition: type_lp.h:34
public methods for primal heuristic plugins and divesets
SCIP_RETCODE SCIPincludeHeurZirounding(SCIP *scip)
Definition: heur_zirounding.c:882
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:201
Definition: struct_lp.h:192
public methods for LP management
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
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:130
ZI Round primal heuristic.
public methods for the LP relaxation, rows and columns
public methods for branching rule plugins and branching
static SCIP_DECL_HEURINITSOL(heurInitsolZirounding)
Definition: heur_zirounding.c:444
public methods for solutions
static SCIP_RETCODE updateSlacks(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real shiftvalue, SCIP_Real *upslacks, SCIP_Real *downslacks, SCIP_Real *activities, SCIP_VAR **slackvars, SCIP_Real *slackcoeffs, int nslacks)
Definition: heur_zirounding.c:228
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:786
public methods for message output
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:74
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1767
public methods for message handling
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:386
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:217
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
static void rowFindSlackVar(SCIP *scip, SCIP_ROW *row, SCIP_VAR **varpointer, SCIP_Real *coeffpointer)
Definition: heur_zirounding.c:319
public methods for primal heuristics
Definition: objbenders.h:33
memory allocation routines
Definition: type_var.h:58