Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

probability based branching rule based on an article by J. Pryor and J.W. Chinneck

Author
Gregor Hendel

The distribution branching rule selects a variable based on its impact on row activity distributions. More formally, let \( a(x) = a_1 x_1 + \dots + a_n x_n \leq b \) be a row of the LP. Let further \( l_i, u_i \in R\) denote the (finite) lower and upper bound, respectively, of the \( i \)-th variable \(x_i\). Viewing every variable \(x_i \) as (continuously) uniformly distributed within its bounds, we can approximately understand the row activity \(a(x)\) as a Gaussian random variate with mean value \( \mu = E[a(x)] = \sum_i a_i\frac{l_i + u_i}{2}\) and variance \( \sigma^2 = \sum_i a_i^2 \sigma_i^2 \), with \( \sigma_i^2 = \frac{(u_i - l_i)^2}{12}\) for continuous and \( \sigma_i^2 = \frac{(u_i - l_i + 1)^2 - 1}{12}\) for discrete variables. With these two parameters, we can calculate the probability to satisfy the row in terms of the cumulative distribution of the standard normal distribution: \( P(a(x) \leq b) = \Phi(\frac{b - \mu}{\sigma})\).

The impact of a variable on the probability to satisfy a constraint after branching can be estimated by altering the variable contribution to the sums described above. In order to keep the tree size small, variables are preferred which decrease the probability to satisfy a row because it is more likely to create infeasible subproblems.

The selection of the branching variable is subject to the parameter scoreparam. For both branching directions, an individual score is calculated. Available options for scoring methods are:

  • d: select a branching variable with largest difference in satisfaction probability after branching
  • l: lowest cumulative probability amongst all variables on all rows (after branching).
  • h: highest cumulative probability amongst all variables on all rows (after branching).
  • v: highest number of votes for lowering row probability for all rows a variable appears in.
  • w: highest number of votes for increasing row probability for all rows a variable appears in.

If the parameter usescipscore is set to TRUE, a single branching score is calculated from the respective up and down scores as defined by the SCIP branching score function (see advanced branching parameter scorefunc), otherwise, the variable with the single highest score is selected, and the maximizing direction is assigned higher branching priority.

The original idea of probability based branching schemes appeared in:

J. Pryor and J.W. Chinneck:
Faster Integer-Feasibility in Mixed-Integer Linear Programs by Branching to Force Change
Computers and Operations Research, vol. 38, 2011, p. 1143–1152
(Paper: PDF).

Definition in file branch_distribution.c.

#include "scip/branch_distribution.h"
#include "scip/pub_branch.h"
#include "scip/pub_event.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_event.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_message.h"
#include "scip/scip_mem.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_pricer.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include <string.h>

Go to the source code of this file.

Macros

#define BRANCHRULE_NAME   "distribution"
 
#define BRANCHRULE_DESC   "branching rule based on variable influence on cumulative normal distribution of row activities"
 
#define BRANCHRULE_PRIORITY   0
 
#define BRANCHRULE_MAXDEPTH   -1
 
#define BRANCHRULE_MAXBOUNDDIST   1.0
 
#define SCOREPARAM_VALUES   "dhlvw"
 
#define DEFAULT_SCOREPARAM   'v'
 
#define DEFAULT_PRIORITY   2.0
 
#define SQRTOFTWO   1.4142136
 
#define SQUARED(x)   ((x) * (x))
 
#define DEFAULT_ONLYACTIVEROWS   FALSE
 
#define DEFAULT_USEWEIGHTEDSCORE   FALSE
 
#define EVENTHDLR_NAME   "eventhdlr_distribution"
 
#define EVENT_DISTRIBUTION   SCIP_EVENTTYPE_BOUNDCHANGED
 

Functions

static SCIP_RETCODE branchruledataEnsureArraySize (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, int maxindex)
 
