50#define HEUR_NAME "zirounding"
51#define HEUR_DESC "LP rounding heuristic as suggested by C. Wallace taking row slacks and bounds into account"
52#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING
53#define HEUR_PRIORITY -500
56#define HEUR_MAXDEPTH -1
57#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE
58#define HEUR_USESSUBSCIP FALSE
60#define DEFAULT_MAXROUNDINGLOOPS 2
61#define DEFAULT_STOPZIROUND TRUE
62#define DEFAULT_STOPPERCENTAGE 0.02
63#define DEFAULT_MINSTOPNCALLS 1000
77 SCIP_Bool stopziround;
78 SCIP_Real stoppercentage;
108 return MIN(upgap, downgap);
116 SCIP_Real currentvalue,
117 SCIP_Real* upperbound,
118 SCIP_Real* lowerbound,
120 SCIP_Real* downslacks,
122 SCIP_Bool* numericalerror
168 for(
i = 0;
i < ncolvals &&
MAX(*lowerbound, *upperbound) >=
MINSHIFT; ++
i )
180 assert(0 <= rowpos && rowpos < nslacks);
188 *numericalerror =
TRUE;
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],
193 *lowerbound, *upperbound);
203 upslack =
MAX(upslacks[rowpos], 0.0);
204 *upperbound =
MIN(*upperbound, upslack/colvals[
i]);
210 downslack =
MAX(downslacks[rowpos], 0.0);
211 *lowerbound =
MIN(*lowerbound, downslack/colvals[
i]);
221 upslack =
MAX(upslacks[rowpos], 0.0);
222 *lowerbound =
MIN(*lowerbound, -upslack/colvals[
i]);
228 downslack =
MAX(downslacks[rowpos], 0.0);
229 *upperbound =
MIN(*upperbound, -downslack/colvals[
i]);
241 SCIP_Real shiftvalue,
243 SCIP_Real* downslacks,
246 SCIP_Real* slackcoeffs,
273 for(
i = 0;
i < nrows; ++
i )
278 assert(-1 <= rowpos && rowpos < nslacks);
288 val = colvals[
i] * shiftvalue;
296 SCIP_Real slackvarshiftval;
297 SCIP_Real slackvarsolval;
303 slackvarshiftval = -val / slackcoeffs[rowpos];
315 upslacks[rowpos] -= val;
317 downslacks[rowpos] += val;
332 SCIP_Real* coeffpointer
352 for( v = nrowvals - 1; v >= 0; --v )
368 *coeffpointer = rowvals[v];
369 *varpointer = colvar;
479 SCIP_Real* downslacks;
481 SCIP_Real* slackvarcoeffs;
482 SCIP_Bool* rowneedsslackvar;
497 SCIP_Bool improvementfound;
498 SCIP_Bool numericalerror;
587 numericalerror =
FALSE;
607 for(
r = 0;
r < ncandrows; ++
r )
617 rowneedsslackvar[rowpos] =
TRUE;
627 for(
i = 0;
i < nslacks; ++
i )
666 if( slackvars[
i] ==
NULL )
673 SCIP_Real ubslackvar;
674 SCIP_Real lbslackvar;
675 SCIP_Real solvalslackvar;
676 SCIP_Real coeffslackvar;
685 coeffslackvar = slackvarcoeffs[
i];
688 ubgap =
MAX(0.0, ubslackvar - solvalslackvar);
689 lbgap =
MAX(0.0, solvalslackvar - lbslackvar);
694 upslacks[
i] += coeffslackvar * lbgap;
698 downslacks[
i] += coeffslackvar * ubgap;
705 upslacks[
i] -= coeffslackvar * ubgap;
709 downslacks[
i] -= coeffslackvar * lbgap;
713 SCIPdebugMsg(
scip,
" Slack variable for row %s at pos %d: %g <= %s = %g <= %g; Coeff %g, upslack = %g, downslack = %g \n",
715 upslacks[
i], downslacks[
i]);
729 improvementfound =
TRUE;
732 while( currentlpcands > 0 && improvementfound && (
heurdata->maxroundingloops == -1 || nroundings < heurdata->maxroundingloops) )
734 improvementfound =
FALSE;
736 SCIPdebugMsg(
scip,
"zirounding enters while loop for %d time with %d candidates left. \n", nroundings, currentlpcands);
739 for(
c = 0;
c < currentlpcands; ++
c )
743 SCIP_Real upperbound;
744 SCIP_Real lowerbound;
755 oldsolval = solarray[
c];
764 calculateBounds(
scip,
var, oldsolval, &upperbound, &lowerbound, upslacks, downslacks, nslacks, &numericalerror);
773 if( nroundings ==
heurdata->maxroundingloops )
780 up = oldsolval + upperbound;
781 down = oldsolval - lowerbound;
792 down =
MAX(down, floorx);
813 shiftval = (direction ==
DIRECTION_UP ? up - oldsolval : down - oldsolval);
817 shiftval =
MIN(shiftval, upperbound);
819 shiftval =
MIN(shiftval, lowerbound);
826 downslacks,
activities, slackvars, slackvarcoeffs, nslacks) );
828 SCIPdebugMsg(
scip,
"zirounding update step : %d var index, oldsolval=%g, shiftval=%g\n",
832 improvementfound =
TRUE;
840 zilpcands[
c] = zilpcands[currentlpcands - 1];
841 solarray[
c] = solarray[currentlpcands - 1];
845 if(
c < currentlpcands )
848 else if( nroundings ==
heurdata->maxroundingloops )
856 if( currentlpcands == 0 )
917 "determines maximum number of rounding loops",
920 "flag to determine if Zirounding is deactivated after a certain percentage of unsuccessful calls",
923 "if percentage of found solutions falls below this parameter, Zirounding will be deactivated",
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)
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)
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)
SCIP_RETCODE SCIPincludeHeurZirounding(SCIP *scip)
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
int SCIPcolGetLPPos(SCIP_COL *col)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
int SCIPcolGetNLPNonz(SCIP_COL *col)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
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)
SCIP_Longint SCIPheurGetNSolsFound(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
const char * SCIPheurGetName(SCIP_HEUR *heur)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
int SCIPgetNLPRows(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Real SCIPgetLPObjval(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
int SCIProwGetNNonz(SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
int SCIProwGetLPPos(SCIP_ROW *row)
const char * SCIProwGetName(SCIP_ROW *row)
SCIP_Real SCIPgetRowActivity(SCIP *scip, SCIP_ROW *row)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
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)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
int SCIPvarGetIndex(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIPcreateSol(scip, &heurdata->sol, heur))
assert(minobj< SCIPgetCutoffbound(scip))
SCIPlinkLPSol(scip, sol))
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)
#define DEFAULT_MAXROUNDINGLOOPS
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)
static void rowFindSlackVar(SCIP *scip, SCIP_ROW *row, SCIP_VAR **varpointer, SCIP_Real *coeffpointer)
#define DEFAULT_STOPPERCENTAGE
#define DEFAULT_STOPZIROUND
SCIPfreeSol(scip, &heurdata->sol))
#define DEFAULT_MINSTOPNCALLS
static SCIP_Real getZiValue(SCIP *scip, SCIP_Real val)
ZI Round primal heuristic.
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
#define BMSclearMemoryArray(ptr, num)
public methods for primal heuristics
public methods for LP management
public methods for message output
#define SCIPstatisticMessage
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
#define SCIP_DECL_HEURINITSOL(x)
#define SCIP_DECL_HEURCOPY(x)
struct SCIP_HeurData SCIP_HEURDATA
#define SCIP_DECL_HEURINIT(x)
#define SCIP_DECL_HEUREXIT(x)
#define SCIP_DECL_HEURFREE(x)
#define SCIP_DECL_HEUREXEC(x)
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS