heur_intshifting.c File Reference

Detailed Description

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.

Author

Tobias Achterberg

Definition in file heur_intshifting.c.

#include <assert.h>
#include <string.h>
#include "scip/heur_intshifting.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

Functions
static void	updateViolations (SCIP *scip, SCIP_ROW *row, SCIP_ROW **violrows, int *violrowpos, int *nviolrows, 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 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, 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)

Macro Definition Documentation

#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().

Function Documentation

static void updateViolations ( SCIP *  scip, SCIP_ROW *  row, SCIP_ROW **  violrows, int *  violrowpos, int *  nviolrows, SCIP_Real  oldminactivity, SCIP_Real  oldmaxactivity, SCIP_Real  newminactivity, SCIP_Real  newmaxactivity  )

static

update row violation arrays after a row's activity value changed

Parameters

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
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 NULL, SCIP_Bool, SCIP_Real, SCIPisFeasGT(), SCIPisFeasLT(), SCIProwGetLhs(), SCIProwGetLPPos(), and SCIProwGetRhs().

Referenced by updateActivities().

static SCIP_RETCODE updateActivities ( SCIP *  scip, SCIP_Real *  minactivities, SCIP_Real *  maxactivities, SCIP_ROW **  violrows, int *  violrowpos, int *  nviolrows, int  nlprows, SCIP_VAR *  var, SCIP_Real  oldsolval, SCIP_Real  newsolval  )

static

update row activities after a variable's solution value changed

Parameters

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
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 119 of file heur_intshifting.c.

References NULL, 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 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

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

Parameters

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 206 of file heur_intshifting.c.

References MAX, MIN, NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPcolGetVar(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetSolVal(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasIntegral(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIProwGetCols(), SCIProwGetLhs(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPvarGetLbGlobal(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetType(), and SCIPvarGetUbGlobal().

Referenced by SCIP_DECL_HEUREXEC().

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

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

Parameters

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 355 of file heur_intshifting.c.

References NULL, 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 void addFracCounter ( int *  nfracsinrow, int  nlprows, SCIP_VAR *  var, int  incval  )

static

adds a given value to the fractionality counters of the rows in which the given variable appears

Parameters

nfracsinrow	array to store number of fractional variables per row
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 433 of file heur_intshifting.c.

References SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIProwGetLPPos(), and SCIPvarGetCol().

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_DECL_HEURCOPY ( heurCopyIntshifting  )

static

copy method for primal heuristic plugins (called when SCIP copies plugins)

Definition at line 466 of file heur_intshifting.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurIntshifting().

static SCIP_DECL_HEURINIT ( heurInitIntshifting  )

static

initialization method of primal heuristic (called after problem was transformed)

Definition at line 481 of file heur_intshifting.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPcreateSol(), SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().

static SCIP_DECL_HEUREXIT ( heurExitIntshifting  )

static

deinitialization method of primal heuristic (called before transformed problem is freed)

Definition at line 500 of file heur_intshifting.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeMemory, SCIPfreeSol(), SCIPheurGetData(), SCIPheurGetName(), and SCIPheurSetData().

static SCIP_DECL_HEURINITSOL ( heurInitsolIntshifting  )

static

solving process initialization method of primal heuristic (called when branch and bound process is about to begin)

Definition at line 518 of file heur_intshifting.c.

References HEUR_NAME, NULL, SCIP_OKAY, SCIPheurGetData(), and SCIPheurGetName().

static SCIP_DECL_HEUREXEC ( heurExecIntshifting  )

static

execution method of primal heuristic

Definition at line 534 of file heur_intshifting.c.

References addFracCounter(), BMSclearMemoryArray, FALSE, HEUR_NAME, MAXSHIFTINGS, NULL, 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, SCIPdebugMessage, SCIPendDive(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfreeBufferArray, SCIPgetCutoffbound(), SCIPgetLPBranchCands(), SCIPgetLPObjval(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNIntVars(), SCIPgetNLPIterations(), SCIPgetNLPs(), SCIPgetNNodes(), SCIPgetNVars(), SCIPgetRandomInt(), SCIPgetSolOrigObj(), SCIPgetSolTransObj(), SCIPgetSolVal(), SCIPgetVars(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPheurGetNSolsFound(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLT(), SCIPisGE(), SCIPisInfinity(), SCIPisStopped(), SCIPlinkLPSol(), SCIPprintRow(), SCIPprintSol(), 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.

SCIP_RETCODE SCIPincludeHeurIntshifting

(

SCIP *

scip

)

creates the intshifting heuristic with infeasibility recovering and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1007 of file heur_intshifting.c.

References HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExit(), SCIPsetHeurInit(), and SCIPsetHeurInitsol().

Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeDefaultPlugins().