Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Diving heuristic that chooses fixings w.r.t. changes in the solution density after Pryor and Chinneck.

Author
Gregor Hendel

Definition in file heur_distributiondiving.c.

#include "blockmemshell/memory.h"
#include "scip/branch_distribution.h"
#include "scip/heur_distributiondiving.h"
#include "scip/heuristics.h"
#include "scip/pub_event.h"
#include "scip/pub_heur.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.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_sol.h"
#include <string.h>

Go to the source code of this file.

Macros

#define HEUR_NAME   "distributiondiving"
 
#define HEUR_DESC   "Diving heuristic that chooses fixings w.r.t. changes in the solution density"
 
#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_DIVING
 
#define HEUR_PRIORITY   -1003300
 
#define HEUR_FREQ   10
 
#define HEUR_FREQOFS   3
 
#define HEUR_MAXDEPTH   -1
 
#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPPLUNGE
 
#define HEUR_USESSUBSCIP   FALSE
 
#define EVENT_DISTRIBUTION   SCIP_EVENTTYPE_BOUNDCHANGED
 
#define EVENTHDLR_NAME   "eventhdlr_distributiondiving"
 
#define DIVESET_DIVETYPES   SCIP_DIVETYPE_INTEGRALITY
 
#define DIVESET_ISPUBLIC   FALSE
 
#define SQUARED(x)   ((x) * (x))
 
#define DEFAULT_MINRELDEPTH   0.0
 
#define DEFAULT_MAXRELDEPTH   1.0
 
#define DEFAULT_MAXLPITERQUOT   0.05
 
#define DEFAULT_MAXLPITEROFS   1000
 
#define DEFAULT_MAXDIVEUBQUOT   0.8
 
#define DEFAULT_MAXDIVEAVGQUOT   0.0
 
#define DEFAULT_MAXDIVEUBQUOTNOSOL   0.1
 
#define DEFAULT_MAXDIVEAVGQUOTNOSOL   0.0
 
#define DEFAULT_BACKTRACK   TRUE
 
#define DEFAULT_LPRESOLVEDOMCHGQUOT   0.15
 
#define DEFAULT_LPSOLVEFREQ   0
 
#define DEFAULT_ONLYLPBRANCHCANDS   TRUE
 
#define SCOREPARAM_VALUES   "lhwvd"
 
#define SCOREPARAM_VALUESLEN   5
 
#define DEFAULT_SCOREPARAM   'r'
 
#define DEFAULT_RANDSEED   117
 
#define divesetAvailableDistributiondiving   NULL
 

Functions

static SCIP_RETCODE heurdataEnsureArraySize (SCIP *scip, SCIP_HEURDATA *heurdata, int maxindex)
 
static void heurdataUpdateCurrentBounds (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var)
 
static void rowCalculateGauss (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_ROW *row, SCIP_Real *mu, SCIP_Real *sigma2, int *rowinfinitiesdown, int *rowinfinitiesup)
 