static void branchruledataUpdateCurrentBounds (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
 
void SCIPvarCalcDistributionParameters (SCIP *scip, SCIP_Real varlb, SCIP_Real varub, SCIP_VARTYPE vartype, SCIP_Real *mean, SCIP_Real *variance)
 
SCIP_Real SCIPcalcCumulativeDistribution (SCIP *scip, SCIP_Real mean, SCIP_Real variance, SCIP_Real value)
 
SCIP_Real SCIProwCalcProbability (SCIP *scip, SCIP_ROW *row, SCIP_Real mu, SCIP_Real sigma2, int rowinfinitiesdown, int rowinfinitiesup)
 
static void rowCalculateGauss (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_ROW *row, SCIP_Real *mu, SCIP_Real *sigma2, int *rowinfinitiesdown, int *rowinfinitiesup)
 
SCIP_RETCODE SCIPupdateDistributionScore (SCIP *scip, SCIP_Real currentprob, SCIP_Real newprobup, SCIP_Real newprobdown, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
 
static SCIP_RETCODE calcBranchScore (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var, SCIP_Real lpsolval, SCIP_Real *upscore, SCIP_Real *downscore, char scoreparam)
 
static void branchruledataFreeArrays (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
 
static void branchruledataAddBoundChangeVar (SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
 
static SCIP_VARbranchruledataPopBoundChangeVar (SCIP_BRANCHRULEDATA *branchruledata)
 
static SCIP_RETCODE varProcessBoundChanges (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_VAR *var)
 
static SCIP_DECL_EVENTFREE (eventFreeDistribution)
 
static SCIP_DECL_BRANCHCOPY (branchCopyDistribution)
 
static SCIP_DECL_BRANCHEXITSOL (branchExitsolDistribution)
 
static SCIP_DECL_BRANCHFREE (branchFreeDistribution)
 
static SCIP_DECL_BRANCHEXECLP (branchExeclpDistribution)
 
static SCIP_DECL_EVENTEXEC (eventExecDistribution)
 
SCIP_RETCODE SCIPincludeBranchruleDistribution (SCIP *scip)
 

Macro Definition Documentation

◆ BRANCHRULE_NAME

#define BRANCHRULE_NAME   "distribution"

◆ BRANCHRULE_DESC

#define BRANCHRULE_DESC   "branching rule based on variable influence on cumulative normal distribution of row activities"

Definition at line 91 of file branch_distribution.c.

Referenced by SCIPincludeBranchruleDistribution().

◆ BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY   0

Definition at line 92 of file branch_distribution.c.

Referenced by SCIPincludeBranchruleDistribution().

◆ BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 93 of file branch_distribution.c.

Referenced by SCIPincludeBranchruleDistribution().

◆ BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 94 of file branch_distribution.c.

Referenced by SCIPincludeBranchruleDistribution().

◆ SCOREPARAM_VALUES

#define SCOREPARAM_VALUES   "dhlvw"

Definition at line 96 of file branch_distribution.c.

Referenced by SCIPincludeBranchruleDistribution().

◆ DEFAULT_SCOREPARAM

#define DEFAULT_SCOREPARAM   'v'

Definition at line 97 of file branch_distribution.c.

Referenced by SCIPincludeBranchruleDistribution().

◆ DEFAULT_PRIORITY

#define DEFAULT_PRIORITY   2.0

Definition at line 98 of file branch_distribution.c.

Referenced by SCIP_DECL_BRANCHEXECLP().

◆ SQRTOFTWO

#define SQRTOFTWO   1.4142136

Definition at line 99 of file branch_distribution.c.

Referenced by SCIPcalcCumulativeDistribution().

◆ SQUARED

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

◆ DEFAULT_ONLYACTIVEROWS

#define DEFAULT_ONLYACTIVEROWS   FALSE

should only rows which are active at the current node be considered?

Definition at line 101 of file branch_distribution.c.

Referenced by SCIPincludeBranchruleDistribution().

◆ DEFAULT_USEWEIGHTEDSCORE

#define DEFAULT_USEWEIGHTEDSCORE   FALSE

should the branching score weigh up- and down-scores of a variable

Definition at line 102 of file branch_distribution.c.

Referenced by SCIPincludeBranchruleDistribution().

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME   "eventhdlr_distribution"

event handler name

Definition at line 105 of file branch_distribution.c.

Referenced by SCIPincludeBranchruleDistribution().

◆ EVENT_DISTRIBUTION

#define EVENT_DISTRIBUTION   SCIP_EVENTTYPE_BOUNDCHANGED

the event tyoe to be handled by this event handler

Definition at line 106 of file branch_distribution.c.

Referenced by branchruledataEnsureArraySize(), and SCIP_DECL_BRANCHEXITSOL().

Function Documentation

◆ branchruledataEnsureArraySize()

static SCIP_RETCODE branchruledataEnsureArraySize ( SCIP scip,
SCIP_BRANCHRULEDATA branchruledata,
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
branchruledatabranchruledata
maxindexrow index at hand (size must be at least this large)

Definition at line 147 of file branch_distribution.c.

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

Referenced by calcBranchScore(), SCIP_DECL_BRANCHEXECLP(), and varProcessBoundChanges().

◆ branchruledataUpdateCurrentBounds()

static void branchruledataUpdateCurrentBounds ( SCIP scip,
SCIP_BRANCHRULEDATA branchruledata,
SCIP_VAR var 
)
static
Parameters
scipSCIP data structure
branchruledatabranchrule data
varthe variable to update current bounds

Definition at line 235 of file branch_distribution.c.

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

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

◆ rowCalculateGauss()

static void rowCalculateGauss ( SCIP scip,
SCIP_BRANCHRULEDATA branchruledata,
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
branchruledatathe branching 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 436 of file branch_distribution.c.

References branchruledataUpdateCurrentBounds(), 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().

◆ calcBranchScore()

static SCIP_RETCODE calcBranchScore ( SCIP scip,
SCIP_BRANCHRULEDATA branchruledata,
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
branchruledatabranch 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 branching rule

Definition at line 619 of file branch_distribution.c.

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

Referenced by SCIP_DECL_BRANCHEXECLP().

◆ branchruledataFreeArrays()

static void branchruledataFreeArrays ( SCIP scip,
SCIP_BRANCHRULEDATA branchruledata 
)
static

free branchrule data

Parameters
scipSCIP data structure
branchruledatabranching rule data

Definition at line 812 of file branch_distribution.c.

References NULL, and SCIPfreeBlockMemoryArray.

Referenced by SCIP_DECL_BRANCHEXITSOL(), and SCIP_DECL_BRANCHFREE().

◆ branchruledataAddBoundChangeVar()

static void branchruledataAddBoundChangeVar ( SCIP_BRANCHRULEDATA branchruledata,
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
branchruledatabranchrule data
varthe variable whose bound changes need to be processed

Definition at line 841 of file branch_distribution.c.

References NULL, SCIP_INVALID, and SCIPvarGetProbindex().

Referenced by SCIP_DECL_EVENTEXEC().

◆ branchruledataPopBoundChangeVar()

static SCIP_VAR* branchruledataPopBoundChangeVar ( SCIP_BRANCHRULEDATA branchruledata)
static

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

Parameters
branchruledatabranchrule data

Definition at line 883 of file branch_distribution.c.

References NULL, and SCIPvarGetProbindex().

Referenced by SCIP_DECL_BRANCHEXECLP().

◆ varProcessBoundChanges()

static SCIP_RETCODE varProcessBoundChanges ( SCIP scip,
SCIP_BRANCHRULEDATA branchruledata,
SCIP_VAR var 
)
static

process a variable from the queue of changed variables

Parameters
scipSCIP data structure
branchruledatabranchrule data
varthe variable whose bound changes need to be processed

Definition at line 912 of file branch_distribution.c.

References branchruledataEnsureArraySize(), branchruledataUpdateCurrentBounds(), 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(), and SQUARED.

Referenced by SCIP_DECL_BRANCHEXECLP().

◆ SCIP_DECL_EVENTFREE()

static SCIP_DECL_EVENTFREE ( eventFreeDistribution  )
static

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

Definition at line 1039 of file branch_distribution.c.

References NULL, SCIP_OKAY, SCIPeventhdlrGetData(), SCIPeventhdlrSetData(), and SCIPfreeBlockMemory.

◆ SCIP_DECL_BRANCHCOPY()

static SCIP_DECL_BRANCHCOPY ( branchCopyDistribution  )
static

copy method for branchrule plugins (called when SCIP copies plugins)

Definition at line 1058 of file branch_distribution.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPincludeBranchruleDistribution().

◆ SCIP_DECL_BRANCHEXITSOL()

static SCIP_DECL_BRANCHEXITSOL ( branchExitsolDistribution  )
static

solving process deinitialization method of branching rule (called before branch and bound process data is freed)

Definition at line 1069 of file branch_distribution.c.

References BRANCHRULE_NAME, branchruledataFreeArrays(), EVENT_DISTRIBUTION, NULL, SCIP_CALL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPdropVarEvent(), SCIPgetNVars(), and SCIPgetVars().

◆ SCIP_DECL_BRANCHFREE()

static SCIP_DECL_BRANCHFREE ( branchFreeDistribution  )
static

destructor of branching rule to free user data (called when SCIP is exiting)

Definition at line 1104 of file branch_distribution.c.

References BRANCHRULE_NAME, branchruledataFreeArrays(), NULL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPbranchruleSetData(), and SCIPfreeBlockMemory.

◆ SCIP_DECL_BRANCHEXECLP()

◆ 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 1302 of file branch_distribution.c.

References branchruledataAddBoundChangeVar(), NULL, SCIP_OKAY, SCIPeventGetVar(), and SCIPeventhdlrGetData().