Detailed Description

zirounding primal heuristic

Author: Gregor Hendel

#include "blockmemshell/memory.h"
#include "scip/heur_zirounding.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 "zirounding"

#define	HEUR_DESC "LP rounding heuristic as suggested by C. Wallace taking row slacks and bounds into account"

#define	HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING

#define	HEUR_PRIORITY -500

#define	HEUR_FREQ 1

#define	HEUR_FREQOFS 0

#define	HEUR_MAXDEPTH -1

#define	HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE

#define	HEUR_USESSUBSCIP FALSE

#define	DEFAULT_MAXROUNDINGLOOPS 2

#define	DEFAULT_STOPZIROUND TRUE

#define	DEFAULT_STOPPERCENTAGE 0.02

#define	DEFAULT_MINSTOPNCALLS 1000

#define	MINSHIFT 1e-4

Typedefs
typedef enum Direction	DIRECTION

Enumerations
enum	Direction { DIRECTION_UP = 1, DIRECTION_DOWN = -1, DIRECTION_NONE = 0, DIRECTION_UP = 1, DIRECTION_DOWN = -1 }

Functions
static SCIP_Real	getZiValue (SCIP *scip, SCIP_Real val)

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)

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)

static	SCIP_DECL_HEURCOPY (heurCopyZirounding)

static	SCIP_DECL_HEURFREE (heurFreeZirounding)

static	SCIP_DECL_HEURINIT (heurInitZirounding)

static	SCIP_DECL_HEUREXIT (heurExitZirounding)

static	SCIP_DECL_HEURINITSOL (heurInitsolZirounding)

static	SCIP_DECL_HEUREXEC (heurExecZirounding)

SCIP_RETCODE	SCIPincludeHeurZirounding (SCIP *scip)

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME "zirounding"

Definition at line 50 of file heur_zirounding.c.

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

◆ HEUR_DESC

#define HEUR_DESC "LP rounding heuristic as suggested by C. Wallace taking row slacks and bounds into account"

Definition at line 51 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_ROUNDING

Definition at line 52 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY -500

Definition at line 53 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ HEUR_FREQ

#define HEUR_FREQ 1

Definition at line 54 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS 0

Definition at line 55 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH -1

Definition at line 56 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ HEUR_TIMING

#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPNODE

Definition at line 57 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 58 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ DEFAULT_MAXROUNDINGLOOPS

#define DEFAULT_MAXROUNDINGLOOPS 2

delimits the number of main loops, can be set to -1 for no limit

Definition at line 60 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ DEFAULT_STOPZIROUND

#define DEFAULT_STOPZIROUND TRUE

deactivation check is enabled by default

Definition at line 61 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ DEFAULT_STOPPERCENTAGE

#define DEFAULT_STOPPERCENTAGE 0.02

the tolerance percentage after which zirounding will not be executed anymore

Definition at line 62 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ DEFAULT_MINSTOPNCALLS

#define DEFAULT_MINSTOPNCALLS 1000

number of heuristic calls before deactivation check

Definition at line 63 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

◆ MINSHIFT

#define MINSHIFT 1e-4

minimum shift value for every single step

Definition at line 65 of file heur_zirounding.c.

Referenced by calculateBounds(), and SCIP_DECL_HEUREXEC().

Typedef Documentation

◆ DIRECTION

typedef enum Direction DIRECTION

Definition at line 87 of file heur_zirounding.c.

Enumeration Type Documentation

◆ Direction

enum Direction

Enumerator
DIRECTION_UP
DIRECTION_DOWN
DIRECTION_NONE
DIRECTION_UP
DIRECTION_DOWN

Definition at line 82 of file heur_zirounding.c.

Function Documentation

◆ getZiValue()

static SCIP_Real getZiValue	(	SCIP *	scip,
		SCIP_Real	val
	)

static

returns the fractionality of a value x, which is calculated as zivalue(x) = min(x-floor(x), ceil(x)-x)

Parameters

scip	pointer to current SCIP data structure
val	the value for which the fractionality should be computed

Definition at line 95 of file heur_zirounding.c.

References NULL, SCIP_Real, SCIPfeasCeil(), and SCIPfeasFloor().

Referenced by SCIP_DECL_HEUREXEC().

◆ calculateBounds()

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
	)

static

determines shifting bounds for variable

Parameters

scip	pointer to current SCIP data structure
var	the variable for which lb and ub have to be calculated
currentvalue	the current value of var in the working solution
upperbound	pointer to store the calculated upper bound on the variable shift
lowerbound	pointer to store the calculated lower bound on the variable shift
upslacks	array that contains the slacks between row activities and the right hand sides of the rows
downslacks	array that contains lhs slacks
nslacks	current number of slacks
numericalerror	flag to determine whether a numerical error occurred

