heur_shiftandpropagate.c File Reference

Detailed Description

shiftandpropagate primal heuristic

Author

Timo Berthold

Gregor Hendel

Definition in file heur_shiftandpropagate.c.

#include <assert.h>
#include <string.h>
#include "scip/pub_misc.h"
#include "scip/heur_shiftandpropagate.h"

Go to the source code of this file.

Macros
#define	HEUR_NAME   "shiftandpropagate"
#define	HEUR_DESC   "Pre-root heuristic to expand an auxiliary branch-and-bound tree and apply propagation techniques"
#define	HEUR_DISPCHAR   'T'
#define	HEUR_PRIORITY   1000
#define	HEUR_FREQ   0
#define	HEUR_FREQOFS   0
#define	HEUR_MAXDEPTH   -1
#define	HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE
#define	HEUR_USESSUBSCIP   FALSE
#define	DEFAULT_WEIGHT_INEQUALITY   1
#define	DEFAULT_WEIGHT_EQUALITY   3
#define	DEFAULT_RELAX   TRUE
#define	DEFAULT_PROBING   TRUE
#define	DEFAULT_ONLYWITHOUTSOL   TRUE
#define	DEFAULT_NPROPROUNDS   10
#define	DEFAULT_PROPBREAKER   65000
#define	DEFAULT_CUTOFFBREAKER   15
#define	DEFAULT_RANDSEED   3141598
#define	DEFAULT_SORTKEY   'v'
#define	DEFAULT_SORTVARS   TRUE
#define	DEFAULT_COLLECTSTATS   TRUE
#define	DEFAULT_STOPAFTERFEASIBLE   TRUE
#define	DEFAULT_PREFERBINARIES   TRUE
#define	DEFAULT_SELECTBEST   FALSE
#define	DEFAULT_MAXCUTOFFQUOT   0.0
#define	SORTKEYS   "nrtuv"
#define	DEFAULT_NOZEROFIXING   FALSE
#define	DEFAULT_FIXBINLOCKS   TRUE
#define	DEFAULT_BINLOCKSFIRST   FALSE
#define	DEFAULT_NORMALIZE   TRUE
#define	DEFAULT_UPDATEWEIGHTS   FALSE
#define	DEFAULT_IMPLISCONTINUOUS   TRUE
#define	EVENTHDLR_NAME   "eventhdlrshiftandpropagate"
#define	EVENTHDLR_DESC   "event handler to catch bound changes"
#define	EVENTTYPE_SHIFTANDPROPAGATE   (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED)

Typedefs
typedef enum TransformStatus	TRANSFORMSTATUS
typedef struct ConstraintMatrix	CONSTRAINTMATRIX

Enumerations
enum	TransformStatus {   TRANSFORMSTATUS_NONE = 0,   TRANSFORMSTATUS_LB = 1,   TRANSFORMSTATUS_NEG = 2,   TRANSFORMSTATUS_FREE = 3 }