static SCIP_RETCODE calcBranchScore (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var, SCIP_Real lpsolval, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
 
static SCIP_RETCODE heurdataFreeArrays (SCIP *scip, SCIP_HEURDATA *heurdata)
 
static void heurdataAddBoundChangeVar (SCIP_HEURDATA *heurdata, SCIP_VAR *var)
 
static SCIP_VARheurdataPopBoundChangeVar (SCIP_HEURDATA *heurdata)
 
static SCIP_RETCODE varProcessBoundChanges (SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var)
 
static SCIP_DECL_EVENTFREE (eventFreeDistributiondiving)
 
static SCIP_DECL_HEURCOPY (heurCopyDistributiondiving)
 
static SCIP_DECL_HEURFREE (heurFreeDistributiondiving)
 
static SCIP_DECL_HEURINIT (heurInitDistributiondiving)
 
static SCIP_DECL_HEUREXIT (heurExitDistributiondiving)
 
static SCIP_DECL_DIVESETGETSCORE (divesetGetScoreDistributiondiving)
 
static SCIP_DECL_HEUREXEC (heurExecDistributiondiving)
 
static SCIP_DECL_EVENTEXEC (eventExecDistribution)
 
SCIP_RETCODE SCIPincludeHeurDistributiondiving (SCIP *scip)
 

Macro Definition Documentation

◆ HEUR_NAME

#define HEUR_NAME   "distributiondiving"

Definition at line 46 of file heur_distributiondiving.c.

◆ HEUR_DESC

#define HEUR_DESC   "Diving heuristic that chooses fixings w.r.t. changes in the solution density"

Definition at line 47 of file heur_distributiondiving.c.

◆ HEUR_DISPCHAR

#define HEUR_DISPCHAR   SCIP_HEURDISPCHAR_DIVING

Definition at line 48 of file heur_distributiondiving.c.

◆ HEUR_PRIORITY

#define HEUR_PRIORITY   -1003300

Definition at line 49 of file heur_distributiondiving.c.

◆ HEUR_FREQ

#define HEUR_FREQ   10

Definition at line 50 of file heur_distributiondiving.c.

◆ HEUR_FREQOFS

#define HEUR_FREQOFS   3

Definition at line 51 of file heur_distributiondiving.c.

◆ HEUR_MAXDEPTH

#define HEUR_MAXDEPTH   -1

Definition at line 52 of file heur_distributiondiving.c.

◆ HEUR_TIMING

#define HEUR_TIMING   SCIP_HEURTIMING_AFTERLPPLUNGE

Definition at line 53 of file heur_distributiondiving.c.

◆ HEUR_USESSUBSCIP

#define HEUR_USESSUBSCIP   FALSE

does the heuristic use a secondary SCIP instance?

Definition at line 54 of file heur_distributiondiving.c.

◆ EVENT_DISTRIBUTION

#define EVENT_DISTRIBUTION   SCIP_EVENTTYPE_BOUNDCHANGED

the event type to be handled by this event handler

Definition at line 55 of file heur_distributiondiving.c.

Referenced by heurdataEnsureArraySize(), and heurdataFreeArrays().

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME   "eventhdlr_distributiondiving"

Definition at line 56 of file heur_distributiondiving.c.

◆ DIVESET_DIVETYPES

#define DIVESET_DIVETYPES   SCIP_DIVETYPE_INTEGRALITY

bit mask that represents all supported dive types

Definition at line 57 of file heur_distributiondiving.c.

◆ DIVESET_ISPUBLIC

#define DIVESET_ISPUBLIC   FALSE

is this dive set publicly available (ie., can be used by other primal heuristics?)

Definition at line 58 of file heur_distributiondiving.c.

◆ SQUARED

#define SQUARED (   x)    ((x) * (x))

◆ DEFAULT_MINRELDEPTH

#define DEFAULT_MINRELDEPTH   0.0

minimal relative depth to start diving

Definition at line 65 of file heur_distributiondiving.c.

◆ DEFAULT_MAXRELDEPTH

#define DEFAULT_MAXRELDEPTH   1.0

maximal relative depth to start diving

Definition at line 66 of file heur_distributiondiving.c.

◆ DEFAULT_MAXLPITERQUOT

#define DEFAULT_MAXLPITERQUOT   0.05

maximal fraction of diving LP iterations compared to node LP iterations

Definition at line 67 of file heur_distributiondiving.c.

◆ DEFAULT_MAXLPITEROFS

#define DEFAULT_MAXLPITEROFS   1000

additional number of allowed LP iterations

Definition at line 68 of file heur_distributiondiving.c.

◆ DEFAULT_MAXDIVEUBQUOT

#define DEFAULT_MAXDIVEUBQUOT   0.8

maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)

Definition at line 69 of file heur_distributiondiving.c.

◆ DEFAULT_MAXDIVEAVGQUOT

#define DEFAULT_MAXDIVEAVGQUOT   0.0

maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)

Definition at line 72 of file heur_distributiondiving.c.

◆ DEFAULT_MAXDIVEUBQUOTNOSOL

#define DEFAULT_MAXDIVEUBQUOTNOSOL   0.1

maximal UBQUOT when no solution was found yet (0.0: no limit)

Definition at line 75 of file heur_distributiondiving.c.

◆ DEFAULT_MAXDIVEAVGQUOTNOSOL

#define DEFAULT_MAXDIVEAVGQUOTNOSOL   0.0

maximal AVGQUOT when no solution was found yet (0.0: no limit)

Definition at line 76 of file heur_distributiondiving.c.

◆ DEFAULT_BACKTRACK

#define DEFAULT_BACKTRACK   TRUE

use one level of backtracking if infeasibility is encountered?

Definition at line 77 of file heur_distributiondiving.c.

◆ DEFAULT_LPRESOLVEDOMCHGQUOT

#define DEFAULT_LPRESOLVEDOMCHGQUOT   0.15

percentage of immediate domain changes during probing to trigger LP resolve

Definition at line 78 of file heur_distributiondiving.c.

◆ DEFAULT_LPSOLVEFREQ

#define DEFAULT_LPSOLVEFREQ   0

LP solve frequency for diving heuristics

Definition at line 79 of file heur_distributiondiving.c.

◆ DEFAULT_ONLYLPBRANCHCANDS

#define DEFAULT_ONLYLPBRANCHCANDS   TRUE

should only LP branching candidates be considered instead of the slower but more general constraint handler diving variable selection?

