Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

shiftandpropagate primal heuristic

Author
Timo Berthold
Gregor Hendel

Definition in file heur_shiftandpropagate.c.

#include "blockmemshell/memory.h"
#include "scip/heur_shiftandpropagate.h"
#include "scip/pub_event.h"
#include "scip/pub_heur.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_sol.h"
#include "scip/pub_var.h"
#include "scip/scip_event.h"
#include "scip/scip_general.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_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_randnumgen.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.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   SCIP_HEURDISPCHAR_PROP
 
#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   29
 
#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 DEFAULT_MINFIXINGRATELP   0.0
 
#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

◆ HEUR_NAME

#define HEUR_NAME   "shiftandpropagate"

◆ HEUR_DESC

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

Definition at line 62 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_PROP

Definition at line 63 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   1000

Definition at line 64 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ HEUR_FREQ

#define HEUR_FREQ   0

Definition at line 65 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 66 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 67 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_BEFORENODE

Definition at line 68 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 69 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_WEIGHT_INEQUALITY

#define DEFAULT_WEIGHT_INEQUALITY   1

the heuristic row weight for inequalities

Definition at line 71 of file heur_shiftandpropagate.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ DEFAULT_WEIGHT_EQUALITY

#define DEFAULT_WEIGHT_EQUALITY   3

the heuristic row weight for equations

Definition at line 72 of file heur_shiftandpropagate.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ DEFAULT_RELAX

#define DEFAULT_RELAX   TRUE

Should continuous variables be relaxed from the problem?

Definition at line 73 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_PROBING

#define DEFAULT_PROBING   TRUE

Is propagation of solution values enabled?

Definition at line 74 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_ONLYWITHOUTSOL

#define DEFAULT_ONLYWITHOUTSOL   TRUE

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

Definition at line 75 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_NPROPROUNDS

#define DEFAULT_NPROPROUNDS   10

The default number of propagation rounds for each propagation used

Definition at line 76 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_PROPBREAKER

#define DEFAULT_PROPBREAKER   65000

fixed maximum number of propagations

Definition at line 77 of file heur_shiftandpropagate.c.

Referenced by SCIP_DECL_HEUREXEC().

◆ DEFAULT_CUTOFFBREAKER

#define DEFAULT_CUTOFFBREAKER   15

fixed maximum number of allowed cutoffs before the heuristic stops

Definition at line 78 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   29

the default random seed for random number generation

Definition at line 79 of file heur_shiftandpropagate.c.

Referenced by SCIP_DECL_HEURINIT().

◆ DEFAULT_SORTKEY

#define DEFAULT_SORTKEY   'v'

the default key for variable sorting

Definition at line 80 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_SORTVARS

#define DEFAULT_SORTVARS   TRUE

should variables be processed in sorted order?

Definition at line 81 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_COLLECTSTATS

#define DEFAULT_COLLECTSTATS   TRUE

should variable statistics be collected during probing?

Definition at line 82 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_STOPAFTERFEASIBLE

#define DEFAULT_STOPAFTERFEASIBLE   TRUE

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

Definition at line 83 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_PREFERBINARIES

#define DEFAULT_PREFERBINARIES   TRUE

Should binary variables be shifted first?

Definition at line 84 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_SELECTBEST

#define DEFAULT_SELECTBEST   FALSE

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

Definition at line 85 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_MAXCUTOFFQUOT

#define DEFAULT_MAXCUTOFFQUOT   0.0

maximum percentage of allowed cutoffs before stopping the heuristic

Definition at line 86 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ SORTKEYS

#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 87 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_NOZEROFIXING

#define DEFAULT_NOZEROFIXING   FALSE

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

Definition at line 90 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_FIXBINLOCKS

#define DEFAULT_FIXBINLOCKS   TRUE

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

Definition at line 91 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_BINLOCKSFIRST

#define DEFAULT_BINLOCKSFIRST   FALSE

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

Definition at line 92 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_NORMALIZE

#define DEFAULT_NORMALIZE   TRUE

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

Definition at line 93 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_UPDATEWEIGHTS

#define DEFAULT_UPDATEWEIGHTS   FALSE

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

Definition at line 94 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_IMPLISCONTINUOUS

#define DEFAULT_IMPLISCONTINUOUS   TRUE

should implicit integer variables be treated as continuous variables?

Definition at line 95 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ DEFAULT_MINFIXINGRATELP

#define DEFAULT_MINFIXINGRATELP   0.0

minimum fixing rate over all variables (including continuous) to solve LP

Definition at line 96 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME   "eventhdlrshiftandpropagate"

◆ EVENTHDLR_DESC

#define EVENTHDLR_DESC   "event handler to catch bound changes"

Definition at line 99 of file heur_shiftandpropagate.c.