Functions
static SCIP_Bool	varIsDiscrete (SCIP_VAR *var, SCIP_Bool impliscontinuous)
static SCIP_Bool	colIsDiscrete (SCIP_COL *col, SCIP_Bool impliscontinuous)
static void	getRowData (CONSTRAINTMATRIX *matrix, int rowindex, SCIP_Real **valpointer, SCIP_Real *lhs, SCIP_Real *rhs, int **indexpointer, int *nrowvals)
static void	getColumnData (CONSTRAINTMATRIX *matrix, int colindex, SCIP_Real **valpointer, int **indexpointer, int *ncolvals)
static void	relaxVar (SCIP *scip, SCIP_VAR *var, CONSTRAINTMATRIX *matrix, SCIP_Bool normalize)
static void	transformVariable (SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int colpos)
static SCIP_RETCODE	initMatrix (SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int *colposs, SCIP_Bool normalize, int *nmaxrows, SCIP_Bool relax, SCIP_Bool *initialized, SCIP_Bool *infeasible)
static void	freeMatrix (SCIP *scip, CONSTRAINTMATRIX **matrix)
static void	checkRowViolation (SCIP *scip, CONSTRAINTMATRIX *matrix, int rowindex, int *violatedrows, int *violatedrowpos, int *nviolatedrows, int *rowweights, SCIP_Bool updateweights)
static void	checkViolations (SCIP *scip, CONSTRAINTMATRIX *matrix, int colidx, int *violatedrows, int *violatedrowpos, int *nviolatedrows, int *rowweights, SCIP_Bool updateweights)
static SCIP_Real	retransformVariable (SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_VAR *var, int varindex, SCIP_Real solvalue)
static SCIP_RETCODE	getOptimalShiftingValue (SCIP *scip, CONSTRAINTMATRIX *matrix, int varindex, int direction, int *rowweights, SCIP_Real *steps, int *violationchange, SCIP_Real *beststep, int *rowviolations)
static SCIP_RETCODE	updateTransformation (SCIP *scip, CONSTRAINTMATRIX *matrix, SCIP_HEURDATA *heurdata, int varindex, SCIP_Real lb, SCIP_Real ub, int *violatedrows, int *violatedrowpos, int *nviolatedrows)
static	SCIP_DECL_SORTPTRCOMP (heurSortColsShiftandpropagate)
static	SCIP_DECL_HEUREXIT (heurExitShiftandpropagate)
static	SCIP_DECL_HEURINIT (heurInitShiftandpropagate)
static	SCIP_DECL_HEURFREE (heurFreeShiftandpropagate)
static	SCIP_DECL_HEURCOPY (heurCopyShiftandpropagate)
static	SCIP_DECL_HEUREXEC (heurExecShiftandpropagate)
static	SCIP_DECL_EVENTEXEC (eventExecShiftandpropagate)
SCIP_RETCODE	SCIPincludeHeurShiftandpropagate (SCIP *scip)

Macro Definition Documentation

#define HEUR_NAME   "shiftandpropagate"

Definition at line 29 of file heur_shiftandpropagate.c.

Referenced by SCIP_DECL_HEURCOPY(), and SCIPincludeHeurShiftandpropagate().

#define HEUR_DESC   "Pre-root heuristic to expand an auxiliary branch-and-bound tree and apply propagation techniques"

Definition at line 30 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define HEUR_DISPCHAR   'T'

Definition at line 31 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define HEUR_PRIORITY   1000

Definition at line 32 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define HEUR_FREQ   0

Definition at line 33 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define HEUR_FREQOFS   0

Definition at line 34 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define HEUR_MAXDEPTH   -1

Definition at line 35 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE

Definition at line 36 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 37 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_WEIGHT_INEQUALITY   1

the heuristic row weight for inequalities

Definition at line 39 of file heur_shiftandpropagate.c.

Referenced by SCIP_DECL_HEUREXEC().

#define DEFAULT_WEIGHT_EQUALITY   3

the heuristic row weight for equations

Definition at line 40 of file heur_shiftandpropagate.c.

Referenced by SCIP_DECL_HEUREXEC().

#define DEFAULT_RELAX   TRUE

Should continuous variables be relaxed from the problem?

Definition at line 41 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_PROBING   TRUE

Is propagation of solution values enabled?

Definition at line 42 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_ONLYWITHOUTSOL   TRUE

Should heuristic only be executed if no primal solution was found, yet?

Definition at line 43 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_NPROPROUNDS   10

The default number of propagation rounds for each propagation used

Definition at line 44 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_PROPBREAKER   65000

fixed maximum number of propagations

Definition at line 45 of file heur_shiftandpropagate.c.

Referenced by SCIP_DECL_HEUREXEC().

#define DEFAULT_CUTOFFBREAKER   15

fixed maximum number of allowed cutoffs before the heuristic stops

Definition at line 46 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_RANDSEED   3141598

the default random seed for random number generation

Definition at line 47 of file heur_shiftandpropagate.c.

Referenced by SCIP_DECL_HEURINIT().

#define DEFAULT_SORTKEY   'v'

the default key for variable sorting

Definition at line 48 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_SORTVARS   TRUE

should variables be processed in sorted order?

Definition at line 49 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_COLLECTSTATS   TRUE

should variable statistics be collected during probing?

Definition at line 50 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_STOPAFTERFEASIBLE   TRUE

Should the heuristic stop calculating optimal shift values when no more rows are violated?