Definition at line 113 of file heur_zirounding.c.

References MAX, MINSHIFT, NULL, SCIP_Real, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPdebugMsg, SCIPinfinity(), SCIPisFeasLT(), SCIPisInfinity(), SCIProwGetLPPos(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by SCIP_DECL_HEUREXEC().

◆ updateSlacks()

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

when a variable is shifted, the activities and slacks of all rows it appears in have to be updated

Parameters

scip	pointer to current SCIP data structure
sol	working solution
var	pointer to variable to be modified
shiftvalue	the value by which the variable is shifted
upslacks	upslacks of all rows the variable appears in
downslacks	downslacks of all rows the variable appears in
activities	activities of the LP rows
slackvars	the slack variables for equality rows
slackcoeffs	the slack variable coefficients
nslacks	size of the arrays

Definition at line 237 of file heur_zirounding.c.

References NULL, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPgetSolVal(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPisZero(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetRhs(), SCIPsetSolVal(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

Referenced by SCIP_DECL_HEUREXEC().

◆ rowFindSlackVar()

static void rowFindSlackVar	(	SCIP *	scip,
		SCIP_ROW *	row,
		SCIP_VAR **	varpointer,
		SCIP_Real *	coeffpointer
	)

static

finds a continuous slack variable for an equation row, NULL if none exists

Parameters

scip	pointer to current SCIP data structure
row	the row for which a slack variable is searched
varpointer	pointer to store the slack variable
coeffpointer	pointer to store the coefficient of the slack variable

Definition at line 328 of file heur_zirounding.c.

References NULL, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPcolGetLPPos(), SCIPcolGetNLPNonz(), SCIPcolGetVar(), SCIPdebugMsg, SCIPisFeasEQ(), SCIProwGetCols(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetVals(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetType(), and SCIPvarGetUbGlobal().

Referenced by SCIP_DECL_HEUREXEC().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyZirounding )

static

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

Definition at line 387 of file heur_zirounding.c.

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

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeZirounding )

static

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

Definition at line 401 of file heur_zirounding.c.

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

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitZirounding )

static

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

Definition at line 419 of file heur_zirounding.c.

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

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitZirounding )

static

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

Definition at line 436 of file heur_zirounding.c.

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

◆ SCIP_DECL_HEURINITSOL()

static SCIP_DECL_HEURINITSOL ( heurInitsolZirounding )

static

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

Definition at line 453 of file heur_zirounding.c.

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

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecZirounding )

static

execution method of primal heuristic

Definition at line 470 of file heur_zirounding.c.

References BMSclearMemoryArray, BMScopyMemoryArray, calculateBounds(), DIRECTION_DOWN, DIRECTION_UP, FALSE, getZiValue(), HEUR_NAME, MAX, MINSHIFT, NULL, r, rowFindSlackVar(), 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_CONTINUOUS, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPdebugMsg, SCIPfeasCeil(), SCIPfeasFloor(), SCIPfreeBufferArrayNull, SCIPgetCutoffbound(), SCIPgetLPBranchCands(), SCIPgetLPObjval(), SCIPgetLPRows(), SCIPgetLPSolstat(), SCIPgetNLPRows(), SCIPgetNLPs(), SCIPgetRowActivity(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurGetNCalls(), SCIPheurGetNSolsFound(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisFeasLT(), SCIPisGE(), SCIPisInfinity(), SCIPisPositive(), SCIPisZero(), SCIPlinkLPSol(), SCIPprintSol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetRhs(), SCIPsetSolVal(), SCIPstatisticMessage, SCIPtrySol(), SCIPvarGetCol(), SCIPvarGetIndex(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbGlobal(), TRUE, and updateSlacks().

SCIP

Detailed Description

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ HEUR_NAME

◆ HEUR_DESC

◆ HEUR_DISPCHAR

◆ HEUR_PRIORITY

◆ HEUR_FREQ

◆ HEUR_FREQOFS

◆ HEUR_MAXDEPTH

◆ HEUR_TIMING

◆ HEUR_USESSUBSCIP

◆ DEFAULT_MAXROUNDINGLOOPS

◆ DEFAULT_STOPZIROUND

◆ DEFAULT_STOPPERCENTAGE

◆ DEFAULT_MINSTOPNCALLS

◆ MINSHIFT

Typedef Documentation

◆ DIRECTION

Enumeration Type Documentation

◆ Direction

Function Documentation

◆ getZiValue()

◆ calculateBounds()

◆ updateSlacks()

◆ rowFindSlackVar()

◆ SCIP_DECL_HEURCOPY()

◆ SCIP_DECL_HEURFREE()

◆ SCIP_DECL_HEURINIT()

◆ SCIP_DECL_HEUREXIT()

◆ SCIP_DECL_HEURINITSOL()

◆ SCIP_DECL_HEUREXEC()