# SCIP

Solving Constraint Integer Programs

treemodel.c File Reference

## Detailed Description

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

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)

## ◆ LAGUERRE_THRESHOLD

 #define LAGUERRE_THRESHOLD   100

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

Definition at line 69 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 72 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 73 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 76 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 79 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 82 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 85 of file treemodel.c.

## ◆ DEFAULT_MAXFPITER

 #define DEFAULT_MAXFPITER   24

maximum number of fixed-point iterations when computing the ratio

Definition at line 88 of file treemodel.c.

## ◆ DEFAULT_MAXSVTSHEIGHT

 #define DEFAULT_MAXSVTSHEIGHT   100

maximum height to compute the SVTS score exactly before approximating

Definition at line 89 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 90 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 93 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 96 of file treemodel.c.

## ◆ SCIP_RATIO

 typedef struct SCIP_Ratio SCIP_RATIO

Definition at line 141 of file treemodel.c.

## ◆ 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 145 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
 scip SCIP data structure a the first set of values b the second set of values size the size of array a (and b) ndominated returns the number of dominated elements dominated returns the array of booleans that determine if an element is dominated

Definition at line 171 of file treemodel.c.

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
 scip SCIP data structure branchratio The variable's ratio to compare against leftgain the left gain of a variable rightgain the right gain of a variable

Definition at line 305 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
 scip SCIP data structure treemodel Treemodel parameter data structure var the candidate branching variable leftgain the left gain of the variable rightgain the right gain of the variable branchratio storage for the computed ratio

Definition at line 331 of file treemodel.c.

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
 scip SCIP data structure treemodel Treemodel parameter data structure branchcands branching candidate storage mingains minimum gain of rounding downwards or upwards maxgains maximum gain of rounding downwards or upwards filterdominated whether dominated variables have been filtered dominated whether each variable is dominated or not nbranchcands the number of branching candidates bestcand the best branching candidate found before the call, and the best candidate after the call (possibly the same)

Definition at line 455 of file treemodel.c.

## ◆ 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
 scip SCIP data structure treemodel Treemodel parameter data structure var the candidate branching variable absgap the absolute gap to close (typically the local gap at the current node) mingain prediction of smaller objective gain of downwards/upwards maxgain prediction of larger objective gain of downwards/upwards

Definition at line 498 of file treemodel.c.

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
 scip SCIP data structure treemodel Treemodel parameter data structure branchcands branching candidate storage mingains minimum gain of rounding downwards or upwards maxgains maximum gain of rounding downwards or upwards tiebreakerscore scores to use for tie breaking localabsgap The dual gap at the current node filterdominated whether dominated variables have been filtered dominated whether each variable is dominated or not nbranchcands the number of branching candidates ndominated the number of dominated candidates bestcand the best branching candidate found before the call, and the best candidate after the call (possibly the same)

Definition at line 584 of file treemodel.c.

Referenced by computeSVTS(), and SCIPtreemodelSelectCandidate().

## ◆ integerpow()

 static SCIP_Real integerpow ( SCIP_Real a, int b )
static

computes a^b for integer b

Parameters
 a the base b the integer exponent

Definition at line 675 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
 scip SCIP data structure treemodel Treemodel parameter data structure var the candidate branching variable absgap the absolute gap to close (typically the local at the current node) leftgain The minimum gain from branching on this variable rightgain The maximum gain from branching on this variable

Definition at line 694 of file treemodel.c.

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
 scip SCIP data structure treemodel Treemodel parameter data structure branchcands branching candidate storage mingains minimum gain of rounding downwards or upwards maxgains maximum gain of rounding downwards or upwards tiebreakerscore scores to use for tie breaking localabsgap The dual gap at the current node filterdominated whether dominated variables have been filtered dominated whether each variable is dominated or not nbranchcands the number of branching candidates ndominated the number of dominated candidates bestcand the best branching candidate found before the call, and the best candidate after the call (possibly the same)

Definition at line 743 of file treemodel.c.

Referenced by computeSampleTreesize(), and SCIPtreemodelSelectCandidate().

## ◆ SCIPtreemodelInit()

 SCIP_RETCODE SCIPtreemodelInit ( SCIP * scip, SCIP_TREEMODEL ** treemodel )

initialises the Treemodel parameter data structure

Parameters
 scip SCIP data structure treemodel Treemodel parameter data structure

Definition at line 834 of file treemodel.c.

Referenced by selectCandidateUsingSampling().

## ◆ SCIPtreemodelFree()

 SCIP_RETCODE SCIPtreemodelFree ( SCIP * scip, SCIP_TREEMODEL ** treemodel )

frees the Treemodel parameter data structure

Parameters
 scip SCIP data structure treemodel Treemodel parameter data structure

Definition at line 892 of file treemodel.c.

## ◆ SCIPtreemodelIsEnabled()

 SCIP_Bool SCIPtreemodelIsEnabled ( SCIP * scip, SCIP_TREEMODEL * treemodel )

returns TRUE if the Treemodel branching rules are enabled

Parameters
 scip SCIP data structure treemodel Treemodel parameter data structure

Definition at line 908 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
 scip SCIP data structure treemodel Treemodel parameter data structure branchcands branching candidate storage mingains minimum gain of rounding downwards or upwards maxgains maximum gain of rounding downwards or upwards tiebreakerscore scores to use for tie breaking nbranchcands the number of branching candidates bestcand the best branching candidate found before the call, and the best candidate after the call (possibly the same)

Definition at line 920 of file treemodel.c.

Referenced by execRelpscost().