Definition at line 51 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_PREFERBINARIES   TRUE

Should binary variables be shifted first?

Definition at line 52 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_SELECTBEST   FALSE

should the heuristic choose the best candidate in every round? (set to FALSE for static order)?

Definition at line 53 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_MAXCUTOFFQUOT   0.0

maximum percentage of allowed cutoffs before stopping the heuristic

Definition at line 54 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define SORTKEYS   "nrtuv"

options sorting key: (n)orms down, norms (u)p, (v)iolated rows decreasing, viola(t)ed rows increasing, or (r)andom

Definition at line 55 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_NOZEROFIXING   FALSE

should variables with a zero shifting value be delayed instead of being fixed?

Definition at line 58 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_FIXBINLOCKS   TRUE

should binary variables with no locks in one direction be fixed to that direction?

Definition at line 59 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_BINLOCKSFIRST   FALSE

should binary variables with no locks be preferred in the ordering?

Definition at line 60 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_NORMALIZE   TRUE

should coefficients and left/right hand sides be normalized by max row coeff?

Definition at line 61 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_UPDATEWEIGHTS   FALSE

should row weight be increased every time the row is violated?

Definition at line 62 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define DEFAULT_IMPLISCONTINUOUS   TRUE

should implicit integer variables be treated as continuous variables?

Definition at line 63 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define EVENTHDLR_NAME   "eventhdlrshiftandpropagate"

Definition at line 65 of file heur_shiftandpropagate.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIPincludeHeurShiftandpropagate().

#define EVENTHDLR_DESC   "event handler to catch bound changes"

Definition at line 66 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

#define EVENTTYPE_SHIFTANDPROPAGATE   (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED)

Definition at line 67 of file heur_shiftandpropagate.c.

Referenced by SCIP_DECL_HEUREXEC().

Typedef Documentation

typedef enum TransformStatus TRANSFORMSTATUS

Definition at line 121 of file heur_shiftandpropagate.c.

typedef struct ConstraintMatrix CONSTRAINTMATRIX

Definition at line 145 of file heur_shiftandpropagate.c.

Enumeration Type Documentation

enum TransformStatus

status of a variable in heuristic transformation

Enumerator
TRANSFORMSTATUS_NONE	variable has not been transformed yet
TRANSFORMSTATUS_LB	variable has been shifted by using lower bound (x-lb)
TRANSFORMSTATUS_NEG	variable has been negated by using upper bound (ub-x)
TRANSFORMSTATUS_FREE	variable does not have to be shifted

Definition at line 114 of file heur_shiftandpropagate.c.

Function Documentation

static SCIP_Bool varIsDiscrete ( SCIP_VAR *  var, SCIP_Bool  impliscontinuous  )

static

returns whether a given variable is counted as discrete, depending on the parameter impliscontinuous

Parameters

var	variable to check for discreteness
impliscontinuous	should implicit integer variables be counted as continuous?

Definition at line 166 of file heur_shiftandpropagate.c.

References colIsDiscrete(), SCIP_Bool, SCIP_VARTYPE_IMPLINT, SCIPvarGetType(), and SCIPvarIsIntegral().

Referenced by initMatrix(), and SCIP_DECL_HEUREXEC().

static SCIP_Bool colIsDiscrete ( SCIP_COL *  col, SCIP_Bool  impliscontinuous  )

static

returns whether a given column is counted as discrete, depending on the parameter impliscontinuous

Parameters

col	column to check for discreteness
impliscontinuous	should implicit integer variables be counted as continuous?

Definition at line 176 of file heur_shiftandpropagate.c.

References getRowData(), SCIP_VARTYPE_IMPLINT, SCIPcolGetVar(), SCIPcolIsIntegral(), and SCIPvarGetType().

Referenced by initMatrix(), and varIsDiscrete().

static void getRowData ( CONSTRAINTMATRIX *  matrix, int  rowindex, SCIP_Real **  valpointer, SCIP_Real *  lhs, SCIP_Real *  rhs, int **  indexpointer, int *  nrowvals  )

static

returns nonzero values and corresponding columns of given row

Parameters

