heur_zirounding.c
Go to the documentation of this file.
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
51#define HEUR_DESC "LP rounding heuristic as suggested by C. Wallace taking row slacks and bounds into account"
60#define DEFAULT_MAXROUNDINGLOOPS 2 /**< delimits the number of main loops, can be set to -1 for no limit */
62#define DEFAULT_STOPPERCENTAGE 0.02 /**< the tolerance percentage after which zirounding will not be executed anymore */
86};
93/** returns the fractionality of a value x, which is calculated as zivalue(x) = min(x-floor(x), ceil(x)-x) */
117 SCIP_Real* upperbound, /**< pointer to store the calculated upper bound on the variable shift */
118 SCIP_Real* lowerbound, /**< pointer to store the calculated lower bound on the variable shift */
119 SCIP_Real* upslacks, /**< array that contains the slacks between row activities and the right hand sides of the rows */
151 /* initialize the bounds on the shift to be the gap of the current solution value to the bounds of the variable */
162 /* go through every nonzero row coefficient corresponding to var to determine bounds for shifting
165 * if one of these values is significantly < 0.0, this will cause the abort of execution of the heuristic so that
182 /* all bounds and slacks as they are calculated in zirounding always have to be greater equal zero.
183 * It might however be due to numerical issues, e.g. with scaling, that they are not. Better abort in this case.
192 SCIPdebugMsg(scip, "colval: %15.8g, downslack: %15.8g, upslack: %5.2g, lb: %5.2g, ub: %5.2g\n", colvals[i], downslacks[rowpos], upslacks[rowpos],
195 /* if coefficient > 0, rounding up might violate up slack and rounding down might violate down slack
203 upslack = MAX(upslacks[rowpos], 0.0); /* avoid errors due to numerically slightly infeasible rows */
210 downslack = MAX(downslacks[rowpos], 0.0); /* avoid errors due to numerically slightly infeasible rows */
221 upslack = MAX(upslacks[rowpos], 0.0); /* avoid errors due to numerically slightly infeasible rows */
228 downslack = MAX(downslacks[rowpos], 0.0); /* avoid errors due to numerically slightly infeasible rows */
235/** when a variable is shifted, the activities and slacks of all rows it appears in have to be updated */
305 assert(SCIPisFeasGE(scip, slackvarsolval + slackvarshiftval, SCIPvarGetLbGlobal(slackvars[rowpos])));
306 assert(SCIPisFeasLE(scip, slackvarsolval + slackvarshiftval, SCIPvarGetUbGlobal(slackvars[rowpos])));
351 /* iterate over the row variables. Stop after the first unfixed continuous variable was found. */
366 SCIPdebugMsg(scip, " slack variable for row %s found: %s\n", SCIProwGetName(row), SCIPvarGetName(colvar));
451/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
522 /* Do not call heuristic if deactivation check is enabled and percentage of found solutions in relation
536 SCIP_CALL( SCIPgetLPBranchCands(scip, &lpcands, &lpcandssol, NULL, &nlpcands, NULL, &nimplfracs) );
590 /* loop over fractional variables and involved LP rows to find all rows which require a slack variable */
618 SCIPdebugMsg(scip, " Row %s needs slack variable for variable %s\n", SCIProwGetName(candrows[r]), SCIPvarGetName(cand));
623 /* calculate row slacks for every every row that belongs to the current LP and ensure, that the current solution
624 * has no violated constraint -- if any constraint is violated, i.e. a slack is significantly smaller than zero,
625 * this will cause the termination of the heuristic because Zirounding does not provide feasibility recovering
655 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]);
668 SCIPdebugMsg(scip, "No slack variable found for equation %s, terminating ZI Round heuristic\n", SCIProwGetName(row));
713 SCIPdebugMsg(scip, " Slack variable for row %s at pos %d: %g <= %s = %g <= %g; Coeff %g, upslack = %g, downslack = %g \n",
714 SCIProwGetName(row), SCIProwGetLPPos(row), lbslackvar, SCIPvarGetName(slackvars[i]), solvalslackvar, ubslackvar, coeffslackvar,
732 while( currentlpcands > 0 && improvementfound && (heurdata->maxroundingloops == -1 || nroundings < heurdata->maxroundingloops) )
736 SCIPdebugMsg(scip, "zirounding enters while loop for %d time with %d candidates left. \n", nroundings, currentlpcands);
738 /* check for every remaining fractional variable if a shifting decreases ZI-value of the variable */
764 calculateBounds(scip, var, oldsolval, &upperbound, &lowerbound, upslacks, downslacks, nslacks, &numericalerror);
783 /* if the variable is integer or implicit binary, do not shift further than the nearest integer */
830 /* since at least one improvement has been found, heuristic will enter main loop for another time because the improvement
831 * might affect many LP rows and their current slacks and thus make further rounding steps possible */
836 * variable is put at the end of remaining candidates array so as not to be considered in future loops
920 "flag to determine if Zirounding is deactivated after a certain percentage of unsuccessful calls",
926 "determines the minimum number of calls before percentage-based deactivation of Zirounding is applied",
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 SCIPincludeHeurZirounding(SCIP *scip)
Definition: heur_zirounding.c:891
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 SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
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:117
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:226
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition: scip_sol.c:1631
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:2954
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:832
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:780
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:793
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:806
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:881
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:113
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:237
static void rowFindSlackVar(SCIP *scip, SCIP_ROW *row, SCIP_VAR **varpointer, SCIP_Real *coeffpointer)
Definition: heur_zirounding.c:328
static SCIP_DECL_HEURINITSOL(heurInitsolZirounding)
Definition: heur_zirounding.c:453
ZI Round primal heuristic.
memory allocation routines
Definition: objbenders.h:44
public methods for primal heuristics
public methods for LP management
public methods for message output
public methods for problem variables
public methods for branching rule plugins and branching
public methods for primal heuristic plugins and divesets
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 solutions
public methods for querying solving statistics
Definition: struct_lp.h:136
Definition: struct_heur.h:98
Definition: struct_lp.h:202
Definition: struct_sol.h:74
Definition: struct_var.h:208
Definition: struct_scip.h:70