Diving heuristic that chooses fixings w.r.t. changes in the solution density after Pryor and Chinneck.
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.
Variables | |
heurdata = SCIPheurGetData(heur) | |
return | SCIP_OKAY |
#define HEUR_NAME "distributiondiving" |
Definition at line 55 of file heur_distributiondiving.c.
#define HEUR_DESC "Diving heuristic that chooses fixings w.r.t. changes in the solution density" |
Definition at line 56 of file heur_distributiondiving.c.
#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_DIVING |
Definition at line 57 of file heur_distributiondiving.c.
#define HEUR_PRIORITY -1003300 |
Definition at line 58 of file heur_distributiondiving.c.
#define HEUR_FREQ 10 |
Definition at line 59 of file heur_distributiondiving.c.
#define HEUR_FREQOFS 3 |
Definition at line 60 of file heur_distributiondiving.c.
#define HEUR_MAXDEPTH -1 |
Definition at line 61 of file heur_distributiondiving.c.
#define HEUR_TIMING SCIP_HEURTIMING_AFTERLPPLUNGE |
Definition at line 62 of file heur_distributiondiving.c.
#define HEUR_USESSUBSCIP FALSE |
does the heuristic use a secondary SCIP instance?
Definition at line 63 of file heur_distributiondiving.c.
#define EVENT_DISTRIBUTION SCIP_EVENTTYPE_BOUNDCHANGED |
the event type to be handled by this event handler
Definition at line 64 of file heur_distributiondiving.c.
#define EVENTHDLR_NAME "eventhdlr_distributiondiving" |
Definition at line 65 of file heur_distributiondiving.c.
#define DIVESET_DIVETYPES SCIP_DIVETYPE_INTEGRALITY |
bit mask that represents all supported dive types
Definition at line 66 of file heur_distributiondiving.c.
#define DIVESET_ISPUBLIC FALSE |
is this dive set publicly available (ie., can be used by other primal heuristics?)
Definition at line 67 of file heur_distributiondiving.c.
#define DEFAULT_MINRELDEPTH 0.0 |
minimal relative depth to start diving
Definition at line 73 of file heur_distributiondiving.c.
#define DEFAULT_MAXRELDEPTH 1.0 |
maximal relative depth to start diving
Definition at line 74 of file heur_distributiondiving.c.
#define DEFAULT_MAXLPITERQUOT 0.05 |
maximal fraction of diving LP iterations compared to node LP iterations
Definition at line 75 of file heur_distributiondiving.c.
#define DEFAULT_MAXLPITEROFS 1000 |
additional number of allowed LP iterations
Definition at line 76 of file heur_distributiondiving.c.
#define DEFAULT_MAXDIVEUBQUOT 0.8 |
maximal quotient (curlowerbound - lowerbound)/(cutoffbound - lowerbound) where diving is performed (0.0: no limit)
Definition at line 77 of file heur_distributiondiving.c.
#define DEFAULT_MAXDIVEAVGQUOT 0.0 |
maximal quotient (curlowerbound - lowerbound)/(avglowerbound - lowerbound) where diving is performed (0.0: no limit)
Definition at line 79 of file heur_distributiondiving.c.
#define DEFAULT_MAXDIVEUBQUOTNOSOL 0.1 |
maximal UBQUOT when no solution was found yet (0.0: no limit)
Definition at line 81 of file heur_distributiondiving.c.
#define DEFAULT_MAXDIVEAVGQUOTNOSOL 0.0 |
maximal AVGQUOT when no solution was found yet (0.0: no limit)
Definition at line 82 of file heur_distributiondiving.c.
#define DEFAULT_BACKTRACK TRUE |
use one level of backtracking if infeasibility is encountered?
Definition at line 83 of file heur_distributiondiving.c.
#define DEFAULT_LPRESOLVEDOMCHGQUOT 0.15 |
percentage of immediate domain changes during probing to trigger LP resolve
Definition at line 84 of file heur_distributiondiving.c.
#define DEFAULT_LPSOLVEFREQ 0 |
LP solve frequency for diving heuristics
Definition at line 85 of file heur_distributiondiving.c.
#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 86 of file heur_distributiondiving.c.
#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 89 of file heur_distributiondiving.c.
#define SCOREPARAM_VALUESLEN 5 |
Definition at line 91 of file heur_distributiondiving.c.
Referenced by SCIP_DECL_HEUREXEC().
#define DEFAULT_SCOREPARAM 'r' |
default scoring parameter to guide the diving
Definition at line 92 of file heur_distributiondiving.c.
#define DEFAULT_RANDSEED 117 |
initial seed for random number generation
Definition at line 93 of file heur_distributiondiving.c.
#define divesetAvailableDistributiondiving NULL |
Definition at line 1042 of file heur_distributiondiving.c.
Referenced by SCIPincludeHeurDistributiondiving().
|
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
scip | SCIP data structure |
heurdata | heuristic data |
maxindex | row index at hand (size must be at least this large) |
Definition at line 130 of file heur_distributiondiving.c.
References assert(), EVENT_DISTRIBUTION, heurdata, NULL, nvars, r, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPallocBufferArray, SCIPcatchVarEvent(), SCIPfeasCeil(), SCIPgetNVars(), SCIPgetStage(), SCIPgetVars(), SCIPreallocBufferArray, SCIPvarGetProbindex(), SCIPvarIsActive(), and vars.
Referenced by calcBranchScore(), SCIP_DECL_HEUREXEC(), and varProcessBoundChanges().
|
static |
update the variables current lower and upper bound
scip | SCIP data structure |
heurdata | heuristic data |
var | the variable to update current bounds |
Definition at line 218 of file heur_distributiondiving.c.
References assert(), heurdata, NULL, SCIP_Real, SCIPisFeasLE(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetUbLocal(), and var.
Referenced by rowCalculateGauss(), SCIP_DECL_DIVESETGETSCORE(), and varProcessBoundChanges().
|
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.
scip | SCIP data structure |
heurdata | the heuristic rule data |
row | the row for which the gaussian normal distribution has to be calculated |
mu | pointer to store the mean value of the gaussian normal distribution |
sigma2 | pointer to store the variance value of the gaussian normal distribution |
rowinfinitiesdown | pointer to store the number of variables with infinite bounds to DECREASE activity |
rowinfinitiesup | pointer to store the number of variables with infinite bounds to INCREASE activity |
Definition at line 251 of file heur_distributiondiving.c.
References assert(), c, heurdata, heurdataUpdateCurrentBounds(), NULL, SCIP_INVALID, SCIP_Real, SCIPcolGetVar(), SCIPdebug, SCIPdebugMsg, SCIPisFeasLE(), SCIPisFeasNegative(), SCIPisInfinity(), SCIPprintRow(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetVals(), SCIPvarCalcDistributionParameters(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbLocal(), and SQR.
Referenced by calcBranchScore().
|
static |
calculate the branching score of a variable, depending on the chosen score parameter
scip | current SCIP |
heurdata | branch rule data |
var | candidate variable |
lpsolval | current fractional LP-relaxation solution value |
upscore | pointer to store the variable score when branching on it in upward direction |
downscore | pointer to store the variable score when branching on it in downward direction |
scoreparam | the score parameter of this heuristic |
Definition at line 363 of file heur_distributiondiving.c.
References assert(), FALSE, heurdata, heurdataEnsureArraySize(), i, 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(), SQR, and var.
Referenced by SCIP_DECL_DIVESETGETSCORE().
|
static |
free heuristic data
scip | SCIP data structure |
heurdata | heuristic data |
Definition at line 565 of file heur_distributiondiving.c.
References assert(), EVENT_DISTRIBUTION, heurdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPdropVarEvent(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetVars(), SCIPvarGetProbindex(), var, and vars.
Referenced by SCIP_DECL_HEUREXEC().
|
static |
add variable to the bound change event queue; skipped if variable is already in there, or if variable has no row currently watched
heurdata | heuristic data |
var | the variable whose bound changes need to be processed |
Definition at line 618 of file heur_distributiondiving.c.
References assert(), heurdata, NULL, SCIP_INVALID, SCIPvarGetProbindex(), and var.
Referenced by SCIP_DECL_EVENTEXEC().
|
static |
returns the next unprocessed variable (last in, first out) with pending bound changes, or NULL
heurdata | heuristic data |
Definition at line 662 of file heur_distributiondiving.c.
References assert(), heurdata, NULL, SCIPvarGetProbindex(), and var.
Referenced by SCIP_DECL_DIVESETGETSCORE().
|
static |
process a variable from the queue of changed variables
scip | SCIP data structure |
heurdata | heuristic data |
var | the variable whose bound changes need to be processed |
Definition at line 691 of file heur_distributiondiving.c.
References assert(), heurdata, heurdataEnsureArraySize(), heurdataUpdateCurrentBounds(), MAX, NULL, r, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPcolGetNNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPinProbing(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisInfinity(), SCIProwGetIndex(), SCIPvarCalcDistributionParameters(), SCIPvarGetCol(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbLocal(), SQR, and var.
Referenced by SCIP_DECL_DIVESETGETSCORE().
|
static |
destructor of event handler to free user data (called when SCIP is exiting)
Definition at line 814 of file heur_distributiondiving.c.
References assert(), NULL, SCIP_OKAY, SCIPeventhdlrGetData(), SCIPeventhdlrSetData(), and SCIPfreeBlockMemory.
|
static |
copy method for primal heuristic plugins (called when SCIP copies plugins)
Definition at line 833 of file heur_distributiondiving.c.
References assert(), HEUR_NAME, NULL, SCIP_CALL, SCIP_OKAY, SCIPheurGetName(), and SCIPincludeHeurDistributiondiving().
static assert | ( | heur ! | = NULL | ) |
assert | ( | strcmp(SCIPheurGetName(heur), HEUR_NAME) | = =0 | ) |
References HEUR_NAME.
SCIPfreeBlockMemory | ( | scip | , |
& | heurdata ) |
References heurdata.
|
static |
scoring callback for distribution diving. best candidate maximizes the distribution score
Definition at line 906 of file heur_distributiondiving.c.
References assert(), calcBranchScore(), diveset, FALSE, heurdata, heurdataPopBoundChangeVar(), heurdataUpdateCurrentBounds(), MAX, NULL, roundup, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPdivesetGetHeur(), SCIPheurGetData(), SCIPisFeasEQ(), SCIPisFeasLE(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetUbLocal(), and varProcessBoundChanges().
|
static |
execution method of primal heuristic
Definition at line 973 of file heur_distributiondiving.c.
References assert(), diveset, HEUR_NAME, heurdata, heurdataEnsureArraySize(), heurdataFreeArrays(), nlprows, NULL, result, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_DIVECONTEXT_SINGLE, SCIP_OKAY, SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNLPRows(), SCIPhasCurrentNodeLP(), SCIPheurGetData(), SCIPheurGetDivesets(), SCIPheurGetName(), SCIPheurGetNCalls(), SCIPheurGetNDivesets(), SCIPperformGenericDivingAlgorithm(), SCOREPARAM_VALUES, and SCOREPARAM_VALUESLEN.
|
static |
event execution method of distribution branching which handles bound change events of variables
Definition at line 1019 of file heur_distributiondiving.c.
References assert(), heurdata, heurdataAddBoundChangeVar(), NULL, SCIP_OKAY, SCIPeventGetVar(), SCIPeventhdlrGetData(), and var.
heurdata = SCIPheurGetData(heur) |
Definition at line 856 of file heur_distributiondiving.c.
return SCIP_OKAY |
Definition at line 861 of file heur_distributiondiving.c.