matrix	constraint matrix object
rowindex	index of the desired row
valpointer	pointer to store the nonzero coefficients of the row
lhs	lhs of the row
rhs	rhs of the row
indexpointer	pointer to store column indices which belong to the nonzeros
nrowvals	pointer to store number of nonzeros in the desired row (or NULL)

Definition at line 186 of file heur_shiftandpropagate.c.

References getColumnData(), and NULL.

Referenced by checkRowViolation(), colIsDiscrete(), and relaxVar().

static void getColumnData ( CONSTRAINTMATRIX *  matrix, int  colindex, SCIP_Real **  valpointer, int **  indexpointer, int *  ncolvals  )

static

returns nonzero values and corresponding rows of given column

Parameters

matrix	constraint matrix object
colindex	the index of the desired column
valpointer	pointer to store the nonzero coefficients of the column
indexpointer	pointer to store row indices which belong to the nonzeros
ncolvals	pointer to store number of nonzeros in the desired column

Definition at line 225 of file heur_shiftandpropagate.c.

References NULL, and relaxVar().

Referenced by checkViolations(), getOptimalShiftingValue(), getRowData(), transformVariable(), and updateTransformation().

static void relaxVar ( SCIP *  scip, SCIP_VAR *  var, CONSTRAINTMATRIX *  matrix, SCIP_Bool  normalize  )

static

relaxes a continuous variable from all its rows, which has influence on both the left and right hand side of the constraint.

Parameters

scip	current scip instance
var	variable which is relaxed from the problem
matrix	constraint matrix object
normalize	should coefficients and be normalized by rows maximum norms?

Definition at line 258 of file heur_shiftandpropagate.c.

References getRowData(), NULL, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPdebugMessage, SCIPgetRowMaxCoef(), SCIPinfinity(), SCIPisFeasGT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIProwGetLPPos(), SCIProwGetName(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), and transformVariable().

Referenced by getColumnData(), and initMatrix().

static void transformVariable ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, SCIP_HEURDATA *  heurdata, int  colpos  )

static

transforms bounds of a given variable s.t. its lower bound equals zero afterwards. If the variable already has lower bound zero, the variable is not transformed, if not, the variable's bounds are changed w.r.t. the smaller absolute value of its bounds in order to avoid numerical inaccuracies. If both lower and upper bound of the variable differ from infinity, there are two cases. If |lb| <= |ub|, the bounds are shifted by -lb, else a new variable ub - x replaces x. The transformation is memorized by the transform status of the variable s.t. retransformation is possible.

Parameters

scip	current scip instance
matrix	constraint matrix object
heurdata	heuristic data
colpos	position of variable column in matrix

Definition at line 361 of file heur_shiftandpropagate.c.

References FALSE, getColumnData(), initMatrix(), NULL, SCIP_Bool, SCIP_Real, SCIPcolGetVar(), SCIPcolIsInLP(), SCIPdebugMessage, SCIPinfinity(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRANSFORMSTATUS_FREE, TRANSFORMSTATUS_LB, TRANSFORMSTATUS_NEG, and TRUE.

Referenced by initMatrix(), relaxVar(), and updateTransformation().

static SCIP_RETCODE initMatrix ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, SCIP_HEURDATA *  heurdata, int *  colposs, SCIP_Bool  normalize, int *  nmaxrows, SCIP_Bool  relax, SCIP_Bool *  initialized, SCIP_Bool *  infeasible  )

static

initializes copy of the original coefficient matrix and applies heuristic specific adjustments: normalizing row vectors, transforming variable domains such that lower bound is zero, and relaxing continuous variables.

Parameters

scip	current scip instance
matrix	constraint matrix object to be initialized
heurdata	heuristic data
colposs	position of columns according to variable type sorting
normalize	should coefficients and be normalized by rows maximum norms?
nmaxrows	maximum number of rows a variable appears in
relax	should continuous variables be relaxed from the problem?
initialized	was the initialization successful?
infeasible	is the problem infeasible?

Definition at line 469 of file heur_shiftandpropagate.c.

References colIsDiscrete(), FALSE, freeMatrix(), MAX, NULL, relaxVar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPcolGetLPPos(), SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPcolGetVar(), SCIPdebug, SCIPdebugMessage, SCIPgetLPRowsData(), SCIPgetRowMaxCoef(), SCIPinfinity(), SCIPisFeasGT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPprintRow(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), TRANSFORMSTATUS_NONE, transformVariable(), TRUE, and varIsDiscrete().

Referenced by SCIP_DECL_HEUREXEC(), and transformVariable().

static void freeMatrix ( SCIP *  scip, CONSTRAINTMATRIX **  matrix  )

static

frees all members of the heuristic matrix

Parameters

scip	current SCIP instance
matrix	constraint matrix object

Definition at line 722 of file heur_shiftandpropagate.c.

References checkRowViolation(), NULL, SCIPfreeBuffer, and SCIPfreeMemoryArray.

Referenced by initMatrix(), and SCIP_DECL_HEUREXEC().

static void checkRowViolation ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, int  rowindex, int *  violatedrows, int *  violatedrowpos, int *  nviolatedrows, int *  rowweights, SCIP_Bool  updateweights  )

static

updates the information about a row whenever violation status changes

Parameters

scip	current SCIP instance
matrix	constraint matrix object
rowindex	index of the row
violatedrows	contains all violated rows
violatedrowpos	positions of rows in the violatedrows array
nviolatedrows	pointer to update total number of violated rows
rowweights	row weight storage
updateweights	should row weight be increased every time the row is violated?

Definition at line 770 of file heur_shiftandpropagate.c.

References checkViolations(), getRowData(), NULL, SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), and SCIPisFeasLT().

Referenced by checkViolations(), and freeMatrix().

static void checkViolations ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, int  colidx, int *  violatedrows, int *  violatedrowpos, int *  nviolatedrows, int *  rowweights, SCIP_Bool  updateweights  )

static

collects the necessary information about row violations for the zero-solution. That is, all solution values in heuristic transformation are zero.

Parameters

scip	current scip instance
matrix	constraint matrix object
colidx	column index for specific column, or -1 for all rows
violatedrows	violated rows
violatedrowpos	row positions of violated rows
nviolatedrows	pointer to store the number of violated rows
rowweights	weight array for every row
updateweights	should row weight be increased every time the row is violated?

Definition at line 835 of file heur_shiftandpropagate.c.

References BMSclearMemoryArray, checkRowViolation(), getColumnData(), NULL, retransformVariable(), SCIP_Real, SCIPdebugMessage, SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), and SCIPisFeasLT().

Referenced by checkRowViolation(), SCIP_DECL_HEUREXEC(), and updateTransformation().

static SCIP_Real retransformVariable ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, SCIP_VAR *  var, int  varindex, SCIP_Real  solvalue  )

static

retransforms solution values of variables according to their transformation status

Parameters

scip	current scip instance
matrix	constraint matrix object
var	variable whose solution value has to be retransformed
varindex	permutation of variable indices according to sorting
solvalue	solution value of the variable

Definition at line 896 of file heur_shiftandpropagate.c.

References getOptimalShiftingValue(), NULL, SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRANSFORMSTATUS_LB, TRANSFORMSTATUS_NEG, and TRANSFORMSTATUS_NONE.

Referenced by checkViolations(), and SCIP_DECL_HEUREXEC().

static SCIP_RETCODE getOptimalShiftingValue ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, int  varindex, int  direction, int *  rowweights, SCIP_Real *  steps, int *  violationchange, SCIP_Real *  beststep, int *  rowviolations  )

static

determines the best shifting value of a variable

Parameters

scip	current scip instance
matrix	constraint matrix object
varindex	index of variable which should be shifted
direction	the direction for this variable
rowweights	weighting of rows for best shift calculation
steps	buffer array to store the individual steps for individual rows
violationchange	buffer array to store the individual change of feasibility of row
beststep	pointer to store optimal shifting step
rowviolations	pointer to store new weighted sum of row violations, i.e, v - f

Definition at line 930 of file heur_shiftandpropagate.c.