Referenced by SCIPincludeHeurShiftandpropagate().

◆ EVENTTYPE_SHIFTANDPROPAGATE

#define EVENTTYPE_SHIFTANDPROPAGATE   (SCIP_EVENTTYPE_BOUNDCHANGED | SCIP_EVENTTYPE_GBDCHANGED)

Definition at line 100 of file heur_shiftandpropagate.c.

Referenced by SCIP_DECL_HEUREXEC().

Typedef Documentation

◆ TRANSFORMSTATUS

Definition at line 155 of file heur_shiftandpropagate.c.

◆ CONSTRAINTMATRIX

typedef struct ConstraintMatrix CONSTRAINTMATRIX

Definition at line 179 of file heur_shiftandpropagate.c.

Enumeration Type Documentation

◆ 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 148 of file heur_shiftandpropagate.c.

Function Documentation

◆ varIsDiscrete()

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
varvariable to check for discreteness
impliscontinuousshould implicit integer variables be counted as continuous?

Definition at line 200 of file heur_shiftandpropagate.c.

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

Referenced by initMatrix(), and SCIP_DECL_HEUREXEC().

◆ colIsDiscrete()

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
colcolumn to check for discreteness
impliscontinuousshould implicit integer variables be counted as continuous?

Definition at line 210 of file heur_shiftandpropagate.c.

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

Referenced by initMatrix(), and varIsDiscrete().

◆ getRowData()

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
matrixconstraint matrix object
rowindexindex of the desired row
valpointerpointer to store the nonzero coefficients of the row
lhslhs of the row
rhsrhs of the row
indexpointerpointer to store column indices which belong to the nonzeros
nrowvalspointer to store number of nonzeros in the desired row (or NULL)

Definition at line 220 of file heur_shiftandpropagate.c.

References getColumnData(), and NULL.

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

◆ getColumnData()

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
matrixconstraint matrix object
colindexthe index of the desired column
valpointerpointer to store the nonzero coefficients of the column
indexpointerpointer to store row indices which belong to the nonzeros
ncolvalspointer to store number of nonzeros in the desired column

Definition at line 259 of file heur_shiftandpropagate.c.

References NULL, and relaxVar().

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

◆ relaxVar()

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
scipcurrent scip instance
varvariable which is relaxed from the problem
matrixconstraint matrix object
normalizeshould coefficients and be normalized by rows maximum norms?

Definition at line 292 of file heur_shiftandpropagate.c.

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

Referenced by getColumnData(), and initMatrix().

◆ transformVariable()

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
scipcurrent scip instance
matrixconstraint matrix object
heurdataheuristic data
colposposition of variable column in matrix

Definition at line 395 of file heur_shiftandpropagate.c.

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

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

◆ initMatrix()

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
scipcurrent scip instance
matrixconstraint matrix object to be initialized
heurdataheuristic data
colpossposition of columns according to variable type sorting
normalizeshould coefficients and be normalized by rows maximum norms?
nmaxrowsmaximum number of rows a variable appears in
relaxshould continuous variables be relaxed from the problem?
initializedwas the initialization successful?
infeasibleis the problem infeasible?

Definition at line 503 of file heur_shiftandpropagate.c.

References ABS, colIsDiscrete(), FALSE, freeMatrix(), MAX, NULL, relaxVar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPcolGetVar(), SCIPdebug, SCIPdebugMsg, 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().

◆ freeMatrix()

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

frees all members of the heuristic matrix

Parameters
scipcurrent SCIP instance
matrixconstraint matrix object

Definition at line 754 of file heur_shiftandpropagate.c.

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

Referenced by initMatrix(), and SCIP_DECL_HEUREXEC().

◆ checkRowViolation()

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
scipcurrent SCIP instance
matrixconstraint matrix object
rowindexindex of the row
violatedrowscontains all violated rows
violatedrowpospositions of rows in the violatedrows array
nviolatedrowspointer to update total number of violated rows
rowweightsrow weight storage
updateweightsshould row weight be increased every time the row is violated?

Definition at line 802 of file heur_shiftandpropagate.c.

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

Referenced by checkViolations(), and freeMatrix().

◆ checkViolations()

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
scipcurrent scip instance
matrixconstraint matrix object
colidxcolumn index for specific column, or -1 for all rows
violatedrowsviolated rows
violatedrowposrow positions of violated rows
nviolatedrowspointer to store the number of violated rows
rowweightsweight array for every row
updateweightsshould row weight be increased every time the row is violated?

Definition at line 867 of file heur_shiftandpropagate.c.

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

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

◆ retransformVariable()

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
scipcurrent scip instance
matrixconstraint matrix object
varvariable whose solution value has to be retransformed
varindexpermutation of variable indices according to sorting
solvaluesolution value of the variable

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

