Scippy

SCIP

Solving Constraint Integer Programs

treemodel.c File Reference

Detailed Description

Branching rules based on the Single-Variable-Branching (SVB) model.

Author
Daniel Anderson
Pierre Le Bodic

The Single-Variable-Branching (SVB) model is a simplified model of Branch & Bound trees, from which several nontrivial variable selection rules arise. The Treemodel branching rule complements SCIP's hybrid branching by suggesting improved branching variables given the current pseudocosts and the current dual gap.

Given a variable with dual bound changes (l, r) (both positive) and an absolute gap G, the SVB model describes the tree that needs to be built by branching on that same variable at every node until the value G is reached at every leaf, starting from 0 at the root node. If we do so for every variable, we can select the variable that produces the smallest tree. In the case where the gap is not known, then we can compute the growth rate of the tree, which we call the ratio. The ratio of a variable (l, r) is the factor by which the size of the tree built using (l, r) that closes a gap G must be multiplied by to close a gap G+1. This ratio is not constant for all gaps, but when G tends to infinity, it converges to a fixed value we can compute numerically using a root finding algorithm (e.g. Laguerre). The ratio is used when the gap is too large (e.g. no primal bound known) or to help approximate the size of the SVB tree for that variable.

See the following publication for more detail:

Pierre Le Bodic and George Nemhauser
An abstract model for branching and its application to mixed integer programming
Mathematical Programming, 2017

Definition in file treemodel.c.

#include "scip/treemodel.h"
#include "scip/history.h"
#include "scip/var.h"
#include <limits.h>

Go to the source code of this file.

Data Structures

struct  SCIP_Treemodel
 
struct  SCIP_Ratio
 

Macros

#define LAGUERRE_THRESHOLD   100
 
#define DEFAULT_ENABLE   FALSE
 
#define DEFAULT_HIGHRULE   'r'
 
#define DEFAULT_LOWRULE   'r'
 
#define DEFAULT_HEIGHT   10
 
#define DEFAULT_FILTERHIGH   'a'
 
#define DEFAULT_FILTERLOW   'a'
 
#define DEFAULT_MAXFPITER   24
 
#define DEFAULT_MAXSVTSHEIGHT   100
 
#define DEFAULT_FALLBACKINF   'r'
 
#define DEFAULT_FALLBACKNOPRIM   'r'
 
#define DEFAULT_SMALLPSCOST   0.1
 

Typedefs

typedef struct SCIP_Ratio SCIP_RATIO
 

Functions

static SCIP_DECL_SORTINDCOMP (sciprealcomp)
 
static SCIP_RETCODE findNonDominatedVars (SCIP *scip, SCIP_Real *a, SCIP_Real *b, int size, int *ndominated, SCIP_Bool *dominated)
 
static SCIP_Bool hasBetterRatio (SCIP *scip, SCIP_RATIO *branchratio, SCIP_Real leftgain, SCIP_Real rightgain)
 
static void computeVarRatio (SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR *var, SCIP_Real leftgain, SCIP_Real rightgain, SCIP_RATIO *branchratio)
 
static SCIP_RETCODE selectCandidateUsingRatio (SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR **branchcands, SCIP_Real *mingains, SCIP_Real *maxgains, SCIP_Bool filterdominated, SCIP_Bool *dominated, int nbranchcands, int *bestcand)
 
static SCIP_Real computeSVTS (SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR *var, SCIP_Real absgap, SCIP_Real mingain, SCIP_Real maxgain)
 
static SCIP_RETCODE selectCandidateUsingSVTS (SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR **branchcands, SCIP_Real *mingains, SCIP_Real *maxgains, SCIP_Real *tiebreakerscore, SCIP_Real localabsgap, SCIP_Bool filterdominated, SCIP_Bool *dominated, int nbranchcands, int ndominated, int *bestcand)
 
static SCIP_Real integerpow (SCIP_Real a, int b)
 
static SCIP_Real computeSampleTreesize (SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR *var, SCIP_Real absgap, SCIP_Real leftgain, SCIP_Real rightgain)
 
