heur_zirounding.c File Reference

Detailed Description

zirounding primal heuristic

Author

Gregor Hendel

Definition in file heur_zirounding.c.

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

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_RETCODE	manageHeurdataMemory (SCIP *scip, SCIP_HEURDATA *heurdata, int nlprows)
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

#define HEUR_NAME   "zirounding"

Definition at line 29 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().

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

Definition at line 30 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

#define HEUR_DISPCHAR   'z'

Definition at line 31 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

#define HEUR_PRIORITY   -500

Definition at line 32 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

#define HEUR_FREQ   1

Definition at line 33 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

#define HEUR_FREQOFS   0

Definition at line 34 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

#define HEUR_MAXDEPTH   -1

Definition at line 35 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPNODE

Definition at line 36 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 37 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

#define DEFAULT_MAXROUNDINGLOOPS   2

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

Definition at line 39 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

#define DEFAULT_STOPZIROUND   TRUE

deactivation check is enabled by default

Definition at line 40 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

#define DEFAULT_STOPPERCENTAGE   0.02

the tolerance percentage after which zirounding will not be executed anymore

Definition at line 41 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

#define DEFAULT_MINSTOPNCALLS   1000

number of heuristic calls before deactivation check

Definition at line 42 of file heur_zirounding.c.

Referenced by SCIPincludeHeurZirounding().

Typedef Documentation

typedef enum Direction DIRECTION

Definition at line 73 of file heur_zirounding.c.

Enumeration Type Documentation

enum Direction

Enumerator:

DIRECTION_UP
DIRECTION_DOWN
DIRECTION_NONE
DIRECTION_UP
DIRECTION_DOWN

Definition at line 68 of file heur_zirounding.c.

Function Documentation

static SCIP_RETCODE manageHeurdataMemory ( SCIP *  scip, SCIP_HEURDATA *  heurdata, int  nlprows  )

static

(re)allocates block memory for heuristic arrays if necessary

Parameters

scip	scip data structure
heurdata	heuristic data pointer
nlprows	current number of LP rows

Definition at line 81 of file heur_zirounding.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, and SCIPreallocBlockMemoryArray.

Referenced by SCIP_DECL_HEUREXEC().

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 126 of file heur_zirounding.c.

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

Referenced by SCIP_DECL_HEUREXEC().

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 144 of file heur_zirounding.c.

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

Referenced by SCIP_DECL_HEUREXEC().

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 268 of file heur_zirounding.c.

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

Referenced by SCIP_DECL_HEUREXEC().

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 353 of file heur_zirounding.c.

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

Referenced by SCIP_DECL_HEUREXEC().

static SCIP_DECL_HEURCOPY ( heurCopyZirounding  )

static

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

Definition at line 412 of file heur_zirounding.c.

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

static SCIP_DECL_HEURFREE ( heurFreeZirounding  )

static

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

Definition at line 426 of file heur_zirounding.c.

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

static SCIP_DECL_HEURINIT ( heurInitZirounding  )

static

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

Definition at line 444 of file heur_zirounding.c.

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

static SCIP_DECL_HEUREXIT ( heurExitZirounding  )

static

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

Definition at line 470 of file heur_zirounding.c.

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

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 509 of file heur_zirounding.c.

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

static SCIP_DECL_HEUREXEC ( heurExecZirounding  )

static

execution method of primal heuristic

Definition at line 526 of file heur_zirounding.c.

References BMSclearMemoryArray, BMScopyMemoryArray, calculateBounds(), DIRECTION_DOWN, DIRECTION_UP, FALSE, getZiValue(), HEUR_NAME, manageHeurdataMemory(), MAX, MIN, NULL, 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(), SCIPdebugMessage, SCIPfeasCeil(), SCIPfeasFloor(), SCIPfreeBufferArray, SCIPgetCutoffbound(), SCIPgetLPBranchCands(), SCIPgetLPObjval(), SCIPgetLPRows(), SCIPgetLPSolstat(), SCIPgetNLPRows(), SCIPgetNLPs(), SCIPgetRowActivity(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetName(), SCIPheurGetNCalls(), SCIPheurGetNSolsFound(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisFeasLT(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisGE(), SCIPisInfinity(), SCIPlinkLPSol(), SCIPprintSol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetRhs(), SCIPsetSolVal(), SCIPstatisticMessage, SCIPtrySol(), SCIPvarGetCol(), SCIPvarGetIndex(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbGlobal(), TRUE, and updateSlacks().

SCIP_RETCODE SCIPincludeHeurZirounding

(

SCIP *

scip

)

creates the zirounding primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 929 of file heur_zirounding.c.

References DEFAULT_MAXROUNDINGLOOPS, DEFAULT_MINSTOPNCALLS, DEFAULT_STOPPERCENTAGE, DEFAULT_STOPZIROUND, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocMemory, SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExit(), SCIPsetHeurFree(), SCIPsetHeurInit(), SCIPsetHeurInitsol(), and TRUE.

Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeDefaultPlugins().