Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

zirounding primal heuristic

Author
Gregor Hendel

Definition in file heur_zirounding.c.

#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

◆ 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
scippointer to current SCIP data structure
valthe 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
scippointer to current SCIP data structure
varthe variable for which lb and ub have to be calculated
currentvaluethe current value of var in the working solution
upperboundpointer to store the calculated upper bound on the variable shift
lowerboundpointer to store the calculated lower bound on the variable shift
upslacksarray that contains the slacks between row activities and the right hand sides of the rows
downslacksarray that contains lhs slacks
nslackscurrent number of slacks
numericalerrorflag 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
scippointer to current SCIP data structure
solworking solution
varpointer to variable to be modified
shiftvaluethe value by which the variable is shifted
upslacksupslacks of all rows the variable appears in
downslacksdownslacks of all rows the variable appears in
activitiesactivities of the LP rows
slackvarsthe slack variables for equality rows
slackcoeffsthe slack variable coefficients
nslackssize 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
scippointer to current SCIP data structure
rowthe row for which a slack variable is searched
varpointerpointer to store the slack variable
coeffpointerpointer 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()