static SCIP_RETCODE selectCandidateUsingSampling (SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR **branchcands, SCIP_Real *mingains, SCIP_Real *maxgains, SCIP_Real *tiebreakerscore, SCIP_Real localabsgap, SCIP_Bool filterdominated, SCIP_Bool *dominated, int nbranchcands, int ndominated, int *bestcand)
 
SCIP_RETCODE SCIPtreemodelInit (SCIP *scip, SCIP_TREEMODEL **treemodel)
 
SCIP_RETCODE SCIPtreemodelFree (SCIP *scip, SCIP_TREEMODEL **treemodel)
 
SCIP_Bool SCIPtreemodelIsEnabled (SCIP *scip, SCIP_TREEMODEL *treemodel)
 
SCIP_RETCODE SCIPtreemodelSelectCandidate (SCIP *scip, SCIP_TREEMODEL *treemodel, SCIP_VAR **branchcands, SCIP_Real *mingains, SCIP_Real *maxgains, SCIP_Real *tiebreakerscore, int nbranchcands, int *bestcand)
 

Macro Definition Documentation

◆ LAGUERRE_THRESHOLD

#define LAGUERRE_THRESHOLD   100

Maximum value of r/l at which Laguerre is the prefered FP method

Definition at line 60 of file treemodel.c.

Referenced by computeVarRatio().

◆ DEFAULT_ENABLE

#define DEFAULT_ENABLE   FALSE

should candidate branching variables be scored using the Treemodel rule?

Definition at line 63 of file treemodel.c.

◆ DEFAULT_HIGHRULE

#define DEFAULT_HIGHRULE   'r'

scoring function to use at nodes predicted to be high in the tree. ('d'efault, 's'vts, 'r'atio, 't'ree sample)

Definition at line 64 of file treemodel.c.

◆ DEFAULT_LOWRULE

#define DEFAULT_LOWRULE   'r'

scoring function to use at nodes predicted to be low in the tree ('d'efault, 's'vts, 'r'atio, 't'ree sample)

Definition at line 67 of file treemodel.c.

◆ DEFAULT_HEIGHT

#define DEFAULT_HEIGHT   10

estimated tree height at which we switch from using the low rule to the high rule

Definition at line 70 of file treemodel.c.

◆ DEFAULT_FILTERHIGH

#define DEFAULT_FILTERHIGH   'a'

should dominated candidates be filtered before using the high scoring function? ('a'uto, 't'rue, 'f'alse)

Definition at line 73 of file treemodel.c.

◆ DEFAULT_FILTERLOW

#define DEFAULT_FILTERLOW   'a'

should dominated candidates be filtered before using the low scoring function? ('a'uto, 't'rue, 'f'alse)

Definition at line 76 of file treemodel.c.

◆ DEFAULT_MAXFPITER

#define DEFAULT_MAXFPITER   24

maximum number of fixed-point iterations when computing the ratio

Definition at line 79 of file treemodel.c.

◆ DEFAULT_MAXSVTSHEIGHT

#define DEFAULT_MAXSVTSHEIGHT   100

maximum height to compute the SVTS score exactly before approximating

Definition at line 80 of file treemodel.c.

◆ DEFAULT_FALLBACKINF

#define DEFAULT_FALLBACKINF   'r'

which method should be used as a fallback if the tree size estimates are infinite? ('d'efault, 'r'atio)

Definition at line 81 of file treemodel.c.

◆ DEFAULT_FALLBACKNOPRIM

#define DEFAULT_FALLBACKNOPRIM   'r'

which method should be used as a fallback if there is no primal bound available? ('d'efault, 'r'atio)

Definition at line 84 of file treemodel.c.

◆ DEFAULT_SMALLPSCOST

#define DEFAULT_SMALLPSCOST   0.1

threshold at which pseudocosts are considered small, making hybrid scores more likely to be the deciding factor in branching

Definition at line 87 of file treemodel.c.

Typedef Documentation

◆ SCIP_RATIO

typedef struct SCIP_Ratio SCIP_RATIO

Definition at line 132 of file treemodel.c.

Function Documentation

◆ SCIP_DECL_SORTINDCOMP()

