Detailed Description

LP rounding heuristic that tries to recover from intermediate infeasibilities and shifts continuous variables.

Author: Tobias Achterberg

#include "blockmemshell/memory.h"
#include "scip/heur_shifting.h"
#include "scip/pub_heur.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_heur.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_prob.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include <string.h>

Go to the source code of this file.

Macros
#define	HEUR_NAME "shifting"

#define	HEUR_DESC "LP rounding heuristic with infeasibility recovering also using continuous variables"

#define	HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING

#define	HEUR_PRIORITY -5000

#define	HEUR_FREQ 10

#define	HEUR_FREQOFS 0

#define	HEUR_MAXDEPTH -1

#define	HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP

#define	HEUR_USESSUBSCIP FALSE

#define	MAXSHIFTINGS 50

#define	WEIGHTFACTOR 1.1

#define	DEFAULT_RANDSEED 31

Functions
static void	updateViolations (SCIP scip, SCIP_ROW row, SCIP_ROW *violrows, int violrowpos, int nviolrows, int nviolfracrows, int *nfracsinrow, SCIP_Real oldactivity, SCIP_Real newactivity)

static SCIP_RETCODE	updateActivities (SCIP scip, SCIP_Real activities, 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 (heurCopyShifting)

static	SCIP_DECL_HEURINIT (heurInitShifting)

static	SCIP_DECL_HEUREXIT (heurExitShifting)

static	SCIP_DECL_HEURINITSOL (heurInitsolShifting)

static	SCIP_DECL_HEUREXEC (heurExecShifting)

SCIP_RETCODE	SCIPincludeHeurShifting (SCIP *scip)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "shifting"

Definition at line 43 of file heur_shifting.c.

Referenced by SCIP_DECL_HEURCOPY(), SCIP_DECL_HEUREXEC(), SCIP_DECL_HEUREXIT(), SCIP_DECL_HEURINIT(), SCIP_DECL_HEURINITSOL(), and SCIPincludeHeurShifting().

◆ HEUR_DESC

#define HEUR_DESC "LP rounding heuristic with infeasibility recovering also using continuous variables"

Definition at line 44 of file heur_shifting.c.

Referenced by SCIPincludeHeurShifting().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING

Definition at line 45 of file heur_shifting.c.

Referenced by SCIPincludeHeurShifting().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY -5000

Definition at line 46 of file heur_shifting.c.

Referenced by SCIPincludeHeurShifting().

◆ HEUR_FREQ

#define HEUR_FREQ 10

Definition at line 47 of file heur_shifting.c.

Referenced by SCIPincludeHeurShifting().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 48 of file heur_shifting.c.

Referenced by SCIPincludeHeurShifting().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 49 of file heur_shifting.c.

Referenced by SCIPincludeHeurShifting().

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP

Definition at line 50 of file heur_shifting.c.

Referenced by SCIPincludeHeurShifting().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 51 of file heur_shifting.c.

Referenced by SCIPincludeHeurShifting().

◆ MAXSHIFTINGS

#define MAXSHIFTINGS 50

maximal number of non improving shiftings

Definition at line 53 of file heur_shifting.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ WEIGHTFACTOR

#define WEIGHTFACTOR 1.1

Definition at line 54 of file heur_shifting.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED 31

initial random seed

Definition at line 55 of file heur_shifting.c.

Referenced by SCIP_DECL_HEURINIT().

Function Documentation

◆ updateViolations()

static void updateViolations	(	SCIP *	scip,
		SCIP_ROW *	row,
		SCIP_ROW **	violrows,
		int *	violrowpos,
		int *	nviolrows,
		int *	nviolfracrows,
		int *	nfracsinrow,
		SCIP_Real	oldactivity,
		SCIP_Real	newactivity
	)

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
nviolfracrows	pointer to the number of violated rows with fractional candidates
nfracsinrow	array with number of fractional variables for every row
oldactivity	old activity value of LP row
newactivity	new activity value of LP row

Definition at line 73 of file heur_shifting.c.

References NULL, SCIP_Bool, SCIP_Real, SCIPisFeasGT(), SCIPisFeasLT(), SCIPisInfinity(), SCIProwGetLhs(), SCIProwGetLPPos(), and SCIProwGetRhs().

Referenced by updateActivities().

◆ updateActivities()

static SCIP_RETCODE updateActivities	(	SCIP *	scip,
		SCIP_Real *	activities,
		SCIP_ROW **	violrows,
		int *	violrowpos,
		int *	nviolrows,
		int *	nviolfracrows,
		int *	nfracsinrow,
		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
activities	LP row 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 191 of file heur_shifting.c.

References NULL, r, SCIP_OKAY, SCIP_Real, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPinfinity(), SCIPisInfinity(), SCIProwGetLPPos(), SCIProwIsInLP(), SCIProwIsLocal(), SCIPvarGetCol(), and updateViolations().

Referenced by SCIP_DECL_HEUREXEC().

◆ selectShifting()

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 a 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 266 of file heur_shifting.c.

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

Referenced by SCIP_DECL_HEUREXEC().

◆ selectEssentialRounding()

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 419 of file heur_shifting.c.

References NULL, SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetCutoffbound(), SCIPgetSolVal(), SCIPinfinity(), SCIPisFeasIntegral(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), and SCIPvarGetType().

Referenced by SCIP_DECL_HEUREXEC().

◆ addFracCounter()

static void addFracCounter	(	int *	nfracsinrow,
		SCIP_ROW **	violrows,
		int *	violrowpos,
		int *	nviolfracrows,
		int	nviolrows,
		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
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 497 of file heur_shifting.c.

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

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyShifting )

static

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

Definition at line 586 of file heur_shifting.c.

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

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitShifting )

static

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

Definition at line 601 of file heur_shifting.c.

References DEFAULT_RANDSEED, HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory(), SCIPcreateRandom(), SCIPcreateSol(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurSetData(), and TRUE.

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitShifting )

static

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

Definition at line 624 of file heur_shifting.c.

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

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolShifting )

static

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

Definition at line 646 of file heur_shifting.c.

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

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecShifting )

static

execution method of primal heuristic

Definition at line 662 of file heur_shifting.c.

References addFracCounter(), BMSclearMemoryArray, FALSE, HEUR_NAME, MAXSHIFTINGS, nnodes, NULL, r, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPdebug, SCIPdebugMsg, SCIPfeasCeil(), SCIPfeasFloor(), SCIPfreeBufferArray, SCIPgetCutoffbound(), SCIPgetLPBranchCands(), SCIPgetLPObjval(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetNLPs(), SCIPgetNNodes(), SCIPgetNVars(), SCIPgetRowActivity(), SCIPgetSolOrigObj(), SCIPgetSolTransObj(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPheurGetNSolsFound(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLT(), SCIPisGE(), SCIPlinkLPSol(), SCIPprintRow(), SCIPprintSol(), SCIPrandomGetInt(), SCIPretransformObj(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetRhs(), SCIProwIsLocal(), SCIPsetSolVal(), SCIPtrySol(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), selectEssentialRounding(), selectShifting(), TRUE, updateActivities(), and WEIGHTFACTOR.

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ MAXSHIFTINGS

◆ WEIGHTFACTOR

◆ DEFAULT_RANDSEED

Function Documentation

◆ updateViolations()

◆ updateActivities()

◆ selectShifting()

◆ selectEssentialRounding()

◆ addFracCounter()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXIT()

◆ SCIP_DECL_HEURINITSOL()

◆ SCIP_DECL_HEUREXEC()