Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

LP rounding heuristic that tries to recover from intermediate infeasibilities.

Author
Tobias Achterberg

Definition in file heur_rounding.c.

#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.

Referenced by SCIPincludeHeurRounding().

◆ HEUR_DESC

#define HEUR_DESC   "LP rounding heuristic with infeasibility recovering"

Definition at line 51 of file heur_rounding.c.

Referenced by SCIPincludeHeurRounding().

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_ROUNDING

Definition at line 52 of file heur_rounding.c.

Referenced by SCIPincludeHeurRounding().

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -1000

Definition at line 53 of file heur_rounding.c.

Referenced by SCIPincludeHeurRounding().

◆ HEUR_FREQ

#define HEUR_FREQ   1

Definition at line 54 of file heur_rounding.c.

Referenced by SCIPincludeHeurRounding().

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   0

Definition at line 55 of file heur_rounding.c.

Referenced by SCIPincludeHeurRounding().

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 56 of file heur_rounding.c.

Referenced by SCIPincludeHeurRounding().

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_DURINGLPLOOP

Definition at line 57 of file heur_rounding.c.

Referenced by SCIPincludeHeurRounding().

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 58 of file heur_rounding.c.

Referenced by SCIPincludeHeurRounding().

◆ 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 60 of file heur_rounding.c.

Referenced by SCIPincludeHeurRounding().

◆ DEFAULT_ONCEPERNODE

#define DEFAULT_ONCEPERNODE   FALSE

should the heuristic only be called once per node?

Definition at line 65 of file heur_rounding.c.

Referenced by SCIPincludeHeurRounding().

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
scipSCIP data structure
rowLP row
violrowsarray with currently violated rows
violrowposposition of LP rows in violrows array
nviolrowspointer to the number of currently violated rows
oldactivityold activity value of LP row
newactivitynew activity value of LP row

Definition at line 85 of file heur_rounding.c.

References NULL, SCIP_Bool, SCIP_Real, SCIPisFeasGT(), SCIPisFeasLT(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetRhs(), and updateActivities().

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
scipSCIP data structure
activitiesLP row activities
violrowsarray with currently violated rows
violrowposposition of LP rows in violrows array
nviolrowspointer to the number of currently violated rows
nlprowsnumber of rows in current LP
varvariable that has been changed
oldsolvalold solution value of variable
newsolvalnew solution value of variable

Definition at line 143 of file heur_rounding.c.

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

Referenced by updateViolations().

◆ 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
scipSCIP data structure
solprimal solution
minobjminimal objective value possible after rounding remaining fractional vars
rowLP row
directionshould the activity be increased (+1) or decreased (-1)?
roundvarpointer to store the rounding variable, returns NULL if impossible
oldsolvalpointer to store old (fractional) solution value of rounding variable
newsolvalpointer to store new (rounded) solution value of rounding variable

Definition at line 214 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(), SCIPvarGetType(), and selectIncreaseRounding().

Referenced by selectDecreaseRounding(), selectIncreaseRounding(), and updateActivities().

◆ 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
scipSCIP data structure
solprimal solution
minobjminimal objective value possible after rounding remaining fractional vars
rowLP row
roundvarpointer to store the rounding variable, returns NULL if impossible
oldsolvalold (fractional) solution value of rounding variable
newsolvalnew (rounded) solution value of rounding variable

Definition at line 316 of file heur_rounding.c.

References selectDecreaseRounding(), and selectRounding().

Referenced by selectRounding().

◆ 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
scipSCIP data structure
solprimal solution
minobjminimal objective value possible after rounding remaining fractional vars
rowLP row
roundvarpointer to store the rounding variable, returns NULL if impossible
oldsolvalold (fractional) solution value of rounding variable
newsolvalnew (rounded) solution value of rounding variable

Definition at line 331 of file heur_rounding.c.

References selectEssentialRounding(), and selectRounding().

Referenced by selectIncreaseRounding().

◆ 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
scipSCIP data structure
solprimal solution
minobjminimal objective value possible after rounding remaining fractional vars
lpcandsfractional variables in LP
nlpcandsnumber of fractional variables in LP
roundvarpointer to store the rounding variable, returns NULL if impossible
oldsolvalold (fractional) solution value of rounding variable
newsolvalnew (rounded) solution value of rounding variable

Definition at line 350 of file heur_rounding.c.

References NULL, SCIP_DECL_HEURCOPY(), 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 selectDecreaseRounding().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyRounding  )
static

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

Definition at line 433 of file heur_rounding.c.

Referenced by selectEssentialRounding().

◆ 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 447 of file heur_rounding.c.

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitRounding  )
static

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

Definition at line 466 of file heur_rounding.c.

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitRounding  )
static

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

Definition at line 484 of file heur_rounding.c.

◆ 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 500 of file heur_rounding.c.

◆ 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 519 of file heur_rounding.c.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecRounding  )
static

execution method of primal heuristic

Definition at line 530 of file heur_rounding.c.