LP rounding heuristic that tries to recover from intermediate infeasibilities, shifts integer variables, and solves a final LP to calculate feasible values for continuous variables.
Definition in file heur_intshifting.c.
#include <assert.h>
#include <string.h>
#include "scip/heur_intshifting.h"
#include "scip/pub_misc.h"
Go to the source code of this file.
Macros | |
#define | HEUR_NAME "intshifting" |
#define | HEUR_DESC "LP rounding heuristic with infeasibility recovering and final LP solving" |
#define | HEUR_DISPCHAR 'i' |
#define | HEUR_PRIORITY -10000 |
#define | HEUR_FREQ 10 |
#define | HEUR_FREQOFS 0 |
#define | HEUR_MAXDEPTH -1 |
#define | HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE |
#define | HEUR_USESSUBSCIP FALSE |
#define | MAXSHIFTINGS 50 |
#define | WEIGHTFACTOR 1.1 |
#define | DEFAULT_RANDSEED 17 |
Functions | |
static void | updateViolations (SCIP *scip, SCIP_ROW *row, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int *nviolfracrows, int *nfracsinrow, SCIP_Real oldminactivity, SCIP_Real oldmaxactivity, SCIP_Real newminactivity, SCIP_Real newmaxactivity) |
static SCIP_RETCODE | updateActivities (SCIP *scip, SCIP_Real *minactivities, SCIP_Real *maxactivities, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, int *nviolfracrows, int *nfracsinrow, int nlprows, SCIP_VAR *var, SCIP_Real oldsolval, SCIP_Real newsolval) |
static SCIP_RETCODE | selectShifting (SCIP *scip, SCIP_SOL *sol, SCIP_ROW *row, SCIP_Real rowactivity, int direction, SCIP_Real *nincreases, SCIP_Real *ndecreases, SCIP_Real increaseweight, SCIP_VAR **shiftvar, SCIP_Real *oldsolval, SCIP_Real *newsolval) |
static SCIP_RETCODE | selectEssentialRounding (SCIP *scip, SCIP_SOL *sol, SCIP_Real minobj, SCIP_VAR **lpcands, int nlpcands, SCIP_VAR **shiftvar, SCIP_Real *oldsolval, SCIP_Real *newsolval) |
static void | addFracCounter (int *nfracsinrow, SCIP_ROW **violrows, int *violrowpos, int *nviolfracrows, int nviolrows, int nlprows, SCIP_VAR *var, int incval) |
static | SCIP_DECL_HEURCOPY (heurCopyIntshifting) |
static | SCIP_DECL_HEURINIT (heurInitIntshifting) |
static | SCIP_DECL_HEUREXIT (heurExitIntshifting) |
static | SCIP_DECL_HEURINITSOL (heurInitsolIntshifting) |
static | SCIP_DECL_HEUREXEC (heurExecIntshifting) |
SCIP_RETCODE | SCIPincludeHeurIntshifting (SCIP *scip) |
#define HEUR_NAME "intshifting" |
Definition at line 30 of file heur_intshifting.c.
Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEURINIT(), SCIP_DECL_HEURINITSOL(), and SCIPincludeHeurIntshifting().
#define HEUR_DESC "LP rounding heuristic with infeasibility recovering and final LP solving" |
Definition at line 31 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
#define HEUR_DISPCHAR 'i' |
Definition at line 32 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
#define HEUR_PRIORITY -10000 |
Definition at line 33 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
#define HEUR_FREQ 10 |
Definition at line 34 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
#define HEUR_FREQOFS 0 |
Definition at line 35 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
#define HEUR_MAXDEPTH -1 |
Definition at line 36 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE |
Definition at line 37 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 38 of file heur_intshifting.c.
Referenced by SCIPincludeHeurIntshifting().
#define MAXSHIFTINGS 50 |
maximal number of non improving shiftings
Definition at line 40 of file heur_intshifting.c.
Referenced by SCIP_DECL_HEUREXEC().
#define WEIGHTFACTOR 1.1 |
Definition at line 41 of file heur_intshifting.c.
Referenced by SCIP_DECL_HEUREXEC().
#define DEFAULT_RANDSEED 17 |
Definition at line 42 of file heur_intshifting.c.
Referenced by SCIP_DECL_HEURINIT().
|
static |
update row violation arrays after a row's activity value changed
scip | SCIP data structure |
row | LP row |
violrows | array with currently violated rows |
violrowpos | position of LP rows in violrows array |
nviolrows | pointer to the number of currently violated rows |
nviolfracrows | pointer to the number of violated rows with fractional candidates |
nfracsinrow | array with number of fractional variables for every row |
oldminactivity | old minimal activity value of LP row |
oldmaxactivity | old maximal activity value of LP row |
newminactivity | new minimal activity value of LP row |
newmaxactivity | new maximal activity value of LP row |
Definition at line 59 of file heur_intshifting.c.
References SCIP_Bool, SCIP_Real, SCIPisFeasGT(), SCIPisFeasLT(), SCIProwGetLhs(), SCIProwGetLPPos(), and SCIProwGetRhs().
Referenced by updateActivities().
|
static |
update row activities after a variable's solution value changed
scip | SCIP data structure |
minactivities | LP row minimal activities |
maxactivities | LP row maximal activities |
violrows | array with currently violated rows |
violrowpos | position of LP rows in violrows array |
nviolrows | pointer to the number of currently violated rows |
nviolfracrows | pointer to the number of violated rows with fractional candidates |
nfracsinrow | array with number of fractional variables for every row |
nlprows | number of rows in current LP |
var | variable that has been changed |
oldsolval | old solution value of variable |
newsolval | new solution value of variable |
Definition at line 158 of file heur_intshifting.c.
References SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPinfinity(), SCIPisInfinity(), SCIProwGetLPPos(), SCIProwIsInLP(), SCIProwIsLocal(), SCIPvarGetCol(), SCIPvarGetType(), and updateViolations().
Referenced by SCIP_DECL_HEUREXEC().
|
static |
returns an integer variable, that pushes activity of the row in the given direction with minimal negative impact on other rows; if variables have equal impact, chooses the one with best objective value improvement in corresponding direction; prefer fractional integers over other variables in order to become integral during the process; shifting in a direction is forbidden, if this forces the objective value over the upper bound, or if the variable was already shifted in the opposite direction
scip | SCIP data structure |
sol | primal solution |
row | LP row |
rowactivity | activity of LP row |
direction | should the activity be increased (+1) or decreased (-1)? |
nincreases | array with weighted number of increasings per variables |
ndecreases | array with weighted number of decreasings per variables |
increaseweight | current weight of increase/decrease updates |
shiftvar | pointer to store the shifting variable, returns NULL if impossible |
oldsolval | pointer to store old solution value of shifting variable |
newsolval | pointer to store new (shifted) solution value of shifting variable |
Definition at line 247 of file heur_intshifting.c.
References MAX, REALABS, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPcolGetVar(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetSolVal(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasIntegral(), SCIPisHugeValue(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIProwGetCols(), SCIProwGetLhs(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPvarGetLbGlobal(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetType(), and SCIPvarGetUbGlobal().
Referenced by SCIP_DECL_HEUREXEC().
|
static |
returns a fractional variable, that has most impact on rows in opposite direction, i.e. that is most crucial to fix in the other direction; if variables have equal impact, chooses the one with best objective value improvement in corresponding direction; shifting in a direction is forbidden, if this forces the objective value over the upper bound
scip | SCIP data structure |
sol | primal solution |
minobj | minimal objective value possible after shifting remaining fractional vars |
lpcands | fractional variables in LP |
nlpcands | number of fractional variables in LP |
shiftvar | pointer to store the shifting variable, returns NULL if impossible |
oldsolval | old (fractional) solution value of shifting variable |
newsolval | new (shifted) solution value of shifting variable |
Definition at line 397 of file heur_intshifting.c.
References SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetCutoffbound(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasIntegral(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetObj(), and SCIPvarGetType().
Referenced by SCIP_DECL_HEUREXEC().
|
static |
adds a given value to the fractionality counters of the rows in which the given variable appears
nfracsinrow | array to store number of fractional variables per row |
violrows | array with currently violated rows |
violrowpos | position of LP rows in violrows array |
nviolfracrows | pointer to store the number of violated rows with fractional variables |
nviolrows | the number of currently violated rows (stays unchanged in this method) |
nlprows | number of rows in LP |
var | variable for which the counting should be updated |
incval | value that should be added to the corresponding array entries |
Definition at line 475 of file heur_intshifting.c.
References SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIProwGetLPPos(), SCIProwIsLocal(), and SCIPvarGetCol().
Referenced by SCIP_DECL_HEUREXEC().
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 570 of file heur_intshifting.c.
References HEUR_NAME, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurIntshifting().
|
static |
initialization method of primal heuristic (called after problem was transformed)
Definition at line 585 of file heur_intshifting.c.
References DEFAULT_RANDSEED, HEUR_NAME, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPcreateRandom(), SCIPcreateSol(), SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
|
static |
deinitialization method of primal heuristic (called before transformed problem is freed)
Definition at line 607 of file heur_intshifting.c.
References HEUR_NAME, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeRandom(), SCIPfreeSol(), SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().
|
static |
solving process initialization method of primal heuristic (called when branch and bound process is about to begin)
Definition at line 629 of file heur_intshifting.c.
References HEUR_NAME, SCIP_OKAY, SCIPheurGetData(), and SCIPheurGetName().
|
static |
execution method of primal heuristic
Definition at line 645 of file heur_intshifting.c.
References addFracCounter(), BMSclearMemoryArray, FALSE, HEUR_NAME, MAXSHIFTINGS, nnodes, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPchgVarLbDive(), SCIPchgVarUbDive(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPdebug, SCIPdebugMsg, SCIPendDive(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfreeBufferArray, SCIPgetCutoffbound(), SCIPgetLPBranchCands(), SCIPgetLPObjval(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNIntVars(), SCIPgetNLPIterations(), SCIPgetNLPs(), SCIPgetNNodes(), SCIPgetNVars(), SCIPgetSolOrigObj(), SCIPgetSolTransObj(), SCIPgetSolVal(), SCIPgetVars(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPheurGetNSolsFound(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLT(), SCIPisGE(), SCIPisInfinity(), SCIPisStopped(), SCIPlinkLPSol(), SCIPprintRow(), SCIPprintSol(), SCIPrandomGetInt(), SCIPretransformObj(), SCIProwGetCols(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsLocal(), SCIPsetSolVal(), SCIPsolveDiveLP(), SCIPstartDive(), SCIPtrySol(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPwarningMessage(), selectEssentialRounding(), selectShifting(), TRUE, updateActivities(), and WEIGHTFACTOR.