◆ getOptimalShiftingValue()

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
scipcurrent scip instance
matrixconstraint matrix object
varindexindex of variable which should be shifted
directionthe direction for this variable
rowweightsweighting of rows for best shift calculation
stepsbuffer array to store the individual steps for individual rows
violationchangebuffer array to store the individual change of feasibility of row
beststeppointer to store optimal shifting step
rowviolationspointer to store new weighted sum of row violations, i.e, v - f

Definition at line 962 of file heur_shiftandpropagate.c.

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

Referenced by retransformVariable(), and SCIP_DECL_HEUREXEC().

◆ updateTransformation()

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
scipcurrent scip
matrixconstraint matrix object
heurdataheuristic data
varindexindex of variable in matrix
lblocal lower bound of the variable
ublocal upper bound of the variable
violatedrowsviolated rows
violatedrowposviolated row positions
nviolatedrowspointer to store number of violated rows

Definition at line 1145 of file heur_shiftandpropagate.c.

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

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

◆ SCIP_DECL_SORTPTRCOMP()

static SCIP_DECL_SORTPTRCOMP ( heurSortColsShiftandpropagate  )
static

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

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

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitShiftandpropagate  )
static

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

Definition at line 1339 of file heur_shiftandpropagate.c.

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

Referenced by SCIP_DECL_SORTPTRCOMP().

◆ SCIP_DECL_HEURINIT()

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 1371 of file heur_shiftandpropagate.c.

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

Referenced by SCIP_DECL_HEUREXIT().

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeShiftandpropagate  )
static

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

Definition at line 1396 of file heur_shiftandpropagate.c.

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

Referenced by SCIP_DECL_HEURINIT().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyShiftandpropagate  )
static

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

Definition at line 1421 of file heur_shiftandpropagate.c.

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

Referenced by SCIP_DECL_HEURFREE().

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecShiftandpropagate  )
static

execution method of primal heuristic

Definition at line 1435 of file heur_shiftandpropagate.c.

References b, BMSclearMemoryArray, BMScopyMemoryArray, checkViolations(), DEFAULT_PROPBREAKER, DEFAULT_WEIGHT_EQUALITY, DEFAULT_WEIGHT_INEQUALITY, EVENTTYPE_SHIFTANDPROPAGATE, FALSE, freeMatrix(), getOptimalShiftingValue(), HEUR_NAME, initMatrix(), NULL, r, REALABS, retransformVariable(), SCIP_Bool, SCIP_CALL, SCIP_DECL_EVENTEXEC(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FOUNDSOL, SCIP_LOCKTYPE_MODEL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MAXSTRLEN, SCIP_MAXTREEDEPTH, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIP_VERBLEVEL_FULL, SCIPallocBuffer, SCIPallocBufferArray, SCIPbacktrackProbing(), SCIPcatchVarEvent(), SCIPceil(), SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPconstructLP(), SCIPcreateSol(), SCIPcutoffNode(), SCIPdebug, SCIPdebugMsg, SCIPdisableVarHistory(), SCIPdropVarEvent(), SCIPenableVarHistory(), SCIPendProbing(), SCIPepsilon(), SCIPeventhdlrGetData(), SCIPfixVarProbing(), SCIPflushLP(), SCIPfreeBuffer, SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetBestSol(), SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLPColsData(), SCIPgetLPSolstat(), SCIPgetNContVars(), SCIPgetNLPCols(), SCIPgetNLPIterations(), SCIPgetNLPRows(), SCIPgetNUnfixedLPCols(), SCIPgetNVars(), SCIPgetProbingDepth(), SCIPgetSolOrigObj(), SCIPgetVars(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisLE(), SCIPisLPConstructed(), SCIPisLPSolBasic(), SCIPisStopped(), SCIPlinkLPSol(), SCIPnewProbingNode(), SCIPprintSol(), SCIPpropagateProbing(), SCIPrandomPermuteIntArray(), SCIPsetSolVal(), SCIPsnprintfProbingStats(), SCIPsolSetHeur(), SCIPsolveProbingLP(), SCIPsortDownIntInt(), SCIPsortDownRealInt(), SCIPsortIntInt(), SCIPsortPtr(), SCIPsortRealInt(), SCIPstartProbing(), SCIPstatistic, SCIPstatisticMessage, SCIPtrySol(), SCIPvarGetCol(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), SCIPvarIsInLP(), SCIPvarIsIntegral(), SCIPverbMessage(), SCIPwarningMessage(), SCIPwriteLP(), TRANSFORMSTATUS_FREE, TRUE, updateTransformation(), and varIsDiscrete().

Referenced by SCIP_DECL_HEURCOPY().

◆ SCIP_DECL_EVENTEXEC()

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 2394 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().