Detailed Description

LP rounding heuristic that tries to recover from intermediate infeasibilities.

Author: Tobias Achterberg

#include "blockmemshell/memory.h"
#include "scip/heur_rounding.h"
#include "scip/pub_heur.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.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_param.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 "rounding"

#define	HEUR_DESC "LP rounding heuristic with infeasibility recovering"

#define	HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING

#define	HEUR_PRIORITY -1000

#define	HEUR_FREQ 1

#define	HEUR_FREQOFS 0

#define	HEUR_MAXDEPTH -1

#define	HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP

#define	HEUR_USESSUBSCIP FALSE

#define	DEFAULT_SUCCESSFACTOR 100

#define	DEFAULT_ONCEPERNODE FALSE

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

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

static SCIP_RETCODE	selectRounding (SCIP scip, SCIP_SOL sol, SCIP_Real minobj, SCIP_ROW row, int direction, SCIP_VAR roundvar, SCIP_Real oldsolval, SCIP_Real *newsolval)

static SCIP_RETCODE	selectIncreaseRounding (SCIP scip, SCIP_SOL sol, SCIP_Real minobj, SCIP_ROW row, SCIP_VAR roundvar, SCIP_Real oldsolval, SCIP_Real *newsolval)

static SCIP_RETCODE	selectDecreaseRounding (SCIP scip, SCIP_SOL sol, SCIP_Real minobj, SCIP_ROW row, SCIP_VAR roundvar, 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 roundvar, SCIP_Real oldsolval, SCIP_Real newsolval)

static	SCIP_DECL_HEURCOPY (heurCopyRounding)

static	SCIP_DECL_HEURFREE (heurFreeRounding)

static	SCIP_DECL_HEURINIT (heurInitRounding)

static	SCIP_DECL_HEUREXIT (heurExitRounding)

static	SCIP_DECL_HEURINITSOL (heurInitsolRounding)

static	SCIP_DECL_HEUREXITSOL (heurExitsolRounding)

static	SCIP_DECL_HEUREXEC (heurExecRounding)

SCIP_RETCODE	SCIPincludeHeurRounding (SCIP *scip)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "rounding"

Definition at line 50 of file heur_rounding.c.

◆ HEUR_DESC

#define HEUR_DESC "LP rounding heuristic with infeasibility recovering"

Definition at line 51 of file heur_rounding.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING

Definition at line 52 of file heur_rounding.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY -1000

Definition at line 53 of file heur_rounding.c.

◆ HEUR_FREQ

#define HEUR_FREQ 1

Definition at line 54 of file heur_rounding.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 55 of file heur_rounding.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 56 of file heur_rounding.c.

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_DURINGLPLOOP

Definition at line 57 of file heur_rounding.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 58 of file heur_rounding.c.

◆ DEFAULT_SUCCESSFACTOR

#define DEFAULT_SUCCESSFACTOR 100

number of calls per found solution that are considered as standard success, a higher factor causes the heuristic to be called more often

Definition at line 62 of file heur_rounding.c.

◆ DEFAULT_ONCEPERNODE

#define DEFAULT_ONCEPERNODE FALSE

should the heuristic only be called once per node?

Definition at line 63 of file heur_rounding.c.

Function Documentation

◆ updateViolations()