Definition at line 80 of file heur_distributiondiving.c.

◆ SCOREPARAM_VALUES

#define SCOREPARAM_VALUES   "lhwvd"

the score;largest 'd'ifference, 'l'owest cumulative probability,'h'ighest c.p., 'v'otes lowest c.p., votes highest c.p.('w'), 'r'evolving

Definition at line 84 of file heur_distributiondiving.c.

◆ SCOREPARAM_VALUESLEN

#define SCOREPARAM_VALUESLEN   5

Definition at line 87 of file heur_distributiondiving.c.

◆ DEFAULT_SCOREPARAM

#define DEFAULT_SCOREPARAM   'r'

default scoring parameter to guide the diving

Definition at line 88 of file heur_distributiondiving.c.

◆ DEFAULT_RANDSEED

#define DEFAULT_RANDSEED   117

initial seed for random number generation

Definition at line 89 of file heur_distributiondiving.c.

◆ divesetAvailableDistributiondiving

#define divesetAvailableDistributiondiving   NULL

Definition at line 1038 of file heur_distributiondiving.c.

Function Documentation

◆ heurdataEnsureArraySize()

static SCIP_RETCODE heurdataEnsureArraySize ( SCIP scip,
SCIP_HEURDATA heurdata,
int  maxindex 
)
static

ensure that maxindex + 1 rows can be represented in data arrays; memory gets reallocated with 10% extra space to save some time for future allocations

Parameters
scipSCIP data structure
heurdataheuristic data
maxindexrow index at hand (size must be at least this large)

Definition at line 126 of file heur_distributiondiving.c.

References EVENT_DISTRIBUTION, heurdataUpdateCurrentBounds(), NULL, r, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPallocBufferArray, SCIPcatchVarEvent(), SCIPfeasCeil(), SCIPgetNVars(), SCIPgetStage(), SCIPgetVars(), SCIPreallocBufferArray, SCIPvarGetProbindex(), and SCIPvarIsActive().

Referenced by calcBranchScore(), and varProcessBoundChanges().

◆ heurdataUpdateCurrentBounds()

static void heurdataUpdateCurrentBounds ( SCIP scip,
SCIP_HEURDATA heurdata,
SCIP_VAR var 
)
static

update the variables current lower and upper bound

Parameters
scipSCIP data structure
heurdataheuristic data
varthe variable to update current bounds

Definition at line 214 of file heur_distributiondiving.c.

References NULL, rowCalculateGauss(), SCIP_Real, SCIPisFeasLE(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), and SCIPvarGetUbLocal().

Referenced by heurdataEnsureArraySize(), rowCalculateGauss(), and varProcessBoundChanges().

◆ rowCalculateGauss()

static void rowCalculateGauss ( SCIP scip,
SCIP_HEURDATA heurdata,
SCIP_ROW row,
SCIP_Real mu,
SCIP_Real sigma2,
int *  rowinfinitiesdown,
int *  rowinfinitiesup 
)
static

calculates the initial mean and variance of the row activity normal distribution.

The mean value \( \mu \) is given by \( \mu = \sum_i=1^n c_i * (lb_i +ub_i) / 2 \) where \(n \) is the number of variables, and \( c_i, lb_i, ub_i \) are the variable coefficient and bounds, respectively. With the same notation, the variance \( \sigma^2 \) is given by \( \sigma^2 = \sum_i=1^n c_i^2 * \sigma^2_i \), with the variance being \( \sigma^2_i = ((ub_i - lb_i + 1)^2 - 1) / 12 \) for integer variables and \( \sigma^2_i = (ub_i - lb_i)^2 / 12 \) for continuous variables.

Parameters
scipSCIP data structure
heurdatathe heuristic rule data
rowthe row for which the gaussian normal distribution has to be calculated
mupointer to store the mean value of the gaussian normal distribution
sigma2pointer to store the variance value of the gaussian normal distribution
rowinfinitiesdownpointer to store the number of variables with infinite bounds to DECREASE activity
rowinfinitiesuppointer to store the number of variables with infinite bounds to INCREASE activity

Definition at line 247 of file heur_distributiondiving.c.