static SCIP_DECL_SORTINDCOMP ( sciprealcomp  )
static

a comparison method for the next method. It simply compares two SCIP_Real

Definition at line 136 of file treemodel.c.

◆ findNonDominatedVars()

static SCIP_RETCODE findNonDominatedVars ( SCIP scip,
SCIP_Real a,
SCIP_Real b,
int  size,
int *  ndominated,
SCIP_Bool dominated 
)
static

given a pair of arrays of real non-negative values (a,b), with a <= b, computes the pairs that belong to the pareto front (with a tolerance). In other words, we are looking for non-dominated pairs of values. One value and one array are computed after this method. The value is the number of non-dominated elements. The array is a boolean array that indicates if an element is dominated. In case of a draw, only one variable is considered as non-dominated.

Parameters
scipSCIP data structure
athe first set of values
bthe second set of values
sizethe size of array a (and b)
ndominatedreturns the number of dominated elements
dominatedreturns the array of booleans that determine if an element is dominated

Definition at line 162 of file treemodel.c.

References FALSE, hasBetterRatio(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisGT(), SCIPisLT(), SCIPsortDownInd(), and TRUE.

Referenced by SCIPtreemodelSelectCandidate().

◆ hasBetterRatio()

static SCIP_Bool hasBetterRatio ( SCIP scip,
SCIP_RATIO branchratio,
SCIP_Real  leftgain,
SCIP_Real  rightgain 
)
static

returns true iff the variable with given gains has a ratio better (i.e smaller) than the given one

Parameters
scipSCIP data structure
branchratioThe variable's ratio to compare against
leftgainthe left gain of a variable
rightgainthe right gain of a variable

Definition at line 296 of file treemodel.c.

Referenced by findNonDominatedVars(), and selectCandidateUsingRatio().

◆ computeVarRatio()

static void computeVarRatio ( SCIP scip,
SCIP_TREEMODEL treemodel,
SCIP_VAR var,
SCIP_Real  leftgain,
SCIP_Real  rightgain,
SCIP_RATIO branchratio 
)
static

computes the variable ratio corresponding to the left and right gains

Parameters
scipSCIP data structure
treemodelTreemodel parameter data structure
varthe candidate branching variable
leftgainthe left gain of the variable
rightgainthe right gain of the variable
branchratiostorage for the computed ratio

Definition at line 322 of file treemodel.c.

References a, FALSE, SCIP_Var::history, SCIP_Ratio::invleft, LAGUERRE_THRESHOLD, SCIP_Treemodel::maxfpiter, r, SCIP_Bool, SCIP_Real, SCIPhistoryGetLastBalance(), SCIPhistoryGetLastRatio(), SCIPhistoryIsRatioValid(), SCIPhistorySetRatioHistory(), SCIPisEQ(), SCIPisGE(), SCIPisSumEQ(), SCIPisZero(), selectCandidateUsingRatio(), TRUE, SCIP_Ratio::upratio, and SCIP_Ratio::valid.

Referenced by computeSampleTreesize(), computeSVTS(), and selectCandidateUsingRatio().

◆ selectCandidateUsingRatio()

static SCIP_RETCODE selectCandidateUsingRatio ( SCIP scip,
SCIP_TREEMODEL treemodel,
SCIP_VAR **  branchcands,
SCIP_Real mingains,
SCIP_Real maxgains,
SCIP_Bool  filterdominated,
SCIP_Bool dominated,
int  nbranchcands,
int *  bestcand 
)
static

use the Ratio scoring function to select a branching candidate

Parameters
scipSCIP data structure
treemodelTreemodel parameter data structure
branchcandsbranching candidate storage
mingainsminimum gain of rounding downwards or upwards
maxgainsmaximum gain of rounding downwards or upwards
filterdominatedwhether dominated variables have been filtered
dominatedwhether each variable is dominated or not
nbranchcandsthe number of branching candidates
bestcandthe best branching candidate found before the call, and the best candidate after the call (possibly the same)

Definition at line 446 of file treemodel.c.

References computeSVTS(), computeVarRatio(), hasBetterRatio(), SCIP_OKAY, SCIP_Real, and SCIP_Ratio::valid.

Referenced by computeVarRatio(), SCIPtreemodelSelectCandidate(), selectCandidateUsingSampling(), and selectCandidateUsingSVTS().

◆ computeSVTS()

static SCIP_Real computeSVTS ( SCIP scip,
SCIP_TREEMODEL treemodel,
SCIP_VAR var,
SCIP_Real  absgap,
SCIP_Real  mingain,
SCIP_Real  maxgain 
)
static

Returns the predicted treesize for the gap and given up and down gains

Parameters
scipSCIP data structure
treemodelTreemodel parameter data structure
varthe candidate branching variable
absgapthe absolute gap to close (typically the local gap at the current node)
mingainprediction of smaller objective gain of downwards/upwards
maxgainprediction of larger objective gain of downwards/upwards

Definition at line 489 of file treemodel.c.

References computeVarRatio(), SCIP_Ratio::invleft, SCIP_Treemodel::maxsvtsheight, SCIP_Real, SCIP_REAL_MAX, SCIPceil(), SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), selectCandidateUsingSVTS(), SCIP_Ratio::upratio, and SCIP_Ratio::valid.