static void updateViolations	(	SCIP *	scip,
		SCIP_ROW *	row,
		SCIP_ROW **	violrows,
		int *	violrowpos,
		int *	nviolrows,
		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
oldactivity	old activity value of LP row
newactivity	new activity value of LP row

Definition at line 83 of file heur_rounding.c.

References NULL, SCIP_Bool, SCIP_Real, SCIPisFeasGT(), SCIPisFeasLT(), 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	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
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 141 of file heur_rounding.c.

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

Referenced by SCIP_DECL_HEUREXEC().

◆ selectRounding()

static SCIP_RETCODE selectRounding	(	SCIP *	scip,
		SCIP_SOL *	sol,
		SCIP_Real	minobj,
		SCIP_ROW *	row,
		int	direction,
		SCIP_VAR **	roundvar,
		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; rounding 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 rounding remaining fractional vars
row	LP row
direction	should the activity be increased (+1) or decreased (-1)?
roundvar	pointer to store the rounding variable, returns NULL if impossible
oldsolval	pointer to store old (fractional) solution value of rounding variable
newsolval	pointer to store new (rounded) solution value of rounding variable

Definition at line 212 of file heur_rounding.c.

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

Referenced by selectDecreaseRounding(), and selectIncreaseRounding().

◆ selectIncreaseRounding()

static SCIP_RETCODE selectIncreaseRounding	(	SCIP *	scip,
		SCIP_SOL *	sol,
		SCIP_Real	minobj,
		SCIP_ROW *	row,
		SCIP_VAR **	roundvar,
		SCIP_Real *	oldsolval,
		SCIP_Real *	newsolval
	)

static

returns a variable, that increases the activity of the row

Parameters

scip	SCIP data structure
sol	primal solution
minobj	minimal objective value possible after rounding remaining fractional vars
row	LP row
roundvar	pointer to store the rounding variable, returns NULL if impossible
oldsolval	old (fractional) solution value of rounding variable
newsolval	new (rounded) solution value of rounding variable

Definition at line 314 of file heur_rounding.c.

References selectRounding().

Referenced by SCIP_DECL_HEUREXEC().

◆ selectDecreaseRounding()

static SCIP_RETCODE selectDecreaseRounding	(	SCIP *	scip,
		SCIP_SOL *	sol,
		SCIP_Real	minobj,
		SCIP_ROW *	row,
		SCIP_VAR **	roundvar,
		SCIP_Real *	oldsolval,
		SCIP_Real *	newsolval
	)

static

returns a variable, that decreases the activity of the row

Parameters

scip	SCIP data structure
sol	primal solution
minobj	minimal objective value possible after rounding remaining fractional vars
row	LP row
roundvar	pointer to store the rounding variable, returns NULL if impossible
oldsolval	old (fractional) solution value of rounding variable
newsolval	new (rounded) solution value of rounding variable

Definition at line 329 of file heur_rounding.c.

References selectRounding().

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 **	roundvar,
		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; rounding 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 rounding remaining fractional vars
lpcands	fractional variables in LP
nlpcands	number of fractional variables in LP
roundvar	pointer to store the rounding variable, returns NULL if impossible
oldsolval	old (fractional) solution value of rounding variable
newsolval	new (rounded) solution value of rounding variable

Definition at line 348 of file heur_rounding.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().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyRounding )

static

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

Definition at line 431 of file heur_rounding.c.

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

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeRounding )

static

destructor of primal heuristic to free user data (called when SCIP is exiting)

Definition at line 445 of file heur_rounding.c.

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

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitRounding )

static

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

Definition at line 464 of file heur_rounding.c.

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

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitRounding )

static

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

Definition at line 482 of file heur_rounding.c.

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

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolRounding )

static

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

Definition at line 498 of file heur_rounding.c.

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

◆ SCIP_DECL_HEUREXITSOL()

static SCIP_DECL_HEUREXITSOL ( heurExitsolRounding )

static

solving process deinitialization method of primal heuristic (called before branch and bound process data is freed)

Definition at line 517 of file heur_rounding.c.

References HEUR_TIMING, SCIP_OKAY, and SCIPheurSetTimingmask().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecRounding )

static

execution method of primal heuristic

Definition at line 528 of file heur_rounding.c.

References FALSE, HEUR_NAME, nnodes, NULL, r, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfeasCeil(), SCIPfeasFloor(), SCIPfreeBufferArray, SCIPgetCutoffbound(), SCIPgetLPBranchCands(), SCIPgetLPObjval(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetNLPs(), SCIPgetNNodes(), SCIPgetRowActivity(), SCIPgetSolOrigObj(), SCIPgetSolTransObj(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurGetNBestSolsFound(), SCIPheurGetNCalls(), SCIPheurGetNSolsFound(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisGE(), SCIPisLE(), SCIPlinkLPSol(), SCIPprintSol(), SCIPretransformObj(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetRhs(), SCIProwIsLocal(), SCIPsetSolVal(), SCIPtrySol(), SCIPvarGetName(), SCIPvarGetObj(), selectDecreaseRounding(), selectEssentialRounding(), selectIncreaseRounding(), TRUE, and updateActivities().

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

◆ DEFAULT_SUCCESSFACTOR

◆ DEFAULT_ONCEPERNODE

Function Documentation

◆ updateViolations()

◆ updateActivities()

◆ selectRounding()

◆ selectIncreaseRounding()

◆ selectDecreaseRounding()

◆ selectEssentialRounding()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXIT()

◆ SCIP_DECL_HEURINITSOL()

◆ SCIP_DECL_HEUREXITSOL()

◆ SCIP_DECL_HEUREXEC()