References calcBranchScore(), heurdataUpdateCurrentBounds(), NULL, SCIP_INVALID, SCIP_Real, SCIPcolGetVar(), SCIPdebug, SCIPdebugMsg, SCIPisFeasLE(), SCIPisFeasNegative(), SCIPisInfinity(), SCIPprintRow(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetVals(), SCIPvarCalcDistributionParameters(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbLocal(), and SQUARED.

Referenced by calcBranchScore(), and heurdataUpdateCurrentBounds().

◆ calcBranchScore()

static SCIP_RETCODE calcBranchScore ( SCIP scip,
SCIP_HEURDATA heurdata,
SCIP_VAR var,
SCIP_Real  lpsolval,
SCIP_Real upscore,
SCIP_Real downscore,
char  scoreparam 
)
static

calculate the branching score of a variable, depending on the chosen score parameter

Parameters
scipcurrent SCIP
heurdatabranch rule data
varcandidate variable
lpsolvalcurrent fractional LP-relaxation solution value
upscorepointer to store the variable score when branching on it in upward direction
downscorepointer to store the variable score when branching on it in downward direction
scoreparamthe score parameter of this heuristic

Definition at line 359 of file heur_distributiondiving.c.

References FALSE, heurdataEnsureArraySize(), heurdataFreeArrays(), MAX, NULL, rowCalculateGauss(), SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPdebugMsg, SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetRowLPFeasibility(), SCIPisInfinity(), SCIPisIntegral(), SCIPisNegative(), SCIPisSumPositive(), SCIProwCalcProbability(), SCIProwGetIndex(), SCIProwGetName(), SCIPupdateDistributionScore(), SCIPvarCalcDistributionParameters(), SCIPvarGetCol(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), and SQUARED.

Referenced by rowCalculateGauss().

◆ heurdataFreeArrays()

static SCIP_RETCODE heurdataFreeArrays ( SCIP scip,
SCIP_HEURDATA heurdata 
)
static

free heuristic data

Parameters
scipSCIP data structure
heurdataheuristic data

Definition at line 561 of file heur_distributiondiving.c.

References EVENT_DISTRIBUTION, heurdataAddBoundChangeVar(), NULL, SCIP_CALL, SCIP_OKAY, SCIPdropVarEvent(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetVars(), and SCIPvarGetProbindex().

Referenced by calcBranchScore().

◆ heurdataAddBoundChangeVar()

static void heurdataAddBoundChangeVar ( SCIP_HEURDATA heurdata,
SCIP_VAR var 
)
static

add variable to the bound change event queue; skipped if variable is already in there, or if variable has no row currently watched

Parameters
heurdataheuristic data
varthe variable whose bound changes need to be processed

Definition at line 614 of file heur_distributiondiving.c.

References heurdataPopBoundChangeVar(), NULL, SCIP_INVALID, and SCIPvarGetProbindex().

Referenced by heurdataFreeArrays().

◆ heurdataPopBoundChangeVar()

static SCIP_VAR* heurdataPopBoundChangeVar ( SCIP_HEURDATA heurdata)
static

returns the next unprocessed variable (last in, first out) with pending bound changes, or NULL

Parameters
heurdataheuristic data

Definition at line 658 of file heur_distributiondiving.c.

Referenced by heurdataAddBoundChangeVar().

◆ varProcessBoundChanges()

static SCIP_RETCODE varProcessBoundChanges ( SCIP scip,
SCIP_HEURDATA heurdata,
SCIP_VAR var 
)
static

◆ SCIP_DECL_EVENTFREE()

static SCIP_DECL_EVENTFREE ( eventFreeDistributiondiving  )
static

destructor of event handler to free user data (called when SCIP is exiting)

Definition at line 810 of file heur_distributiondiving.c.

Referenced by varProcessBoundChanges().

◆ SCIP_DECL_HEURCOPY()

static SCIP_DECL_HEURCOPY ( heurCopyDistributiondiving  )
static

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

Definition at line 829 of file heur_distributiondiving.c.

◆ SCIP_DECL_HEURFREE()

static SCIP_DECL_HEURFREE ( heurFreeDistributiondiving  )
static

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

Definition at line 843 of file heur_distributiondiving.c.

◆ SCIP_DECL_HEURINIT()

static SCIP_DECL_HEURINIT ( heurInitDistributiondiving  )
static

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

Definition at line 863 of file heur_distributiondiving.c.

◆ SCIP_DECL_HEUREXIT()

static SCIP_DECL_HEUREXIT ( heurExitDistributiondiving  )
static

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

Definition at line 883 of file heur_distributiondiving.c.

◆ SCIP_DECL_DIVESETGETSCORE()

static SCIP_DECL_DIVESETGETSCORE ( divesetGetScoreDistributiondiving  )
static

scoring callback for distribution diving. best candidate maximizes the distribution score

Definition at line 902 of file heur_distributiondiving.c.

◆ SCIP_DECL_HEUREXEC()

static SCIP_DECL_HEUREXEC ( heurExecDistributiondiving  )
static

execution method of primal heuristic

Definition at line 969 of file heur_distributiondiving.c.

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecDistribution  )
static

event execution method of distribution branching which handles bound change events of variables

Definition at line 1015 of file heur_distributiondiving.c.