References FALSE, getColumnData(), NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPfeasCeil(), SCIPfeasFloor(), SCIPinfinity(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisFeasLT(), SCIPisInfinity(), SCIPsortRealInt(), TRUE, and updateTransformation().

Referenced by retransformVariable(), and SCIP_DECL_HEUREXEC().

static SCIP_RETCODE updateTransformation ( SCIP *  scip, CONSTRAINTMATRIX *  matrix, SCIP_HEURDATA *  heurdata, int  varindex, SCIP_Real  lb, SCIP_Real  ub, int *  violatedrows, int *  violatedrowpos, int *  nviolatedrows  )

static

updates transformation of a given variable by taking into account current local bounds. if the bounds have changed since last update, updating the heuristic specific upper bound of the variable, its current transformed solution value and all affected rows is necessary.

Parameters

scip	current scip
matrix	constraint matrix object
heurdata	heuristic data
varindex	index of variable in matrix
lb	local lower bound of the variable
ub	local upper bound of the variable
violatedrows	violated rows
violatedrowpos	violated row positions
nviolatedrows	pointer to store number of violated rows

Definition at line 1109 of file heur_shiftandpropagate.c.

References checkViolations(), FALSE, getColumnData(), NULL, SCIP_Bool, SCIP_DECL_SORTPTRCOMP(), SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPdebugMessage, SCIPerrorMessage, SCIPinfinity(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisInfinity(), TRANSFORMSTATUS_FREE, TRANSFORMSTATUS_LB, TRANSFORMSTATUS_NEG, TRANSFORMSTATUS_NONE, transformVariable(), and TRUE.

Referenced by getOptimalShiftingValue(), SCIP_DECL_EVENTEXEC(), and SCIP_DECL_HEUREXEC().

static SCIP_DECL_SORTPTRCOMP ( heurSortColsShiftandpropagate  )

static

comparison method for columns; binary < integer < implicit < continuous variables

Definition at line 1232 of file heur_shiftandpropagate.c.

References NULL, SCIP_DECL_HEUREXIT(), SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPABORT, SCIPcolGetVar(), SCIPerrorMessage, and SCIPvarGetType().

Referenced by updateTransformation().

static SCIP_DECL_HEUREXIT ( heurExitShiftandpropagate  )

static

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

Definition at line 1301 of file heur_shiftandpropagate.c.

References NULL, SCIP_DECL_HEURINIT(), SCIP_OKAY, SCIPheurGetData(), SCIPstatistic, and SCIPstatisticMessage.

Referenced by SCIP_DECL_SORTPTRCOMP().

static SCIP_DECL_HEURINIT ( heurInitShiftandpropagate  )

static

initialization method of primal heuristic(called after problem was transformed). We only need this method for statistic mode of heuristic.

Definition at line 1331 of file heur_shiftandpropagate.c.

References DEFAULT_RANDSEED, NULL, SCIP_DECL_HEURFREE(), SCIP_LPSOLSTAT_NOTSOLVED, SCIP_OKAY, SCIPheurGetData(), and SCIPstatistic.

Referenced by SCIP_DECL_HEUREXIT().

static SCIP_DECL_HEURFREE ( heurFreeShiftandpropagate  )

static

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

Definition at line 1355 of file heur_shiftandpropagate.c.

References NULL, SCIP_DECL_HEURCOPY(), SCIP_OKAY, SCIPeventhdlrGetData(), SCIPfreeMemory, SCIPheurGetData(), and SCIPheurSetData().

Referenced by SCIP_DECL_HEURINIT().

static SCIP_DECL_HEURCOPY ( heurCopyShiftandpropagate  )

static

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

Definition at line 1380 of file heur_shiftandpropagate.c.

References HEUR_NAME, NULL, SCIP_CALL, SCIP_DECL_HEUREXEC(), SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurShiftandpropagate().

Referenced by SCIP_DECL_HEURFREE().

static SCIP_DECL_HEUREXEC ( heurExecShiftandpropagate  )

static

execution method of primal heuristic

Definition at line 1394 of file heur_shiftandpropagate.c.

References BMSclearMemoryArray, BMScopyMemoryArray, checkViolations(), DEFAULT_PROPBREAKER, DEFAULT_WEIGHT_EQUALITY, DEFAULT_WEIGHT_INEQUALITY, EVENTTYPE_SHIFTANDPROPAGATE, FALSE, freeMatrix(), getOptimalShiftingValue(), initMatrix(), NULL, retransformVariable(), SCIP_Bool, SCIP_CALL, SCIP_DECL_EVENTEXEC(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_Longint, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPallocBuffer, SCIPallocBufferArray, SCIPbacktrackProbing(), SCIPcatchVarEvent(), SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPconstructLP(), SCIPcreateSol(), SCIPdebug, SCIPdebugMessage, SCIPdisableVarHistory(), SCIPdropVarEvent(), SCIPenableVarHistory(), SCIPendProbing(), SCIPeventhdlrGetData(), SCIPfixVarProbing(), SCIPflushLP(), SCIPfreeBuffer, SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetBestSol(), SCIPgetDepth(), SCIPgetDepthLimit(), SCIPgetLPColsData(), SCIPgetLPSolstat(), SCIPgetNContVars(), SCIPgetNLPIterations(), SCIPgetNLPRows(), SCIPgetNVars(), SCIPgetProbingDepth(), SCIPgetSolOrigObj(), SCIPgetVars(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisLE(), SCIPisLPConstructed(), SCIPisStopped(), SCIPlinkLPSol(), SCIPnewProbingNode(), SCIPpermuteIntArray(), SCIPprintSol(), SCIPpropagateProbing(), SCIPsetSolVal(), SCIPsolSetHeur(), SCIPsolveProbingLP(), SCIPsortDownIntInt(), SCIPsortDownRealInt(), SCIPsortIntInt(), SCIPsortPtr(), SCIPsortRealInt(), SCIPstartProbing(), SCIPstatistic, SCIPstatisticMessage, SCIPtrySol(), SCIPvarGetCol(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), SCIPvarIsInLP(), SCIPvarIsIntegral(), SCIPwarningMessage(), TRANSFORMSTATUS_FREE, TRUE, updateTransformation(), and varIsDiscrete().

Referenced by SCIP_DECL_HEURCOPY().

static SCIP_DECL_EVENTEXEC ( eventExecShiftandpropagate  )

static

event handler execution method for the heuristic which catches all events in which a lower or upper bound were tightened

Definition at line 2281 of file heur_shiftandpropagate.c.

References EVENTHDLR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcolGetVar(), SCIPeventhdlrGetData(), SCIPeventhdlrGetName(), SCIPincludeHeurShiftandpropagate(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and updateTransformation().

Referenced by SCIP_DECL_HEUREXEC().

SCIP_RETCODE SCIPincludeHeurShiftandpropagate

(

SCIP *

scip

)

creates the shiftandpropagate primal heuristic and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 2325 of file heur_shiftandpropagate.c.

References DEFAULT_BINLOCKSFIRST, DEFAULT_COLLECTSTATS, DEFAULT_CUTOFFBREAKER, DEFAULT_FIXBINLOCKS, DEFAULT_IMPLISCONTINUOUS, DEFAULT_MAXCUTOFFQUOT, DEFAULT_NORMALIZE, DEFAULT_NOZEROFIXING, DEFAULT_NPROPROUNDS, DEFAULT_ONLYWITHOUTSOL, DEFAULT_PREFERBINARIES, DEFAULT_PROBING, DEFAULT_RELAX, DEFAULT_SELECTBEST, DEFAULT_SORTKEY, DEFAULT_SORTVARS, DEFAULT_STOPAFTERFEASIBLE, DEFAULT_UPDATEWEIGHTS, EVENTHDLR_DESC, EVENTHDLR_NAME, HEUR_DESC, HEUR_DISPCHAR, HEUR_FREQ, HEUR_FREQOFS, HEUR_MAXDEPTH, HEUR_NAME, HEUR_PRIORITY, HEUR_TIMING, HEUR_USESSUBSCIP, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddCharParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocMemory, SCIPincludeEventhdlrBasic(), SCIPincludeHeurBasic(), SCIPsetHeurCopy(), SCIPsetHeurExit(), SCIPsetHeurFree(), SCIPsetHeurInit(), SORTKEYS, and TRUE.

Referenced by SCIP_DECL_EVENTEXEC(), SCIP_DECL_HEURCOPY(), and SCIPincludeDefaultPlugins().