Referenced by selectCandidateUsingRatio(), and selectCandidateUsingSVTS().

◆ selectCandidateUsingSVTS()

static SCIP_RETCODE selectCandidateUsingSVTS ( SCIP scip,
SCIP_TREEMODEL treemodel,
SCIP_VAR **  branchcands,
SCIP_Real mingains,
SCIP_Real maxgains,
SCIP_Real tiebreakerscore,
SCIP_Real  localabsgap,
SCIP_Bool  filterdominated,
SCIP_Bool dominated,
int  nbranchcands,
int  ndominated,
int *  bestcand 
)
static

use the SVTS scoring function to select a branching candidate

Parameters
scipSCIP data structure
treemodelTreemodel parameter data structure
branchcandsbranching candidate storage
mingainsminimum gain of rounding downwards or upwards
maxgainsmaximum gain of rounding downwards or upwards
tiebreakerscorescores to use for tie breaking
localabsgapThe dual gap at the current node
filterdominatedwhether dominated variables have been filtered
dominatedwhether each variable is dominated or not
nbranchcandsthe number of branching candidates
ndominatedthe number of dominated candidates
bestcandthe best branching candidate found before the call, and the best candidate after the call (possibly the same)

Definition at line 575 of file treemodel.c.

References a, b, computeSVTS(), SCIP_Treemodel::fallbackinf, SCIP_Treemodel::fallbacknoprim, integerpow(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisInfinity(), and selectCandidateUsingRatio().

Referenced by computeSVTS(), and SCIPtreemodelSelectCandidate().

◆ integerpow()

static SCIP_Real integerpow ( SCIP_Real  a,
int  b 
)
static

computes a^b for integer b

Parameters
athe base
bthe integer exponent

Definition at line 666 of file treemodel.c.

References a, computeSampleTreesize(), and SCIP_Real.

Referenced by computeSampleTreesize(), and selectCandidateUsingSVTS().

◆ computeSampleTreesize()

static SCIP_Real computeSampleTreesize ( SCIP scip,
SCIP_TREEMODEL treemodel,
SCIP_VAR var,
SCIP_Real  absgap,
SCIP_Real  leftgain,
SCIP_Real  rightgain 
)
static

returns the sampled tree size for the given lp gains and dual gap

Parameters
scipSCIP data structure
treemodelTreemodel parameter data structure
varthe candidate branching variable
absgapthe absolute gap to close (typically the local at the current node)
leftgainThe minimum gain from branching on this variable
rightgainThe maximum gain from branching on this variable

Definition at line 685 of file treemodel.c.

References computeVarRatio(), integerpow(), SCIP_Ratio::invleft, SCIP_Real, SCIP_REAL_MAX, selectCandidateUsingSampling(), SCIP_Ratio::upratio, and SCIP_Ratio::valid.

Referenced by integerpow(), and selectCandidateUsingSampling().

◆ selectCandidateUsingSampling()

static SCIP_RETCODE selectCandidateUsingSampling ( SCIP scip,
SCIP_TREEMODEL treemodel,
SCIP_VAR **  branchcands,
SCIP_Real mingains,
SCIP_Real maxgains,
SCIP_Real tiebreakerscore,
SCIP_Real  localabsgap,
SCIP_Bool  filterdominated,
SCIP_Bool dominated,
int  nbranchcands,
int  ndominated,
int *  bestcand 
)
static

use the Tree Sampling scoring function to select a branching candidate

Parameters
scipSCIP data structure
treemodelTreemodel parameter data structure
branchcandsbranching candidate storage
mingainsminimum gain of rounding downwards or upwards
maxgainsmaximum gain of rounding downwards or upwards
tiebreakerscorescores to use for tie breaking
localabsgapThe dual gap at the current node
filterdominatedwhether dominated variables have been filtered
dominatedwhether each variable is dominated or not
nbranchcandsthe number of branching candidates
ndominatedthe number of dominated candidates
bestcandthe best branching candidate found before the call, and the best candidate after the call (possibly the same)

Definition at line 734 of file treemodel.c.

References computeSampleTreesize(), SCIP_Treemodel::fallbackinf, SCIP_Treemodel::fallbacknoprim, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIPallocBlockMemory(), SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisInfinity(), SCIPtreemodelInit(), and selectCandidateUsingRatio().

Referenced by computeSampleTreesize(), and SCIPtreemodelSelectCandidate().

◆ SCIPtreemodelInit()

SCIP_RETCODE SCIPtreemodelInit ( SCIP scip,
SCIP_TREEMODEL **  treemodel 
)

initialises the Treemodel parameter data structure

Parameters
scipSCIP data structure
treemodelTreemodel parameter data structure

Definition at line 825 of file treemodel.c.

Referenced by selectCandidateUsingSampling().

◆ SCIPtreemodelFree()

SCIP_RETCODE SCIPtreemodelFree ( SCIP scip,
SCIP_TREEMODEL **  treemodel 
)

frees the Treemodel parameter data structure

Parameters
scipSCIP data structure
treemodelTreemodel parameter data structure

Definition at line 883 of file treemodel.c.

◆ SCIPtreemodelIsEnabled()

SCIP_Bool SCIPtreemodelIsEnabled ( SCIP scip,
SCIP_TREEMODEL treemodel 
)

returns TRUE if the Treemodel branching rules are enabled

Parameters
scipSCIP data structure
treemodelTreemodel parameter data structure

Definition at line 899 of file treemodel.c.

Referenced by execRelpscost().

◆ SCIPtreemodelSelectCandidate()

SCIP_RETCODE SCIPtreemodelSelectCandidate ( SCIP scip,
SCIP_TREEMODEL treemodel,
SCIP_VAR **  branchcands,
SCIP_Real mingains,
SCIP_Real maxgains,
SCIP_Real tiebreakerscore,
int  nbranchcands,
int *  bestcand 
)

apply the Treemodel branching rules to attempt to select a better branching candidate than the one selected by pseudocost branching

Parameters
scipSCIP data structure
treemodelTreemodel parameter data structure
branchcandsbranching candidate storage
mingainsminimum gain of rounding downwards or upwards
maxgainsmaximum gain of rounding downwards or upwards
tiebreakerscorescores to use for tie breaking
nbranchcandsthe number of branching candidates
bestcandthe best branching candidate found before the call, and the best candidate after the call (possibly the same)

Definition at line 911 of file treemodel.c.

References SCIP_Treemodel::enabled, SCIP_Treemodel::filterhigh, SCIP_Treemodel::filterlow, findNonDominatedVars(), SCIP_Treemodel::height, SCIP_Treemodel::highrule, SCIP_Treemodel::lowrule, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PARAMETERWRONGVAL, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetCurrentNode(), SCIPgetNodeLowerbound(), SCIPgetUpperbound(), SCIPinfinity(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), selectCandidateUsingRatio(), selectCandidateUsingSampling(), and selectCandidateUsingSVTS().

Referenced by execRelpscost().