Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

lookahead LP branching rule

Author
Christoph Schubert
Gerald Gamrath

The (multi-level) lookahead branching rule applies strong branching to every fractional value of the LP solution at the current node of the branch-and-bound tree, as well as recursivly to every temporary child problem created by this strong branching. The rule selects the candidate with the best proven dual bound.

The branching rule was motivated by the following technical report:

Wasu Glankwamdee and Jeff Linderoth
Lookahead Branching for Mixed Integer Programming
Technical Report 06T-004, Department of Industrial and Systems Engineering, Lehigh University.

For a more mathematical description and a comparison between lookahead branching and other branching rules in SCIP, we refer to

Christoph Schubert
Multi-Level Lookahead Branching
Master Thesis, Technische Universität Berlin, 2017

Definition in file branch_lookahead.c.

#include "blockmemshell/memory.h"
#include "lpi/lpi.h"
#include "scip/branch_lookahead.h"
#include "scip/cons_logicor.h"
#include "scip/pub_branch.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_tree.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cons.h"
#include "scip/scip_general.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 "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/scip_var.h"
#include <string.h>

Go to the source code of this file.

Data Structures

struct  WARMSTARTINFO
 
struct  CANDIDATE
 
struct  BRANCHINGDECISION
 
struct  BRANCHINGRESULTDATA
 
struct  LEVEL2RESULT
 
struct  LEVEL2DATA
 
struct  PERSISTENTDATA
 
struct  CONFIGURATION
 
struct  CONSTRAINTLIST
 
struct  BINARYVARLIST
 
struct  BINCONSDATA
 
struct  CANDIDATELIST
 
struct  DOMAINREDUCTIONS
 
struct  STATUS
 
struct  SCORECONTAINER
 

Macros

#define BRANCHRULE_NAME   "lookahead"
 
#define BRANCHRULE_DESC   "full strong branching over multiple levels"
 
#define BRANCHRULE_PRIORITY   0
 
#define BRANCHRULE_MAXDEPTH   -1
 
#define BRANCHRULE_MAXBOUNDDIST   1.0
 
#define DEFAULT_USEBINARYCONSTRAINTS   FALSE
 
#define DEFAULT_ADDCLIQUE   FALSE
 
#define DEFAULT_ADDBINCONSROW   0
 
#define DEFAULT_USEDOMAINREDUCTION   TRUE
 
#define DEFAULT_MERGEDOMAINREDUCTIONS   FALSE
 
#define DEFAULT_PREFERSIMPLEBOUNDS   FALSE
 
#define DEFAULT_ONLYVIOLDOMREDS   FALSE
 
#define DEFAULT_MAXNVIOLATEDCONS   1
 
#define DEFAULT_MAXNVIOLATEDBINCONS   0
 
#define DEFAULT_MAXNVIOLATEDDOMREDS   1
 
#define DEFAULT_STOREUNVIOLATEDSOL   TRUE
 
#define DEFAULT_REEVALAGE   10LL
 
#define DEFAULT_REEVALAGEFSB   10LL
 
#define DEFAULT_RECURSIONDEPTH   2
 
#define DEFAULT_ADDNONVIOCONS   FALSE
 
#define DEFAULT_PROPAGATE   TRUE
 
#define DEFAULT_USELEVEL2DATA   TRUE
 
#define DEFAULT_APPLYCHILDBOUNDS   FALSE
 
#define DEFAULT_ENFORCEMAXDOMREDS   FALSE
 
#define DEFAULT_UPDATEBRANCHINGRESULTS   FALSE
 
#define DEFAULT_MAXPROPROUNDS   0
 
#define DEFAULT_ABBREVIATED   TRUE
 
#define DEFAULT_MAXNCANDS   4
 
#define DEFAULT_MAXNDEEPERCANDS   2
 
#define DEFAULT_REUSEBASIS   TRUE
 
#define DEFAULT_ABBREVPSEUDO   FALSE
 
#define DEFAULT_LEVEL2AVGSCORE   FALSE
 
#define DEFAULT_LEVEL2ZEROSCORE   FALSE
 
#define DEFAULT_SCORINGFUNCTION   'a'
 
#define DEFAULT_DEEPERSCORINGFUNCTION   'x'
 
#define DEFAULT_SCORINGSCORINGFUNCTION   'd'
 
#define DEFAULT_MINWEIGHT   0.8
 
#define DEFAULT_WORSEFACTOR   -1.0
 
#define DEFAULT_FILTERBYMAXGAIN   FALSE
 
#define LABdebugMessage(scip, lvl, ...)
 
#define level2resultPrint(scip, result)
 

Functions

static SCIP_RETCODE warmStartInfoCreate (SCIP *scip, WARMSTARTINFO **warmstartinfo)
 
static SCIP_Bool warmStartInfoIsAvailable (WARMSTARTINFO *warmstartinfo)
 
static SCIP_RETCODE warmStartInfoFree (SCIP *scip, WARMSTARTINFO **warmstartinfo)
 
static SCIP_RETCODE candidateCreate (SCIP *scip, CANDIDATE **candidate)
 
static SCIP_RETCODE candidateFreeWarmStartInfo (SCIP *scip, CANDIDATE *candidate)
 
static SCIP_RETCODE candidateFree (SCIP *scip, CANDIDATE **candidate)
 
static SCIP_RETCODE candidateStoreWarmStartInfo (SCIP *scip, CANDIDATE *candidate, SCIP_Bool down)
 
static SCIP_Bool candidateHasWarmStartInfo (CANDIDATE *candidate, SCIP_Bool down)
 
static SCIP_RETCODE candidateLoadWarmStartInfo (SCIP *scip, CANDIDATE *candidate, SCIP_Bool down)
 
static void branchingDecisionInit (SCIP *scip, BRANCHINGDECISION *decision)
 
static SCIP_RETCODE branchingDecisionCreate (SCIP *scip, BRANCHINGDECISION **decision)
 
static void branchingDecisionCopy (BRANCHINGDECISION *sourcedecision, BRANCHINGDECISION *targetdecision)
 
static SCIP_Bool branchingDecisionIsValid (BRANCHINGDECISION *decision)
 
static SCIP_RETCODE branchingDecisionEnsureBoundArraysSize (SCIP *scip, BRANCHINGDECISION *decision, int nvars)
 
static void branchingDecisionFree (SCIP *scip, BRANCHINGDECISION **decision)
 
static SCIP_RETCODE branchingResultDataCreate (SCIP *scip, BRANCHINGRESULTDATA **resultdata)
 
static void branchingResultDataInit (SCIP *scip, BRANCHINGRESULTDATA *resultdata)
 
static void branchingResultDataCopy (BRANCHINGRESULTDATA *sourcedata, BRANCHINGRESULTDATA *targetdata)
 
static void branchingResultDataFree (SCIP *scip, BRANCHINGRESULTDATA **resultdata)
 
static SCIP_RETCODE level2resultCreateFromData (SCIP *scip, LEVEL2DATA *data, LEVEL2RESULT **result)
 
static void level2resultFree (SCIP *scip, LEVEL2RESULT **result)
 
static SCIP_Bool level2resultEqual (LEVEL2RESULT *result1, LEVEL2RESULT *result2)
 
static SCIP_RETCODE level2dataCreate (SCIP *scip, LEVEL2DATA **data)
 
static void level2dataFree (SCIP *scip, LEVEL2DATA **data)
 
static SCIP_RETCODE level2dataEnsureSize (SCIP *scip, LEVEL2DATA *data)
 
static SCIP_RETCODE level2dataGetResult (SCIP *scip, LEVEL2DATA *data, LEVEL2RESULT **result)
 
static SCIP_RETCODE level2dataStoreResult (SCIP *scip, LEVEL2DATA *data, SCIP_Real lpobjval, SCIP_Bool cutoff, SCIP_Bool valid, SCIP_Bool *duplicate)
 
static SCIP_RETCODE constraintListCreate (SCIP *scip, CONSTRAINTLIST **conslist, int startsize)
 
static SCIP_RETCODE constraintListAppend (SCIP *scip, CONSTRAINTLIST *list, SCIP_VAR **consvars, int nconsvars, SCIP_Bool violated)
 
static void constraintListFree (SCIP *scip, CONSTRAINTLIST **conslist)
 
static SCIP_RETCODE binaryVarListCreate (SCIP *scip, BINARYVARLIST **list, int startsize)
 
static void binaryVarListAppend (SCIP *scip, BINARYVARLIST *list, SCIP_VAR *vartoadd)
 
static void binaryVarListDrop (BINARYVARLIST *list)
 
static void binaryVarListFree (SCIP *scip, BINARYVARLIST **list)
 
static SCIP_RETCODE binConsDataCreate (SCIP *scip, BINCONSDATA **consdata, int maxdepth, int nstartcons)
 
static void binConsDataFree (SCIP *scip, BINCONSDATA **consdata)
 
static SCIP_RETCODE candidateListCreate (SCIP *scip, CANDIDATELIST **candidatelist, int ncandidates)
 
static SCIP_RETCODE candidateListGetAllFractionalCandidates (SCIP *scip, CANDIDATELIST **candidatelist)
 
static SCIP_RETCODE candidateListFree (SCIP *scip, CANDIDATELIST **candidatelist)
 
static SCIP_RETCODE candidateListKeep (SCIP *scip, CANDIDATELIST *candidatelist, int nindices)
 
static SCIP_RETCODE domainReductionsCreate (SCIP *scip, DOMAINREDUCTIONS **domreds)
 
static void domainReductionsFree (SCIP *scip, DOMAINREDUCTIONS **domreds)
 
static SCIP_RETCODE statusCreate (SCIP *scip, STATUS **status)
 
static void statusFree (SCIP *scip, STATUS **status)
 
static void scoreContainterResetBestSortedCands (SCORECONTAINER *scorecontainer)
 
static SCIP_RETCODE scoreContainerCreate (SCIP *scip, SCORECONTAINER **scorecontainer, CONFIGURATION *config)
 
static int findInsertionPoint (SCIP *scip, SCORECONTAINER *scorecontainer, SCIP_Real scoretoinsert, CANDIDATE **candidates, int ncandidates)
 
static CANDIDATEscoreContainerUpdateSortOrder (SCORECONTAINER *scorecontainer, CANDIDATE *candidate, int insertpoint)
 
static SCIP_RETCODE scoreContainerSetScore (SCIP *scip, SCORECONTAINER *scorecontainer, CANDIDATE *cand, SCIP_Real score, SCIP_Real downgain, SCIP_Real upgain)
 
static SCIP_RETCODE scoreContainerFree (SCIP *scip, SCORECONTAINER **scorecontainer)
 
static SCIP_RETCODE selectVarRecursive (SCIP *scip, STATUS *status, PERSISTENTDATA *persistent, CONFIGURATION *config, SCIP_SOL *baselpsol, DOMAINREDUCTIONS *domainreductions, BINCONSDATA *binconsdata, CANDIDATELIST *candidatelist, BRANCHINGDECISION *decision, SCORECONTAINER *scorecontainer, LEVEL2DATA *level2data, int recursiondepth, SCIP_Real lpobjval, SCIP_Real baselpobjval, SCIP_Longint *niterations, int *ndeepestcutoffs, SCIP_Real *bestgain, SCIP_Real *totalgains, int *ntotalgains, int *ndeepestnodes)
 
static void addLowerBound (SCIP *scip, SCIP_VAR *var, SCIP_Real lowerbound, SCIP_SOL *baselpsol, SCIP_Bool simplechange, DOMAINREDUCTIONS *domainreductions)
 
static void addUpperBound (SCIP *scip, SCIP_VAR *var, SCIP_Real upperbound, SCIP_SOL *baselpsol, SCIP_Bool simplechange, DOMAINREDUCTIONS *domainreductions)
 
static void applySingleDeeperDomainReductions (SCIP *scip, SCIP_SOL *baselpsol, int maxstoredomreds, DOMAINREDUCTIONS *targetdomreds, DOMAINREDUCTIONS *domreds)
 
static void applyDeeperDomainReductions (SCIP *scip, SCIP_SOL *baselpsol, int maxstoredomreds, DOMAINREDUCTIONS *targetdomreds, DOMAINREDUCTIONS *downdomreds, DOMAINREDUCTIONS *updomreds)
 
static SCIP_RETCODE applyDomainReductions (SCIP *scip, CONFIGURATION *config, SCIP_SOL *baselpsol, DOMAINREDUCTIONS *domreds, SCIP_Bool *domredcutoff, SCIP_Bool *domred)
 
static SCIP_RETCODE copyCurrentSolution (SCIP *scip, SCIP_SOL **lpsol)
 
static SCIP_RETCODE branchOnVar (SCIP *scip, CONFIGURATION *config, BRANCHINGDECISION *decision)
 
static SCIP_RETCODE getNIterationsLastLP (SCIP *scip, SCIP_Longint *iterations)
 
static SCIP_RETCODE executeBranching (SCIP *scip, CONFIGURATION *config, SCIP_Bool downbranching, CANDIDATE *candidate, BRANCHINGRESULTDATA *resultdata, SCIP_SOL *baselpsol, DOMAINREDUCTIONS *domreds, STATUS *status)
 
static SCIP_RETCODE createBinaryConstraint (SCIP *scip, CONFIGURATION *config, SCIP_CONS **constraint, char *constraintname, SCIP_VAR **consvars, int nconsvars)
 
static void createBinaryConstraintName (SCIP_VAR **binaryvars, int nbinaryvars, char *constraintname)
 
static SCIP_RETCODE addBinaryConstraint (SCIP *scip, CONFIGURATION *config, BINCONSDATA *binconsdata, SCIP_SOL *baselpsol)
 
static SCIP_RETCODE applyBinaryConstraints (SCIP *scip, SCIP_NODE *basenode, CONSTRAINTLIST *conslist, CONFIGURATION *config, SCIP_Bool *consadded, SCIP_Bool *cutoff, SCIP_Bool *boundchange)
 
static SCIP_Bool areBoundsChanged (SCIP *scip, SCIP_VAR *var, SCIP_Real lowerbound, SCIP_Real upperbound)
 
static SCIP_Bool isBranchFurther (STATUS *status, SCIP_Bool checkdomreds)
 
static SCIP_Bool isBranchFurtherLoopDecrement (STATUS *status, int *loopcounter)
 
static SCIP_Bool isUseOldBranching (SCIP *scip, PERSISTENTDATA *persistent, CONFIGURATION *config, SCIP_VAR *branchvar)
 
static SCIP_RETCODE getOldBranching (SCIP *scip, PERSISTENTDATA *persistent, CONFIGURATION *config, SCIP_VAR *branchvar, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult, SCIP_Real *oldlpobjval)
 
static SCIP_RETCODE updateOldBranching (SCIP *scip, PERSISTENTDATA *persistent, CONFIGURATION *config, SCIP_VAR *branchvar, SCIP_Real branchval, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult, SCIP_Real lpobjval)
 
static SCIP_RETCODE getFSBResult (SCIP *scip, STATUS *status, PERSISTENTDATA *persistent, CONFIGURATION *config, SCIP_SOL *baselpsol, DOMAINREDUCTIONS *domainreductions, BINCONSDATA *binconsdata, CANDIDATELIST *candidatelist, BRANCHINGDECISION *decision, SCORECONTAINER *scorecontainer, LEVEL2DATA *level2data, SCIP_Real lpobjval)
 
static SCIP_Real calculateScoreFromResult (SCIP *scip, SCIP_VAR *branchvar, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult, SCIP_Real lpobjval)
 
static SCIP_Real calculateScoreFromResult2 (SCIP *scip, SCIP_VAR *branchvar, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult, SCIP_Real lpobjval)
 
static SCIP_Real calculateScoreFromDeeperscore (SCIP *scip, SCIP_VAR *branchvar, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult)
 
static SCIP_Real calculateScoreFromDeeperscoreAndCutoffs (SCIP *scip, SCIP_VAR *branchvar, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult)
 
static SCIP_Real calculateWeightedGain (SCIP *scip, CONFIGURATION *config, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult, SCIP_Real lpobjval)
 
static SCIP_Real calculateScaledCutoffScore (BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult)
 
static SCIP_Real calculateWeightedCutoffScore (CONFIGURATION *config, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult)
 
static SCIP_Real calculateCutoffScore (SCIP *scip, SCIP_VAR *branchvar, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult, SCIP_Real lpobjval)
 
static SCIP_Real calculateRelCutoffScore (SCIP *scip, SCIP_VAR *branchvar, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult, SCIP_Real lpobjval)
 
static SCIP_Real calculateScore (SCIP *scip, CONFIGURATION *config, SCIP_VAR *branchvar, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult, SCIP_Real lpobjval, SCIP_Real baselpobjval)
 
static SCIP_Real calculateScoreFromPseudocosts (SCIP *scip, CANDIDATE *lpcand)
 
static void sortFirstCandidatesByScore (SCIP *scip, CANDIDATELIST *candidatelist, SCORECONTAINER *scorecontainer, int nbestcandidates)
 
static SCIP_Bool isCandidateReliable (SCIP *scip, SCIP_VAR *branchvar)
 
static SCIP_Bool isCurrentNodeCutoff (SCIP *scip)
 
static SCIP_RETCODE ensureScoresPresent (SCIP *scip, STATUS *status, PERSISTENTDATA *persistent, CONFIGURATION *config, SCIP_SOL *baselpsol, DOMAINREDUCTIONS *domainreductions, BINCONSDATA *binconsdata, CANDIDATELIST *allcandidates, BRANCHINGDECISION *decision, SCORECONTAINER *scorecontainer, LEVEL2DATA *level2data, SCIP_Real lpobjval)
 
static SCIP_RETCODE filterCandidates (SCIP *scip, STATUS *status, PERSISTENTDATA *persistent, CONFIGURATION *config, SCIP_SOL *baselpsol, DOMAINREDUCTIONS *domainreductions, BINCONSDATA *binconsdata, CANDIDATELIST *candidatelist, BRANCHINGDECISION *decision, SCORECONTAINER *scorecontainer, LEVEL2DATA *level2data, SCIP_Real lpobjval)
 
static SCIP_RETCODE executeBranchingRecursive (SCIP *scip, STATUS *status, CONFIGURATION *config, SCIP_SOL *baselpsol, CANDIDATE *candidate, SCIP_Real localbaselpsolval, SCIP_Real baselpobjval, int recursiondepth, DOMAINREDUCTIONS *domainreductions, BINCONSDATA *binconsdata, LEVEL2DATA *level2data, BRANCHINGRESULTDATA *branchingresult, SCORECONTAINER *scorecontainer, SCIP_Bool downbranching)
 
static SCIP_Bool isStoreDecision (CONFIGURATION *config, BINCONSDATA *binconsdata, DOMAINREDUCTIONS *domainreductions)
 
static SCIP_RETCODE selectVarStart (SCIP *scip, CONFIGURATION *config, PERSISTENTDATA *persistent, STATUS *status, BRANCHINGDECISION *decision, SCORECONTAINER *scorecontainer, CANDIDATELIST *candidatelist)
 
static SCIP_Bool isUsePreviousResult (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
 
static SCIP_RETCODE usePreviousResult (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata, SCIP_RESULT *result)
 
static SCIP_RETCODE freePersistent (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
 
static SCIP_RETCODE initBranchruleData (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
 
static SCIP_DECL_BRANCHCOPY (branchCopyLookahead)
 
static SCIP_DECL_BRANCHFREE (branchFreeLookahead)
 
static SCIP_DECL_BRANCHINIT (branchInitLookahead)
 
static SCIP_DECL_BRANCHEXIT (branchExitLookahead)
 
static SCIP_DECL_BRANCHEXITSOL (branchExitSolLookahead)
 
static SCIP_DECL_BRANCHEXECLP (branchExeclpLookahead)
 
SCIP_RETCODE SCIPincludeBranchruleLookahead (SCIP *scip)
 

Macro Definition Documentation

◆ BRANCHRULE_NAME

#define BRANCHRULE_NAME   "lookahead"

Definition at line 84 of file branch_lookahead.c.

Referenced by initBranchruleData(), and SCIP_DECL_BRANCHEXITSOL().

◆ BRANCHRULE_DESC

#define BRANCHRULE_DESC   "full strong branching over multiple levels"

Definition at line 85 of file branch_lookahead.c.

◆ BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY   0

Definition at line 86 of file branch_lookahead.c.

◆ BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 87 of file branch_lookahead.c.

◆ BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 88 of file branch_lookahead.c.

◆ DEFAULT_USEBINARYCONSTRAINTS

#define DEFAULT_USEBINARYCONSTRAINTS   FALSE

should binary constraints be collected and applied?

Definition at line 90 of file branch_lookahead.c.

◆ DEFAULT_ADDCLIQUE

#define DEFAULT_ADDCLIQUE   FALSE

add binary constraints with two variables found at the root node also as a clique?

Definition at line 91 of file branch_lookahead.c.

◆ DEFAULT_ADDBINCONSROW

#define DEFAULT_ADDBINCONSROW   0

should binary constraints be added as rows to the base LP? (0: no, 1: separate, 2: as initial rows)

Definition at line 92 of file branch_lookahead.c.

◆ DEFAULT_USEDOMAINREDUCTION

#define DEFAULT_USEDOMAINREDUCTION   TRUE

Should domain reductions be collected and applied?

Definition at line 95 of file branch_lookahead.c.

◆ DEFAULT_MERGEDOMAINREDUCTIONS

#define DEFAULT_MERGEDOMAINREDUCTIONS   FALSE

should domain reductions of feasible siblings should be merged?

Definition at line 96 of file branch_lookahead.c.

◆ DEFAULT_PREFERSIMPLEBOUNDS

#define DEFAULT_PREFERSIMPLEBOUNDS   FALSE

should domain reductions only be applied if there are simple bound changes?

Definition at line 97 of file branch_lookahead.c.

◆ DEFAULT_ONLYVIOLDOMREDS

#define DEFAULT_ONLYVIOLDOMREDS   FALSE

Should only domain reductions that violate the LP solution be applied?

Definition at line 98 of file branch_lookahead.c.

◆ DEFAULT_MAXNVIOLATEDCONS

#define DEFAULT_MAXNVIOLATEDCONS   1

How many constraints that are violated by the base lp solution should be gathered until the rule is stopped and they are added?

Definition at line 99 of file branch_lookahead.c.

◆ DEFAULT_MAXNVIOLATEDBINCONS

#define DEFAULT_MAXNVIOLATEDBINCONS   0

How many binary constraints that are violated by the base lp solution should be gathered until the rule is stopped and they are added?

Definition at line 102 of file branch_lookahead.c.

◆ DEFAULT_MAXNVIOLATEDDOMREDS

#define DEFAULT_MAXNVIOLATEDDOMREDS   1

How many domain reductions that are violated by the base lp solution should be gathered until the rule is stopped and they are added?

Definition at line 107 of file branch_lookahead.c.

◆ DEFAULT_STOREUNVIOLATEDSOL

#define DEFAULT_STOREUNVIOLATEDSOL   TRUE

If only non violating constraints are added, should the branching decision be stored till the next call?

Definition at line 110 of file branch_lookahead.c.

◆ DEFAULT_REEVALAGE

#define DEFAULT_REEVALAGE   10LL

Max number of LPs solved after which a previous prob branching result is recalculated.

Definition at line 113 of file branch_lookahead.c.

◆ DEFAULT_REEVALAGEFSB

#define DEFAULT_REEVALAGEFSB   10LL

Max number of LPs solved after which a previous FSB scoring result is recalculated.

Definition at line 116 of file branch_lookahead.c.

◆ DEFAULT_RECURSIONDEPTH

#define DEFAULT_RECURSIONDEPTH   2

The max depth of LAB.

Definition at line 119 of file branch_lookahead.c.

◆ DEFAULT_ADDNONVIOCONS

#define DEFAULT_ADDNONVIOCONS   FALSE

Should binary constraints, that are not violated by the base LP, be collected and added?

Definition at line 120 of file branch_lookahead.c.

◆ DEFAULT_PROPAGATE

#define DEFAULT_PROPAGATE   TRUE

Should domain propagation be executed before each temporary node is solved?

Definition at line 123 of file branch_lookahead.c.

◆ DEFAULT_USELEVEL2DATA

#define DEFAULT_USELEVEL2DATA   TRUE

should branching data generated at depth level 2 be stored for re-using it?

Definition at line 126 of file branch_lookahead.c.

◆ DEFAULT_APPLYCHILDBOUNDS

#define DEFAULT_APPLYCHILDBOUNDS   FALSE

should bounds known for child nodes be applied?

Definition at line 127 of file branch_lookahead.c.

◆ DEFAULT_ENFORCEMAXDOMREDS

#define DEFAULT_ENFORCEMAXDOMREDS   FALSE

should the maximum number of domain reductions maxnviolateddomreds be enforced?

Definition at line 128 of file branch_lookahead.c.

◆ DEFAULT_UPDATEBRANCHINGRESULTS

#define DEFAULT_UPDATEBRANCHINGRESULTS   FALSE

should branching results (and scores) be updated w.r.t. proven dual bounds?

Definition at line 129 of file branch_lookahead.c.

◆ DEFAULT_MAXPROPROUNDS

#define DEFAULT_MAXPROPROUNDS   0

maximum number of propagation rounds to perform at temporary nodes (-1: unlimited, 0: SCIP default)

Definition at line 130 of file branch_lookahead.c.

◆ DEFAULT_ABBREVIATED

#define DEFAULT_ABBREVIATED   TRUE

Toggles the abbreviated LAB.

Definition at line 133 of file branch_lookahead.c.

◆ DEFAULT_MAXNCANDS

#define DEFAULT_MAXNCANDS   4

If abbreviated: The max number of candidates to consider at the base node

Definition at line 134 of file branch_lookahead.c.

◆ DEFAULT_MAXNDEEPERCANDS

#define DEFAULT_MAXNDEEPERCANDS   2

If abbreviated: The max number of candidates to consider per deeper node (0: same as base node)

Definition at line 135 of file branch_lookahead.c.

◆ DEFAULT_REUSEBASIS

#define DEFAULT_REUSEBASIS   TRUE

If abbreviated: Should the information gathered to obtain the best candidates be reused?

Definition at line 138 of file branch_lookahead.c.

◆ DEFAULT_ABBREVPSEUDO

#define DEFAULT_ABBREVPSEUDO   FALSE

If abbreviated: Use pseudo costs to estimate the score of a candidate.

Definition at line 141 of file branch_lookahead.c.

◆ DEFAULT_LEVEL2AVGSCORE

#define DEFAULT_LEVEL2AVGSCORE   FALSE

should the average score be used for uninitialized scores in level 2?

Definition at line 144 of file branch_lookahead.c.

◆ DEFAULT_LEVEL2ZEROSCORE

#define DEFAULT_LEVEL2ZEROSCORE   FALSE

should uninitialized scores be set to 0?

Definition at line 145 of file branch_lookahead.c.

◆ DEFAULT_SCORINGFUNCTION

#define DEFAULT_SCORINGFUNCTION   'a'

scoring function to be used at the base level

Definition at line 146 of file branch_lookahead.c.

◆ DEFAULT_DEEPERSCORINGFUNCTION

#define DEFAULT_DEEPERSCORINGFUNCTION   'x'

scoring function to be used at deeper levels

Definition at line 147 of file branch_lookahead.c.

◆ DEFAULT_SCORINGSCORINGFUNCTION

#define DEFAULT_SCORINGSCORINGFUNCTION   'd'

scoring function to be used for FSB scoring

Definition at line 148 of file branch_lookahead.c.

◆ DEFAULT_MINWEIGHT

#define DEFAULT_MINWEIGHT   0.8

default value for the weight of the minimum in the convex combination of two child gains (taken from the paper)

Definition at line 149 of file branch_lookahead.c.

◆ DEFAULT_WORSEFACTOR

#define DEFAULT_WORSEFACTOR   -1.0

if the FSB score is of a candidate is worse than the best by this factor, skip this candidate (-1: disable)

Definition at line 152 of file branch_lookahead.c.

◆ DEFAULT_FILTERBYMAXGAIN

#define DEFAULT_FILTERBYMAXGAIN   FALSE

should lookahead branching only be applied if the max gain in level 1 is not uniquely that of the best candidate?

Definition at line 153 of file branch_lookahead.c.

◆ LABdebugMessage

◆ level2resultPrint

#define level2resultPrint (   scip,
  result 
)

Definition at line 782 of file branch_lookahead.c.

Referenced by level2dataStoreResult(), and level2resultCreateFromData().

Function Documentation

◆ warmStartInfoCreate()

static SCIP_RETCODE warmStartInfoCreate ( SCIP scip,
WARMSTARTINFO **  warmstartinfo 
)
static

Allocates the warm start information on the buffer and initializes it with default values.

Parameters
scipSCIP data structure
warmstartinfothe warmstartinfo to allocate and initialize

Definition at line 210 of file branch_lookahead.c.

References WARMSTARTINFO::lpistate, NULL, and warmStartInfoFree().

Referenced by candidateStoreWarmStartInfo().

◆ warmStartInfoIsAvailable()

static SCIP_Bool warmStartInfoIsAvailable ( WARMSTARTINFO warmstartinfo)
static

checks that the warm start info can be read into the lp solver.

Parameters
warmstartinfothe warm start info to check (may be NULL)

Definition at line 230 of file branch_lookahead.c.

Referenced by candidateStoreWarmStartInfo().

◆ warmStartInfoFree()

static SCIP_RETCODE warmStartInfoFree ( SCIP scip,
WARMSTARTINFO **  warmstartinfo 
)
static

Frees the allocated buffer memory of the warm start info.

Parameters
scipSCIP data structure
warmstartinfothe warm start info to free

Definition at line 239 of file branch_lookahead.c.

References candidateCreate(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfreeBlockMemory, SCIPlpiFreeNorms(), and SCIPlpiFreeState().

Referenced by candidateCreate(), candidateFreeWarmStartInfo(), and warmStartInfoCreate().

◆ candidateCreate()

static SCIP_RETCODE candidateCreate ( SCIP scip,
CANDIDATE **  candidate 
)
static

Allocates the candidate on the buffer and initializes it with default values.

Parameters
scipSCIP data structure
candidatethe candidate to allocate and initialize

Definition at line 280 of file branch_lookahead.c.

References CANDIDATE::branchvar, CANDIDATE::downwarmstartinfo, LABdebugMessage, NULL, SCIP_CALL, SCIP_VERBLEVEL_FULL, SCIPvarGetName(), CANDIDATE::upwarmstartinfo, and warmStartInfoFree().

Referenced by warmStartInfoFree().

◆ candidateFreeWarmStartInfo()

static SCIP_RETCODE candidateFreeWarmStartInfo ( SCIP scip,
CANDIDATE candidate 
)
static

free the warm starting information for the given candidate

Parameters
scipSCIP data structure
candidatethe candidate to free the warm starting information for

Definition at line 299 of file branch_lookahead.c.

References candidateFree(), CANDIDATE::downwarmstartinfo, LABdebugMessage, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIPvarGetName(), and warmStartInfoFree().

◆ candidateFree()

static SCIP_RETCODE candidateFree ( SCIP scip,
CANDIDATE **  candidate 
)
static

Frees the allocated buffer memory of the candidate and clears the contained lpi memories.

Parameters
scipSCIP data structure
candidatethe candidate to free

Definition at line 326 of file branch_lookahead.c.

Referenced by candidateFreeWarmStartInfo(), candidateListFree(), and candidateListKeep().

◆ candidateStoreWarmStartInfo()

static SCIP_RETCODE candidateStoreWarmStartInfo ( SCIP scip,
CANDIDATE candidate,
SCIP_Bool  down 
)
static

Store the current lp solution in the warm start info for further usage.

Parameters
scipSCIP data structure
candidatethe branching candidate
downis the info for down branching?

Definition at line 347 of file branch_lookahead.c.

References candidateHasWarmStartInfo(), candidateLoadWarmStartInfo(), CANDIDATE::downwarmstartinfo, WARMSTARTINFO::dualfeas, WARMSTARTINFO::lpinorms, WARMSTARTINFO::lpistate, NULL, WARMSTARTINFO::primalfeas, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPlpiGetNorms(), SCIPlpiGetState(), SCIPlpiIsDualFeasible(), SCIPlpiIsPrimalFeasible(), CANDIDATE::upwarmstartinfo, warmStartInfoCreate(), and warmStartInfoIsAvailable().

Referenced by executeBranchingRecursive().

◆ candidateHasWarmStartInfo()

static SCIP_Bool candidateHasWarmStartInfo ( CANDIDATE candidate,
SCIP_Bool  down 
)
static

returns whether the candidate has stored warm starting information for the given direction

Parameters
candidatethe branching candidate
downis the info for down branching?

Definition at line 395 of file branch_lookahead.c.

References CANDIDATE::downwarmstartinfo, LABdebugMessage, NULL, and SCIP_VERBLEVEL_HIGH.

Referenced by candidateStoreWarmStartInfo().

◆ candidateLoadWarmStartInfo()

static SCIP_RETCODE candidateLoadWarmStartInfo ( SCIP scip,
CANDIDATE candidate,
SCIP_Bool  down 
)
static

loads the warm starting information of the candidate for the given direction

Parameters
scipSCIP data structure
candidatethe branching candidate
downis the info for down branching?

Definition at line 408 of file branch_lookahead.c.

Referenced by candidateStoreWarmStartInfo().

◆ branchingDecisionInit()

static void branchingDecisionInit ( SCIP scip,
BRANCHINGDECISION decision 
)
static

initialize a branching decsion with default values

Parameters
scipSCIP data structure
decisionthe decision to initialize

Definition at line 466 of file branch_lookahead.c.

Referenced by initBranchruleData().

◆ branchingDecisionCreate()

static SCIP_RETCODE branchingDecisionCreate ( SCIP scip,
BRANCHINGDECISION **  decision 
)
static

allocates a branching decision in the buffer and initializes it with default values.

Parameters
scipSCIP data structure
decisionpointer to the decision to allocate and initialize

Definition at line 493 of file branch_lookahead.c.

References BRANCHINGDECISION::branchval, BRANCHINGDECISION::branchvar, BRANCHINGDECISION::downdb, BRANCHINGDECISION::downdbvalid, NULL, BRANCHINGDECISION::proveddb, BRANCHINGDECISION::updb, and BRANCHINGDECISION::updbvalid.

Referenced by executeBranchingRecursive().

◆ branchingDecisionCopy()

static void branchingDecisionCopy ( BRANCHINGDECISION sourcedecision,
BRANCHINGDECISION targetdecision 
)
static

copies the data from the source branching decision storage to the target storage; this is used to store the most important information (i.e., the dual bounds obtained) so that it can be used in a subsequent call in case the LP solution did not change because we only added bound changes that did not forbid the current LP solution; however, we do not want to store all the domain changes for the two potential child nodes for this rare case, they will be identified when processing the child nodes anyway

Parameters
sourcedecisionthe source branching decision
targetdecisionthe target branching decision

Definition at line 516 of file branch_lookahead.c.

◆ branchingDecisionIsValid()

static SCIP_Bool branchingDecisionIsValid ( BRANCHINGDECISION decision)
static

Checks whether the given branching decision can be used to branch on.

Parameters
decisionthe branching decision to check

Definition at line 543 of file branch_lookahead.c.

References BRANCHINGDECISION::boundssize, BRANCHINGDECISION::downlowerbounds, BRANCHINGDECISION::downupperbounds, NULL, SCIP_CALL, SCIPallocBlockMemoryArray, BRANCHINGDECISION::uplowerbounds, and BRANCHINGDECISION::upupperbounds.

◆ branchingDecisionEnsureBoundArraysSize()

static SCIP_RETCODE branchingDecisionEnsureBoundArraysSize ( SCIP scip,
BRANCHINGDECISION decision,
int  nvars 
)
static
Parameters
scipSCIP data structure
decisionbranching decision
nvarsnumber of problem variables

Definition at line 555 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ branchingDecisionFree()

static void branchingDecisionFree ( SCIP scip,
BRANCHINGDECISION **  decision 
)
static

Frees the allocated memory of the branching decision.

Parameters
scipSCIP data structure
decisionpointer to the decision to be freed

Definition at line 578 of file branch_lookahead.c.

Referenced by executeBranchingRecursive().

◆ branchingResultDataCreate()

static SCIP_RETCODE branchingResultDataCreate ( SCIP scip,
BRANCHINGRESULTDATA **  resultdata 
)
static

Allocates a branching result in the buffer.

Parameters
scipSCIP data structure
resultdatapointer to the result to be allocated

Definition at line 623 of file branch_lookahead.c.

References BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::deeperscore, BRANCHINGRESULTDATA::dualbound, BRANCHINGRESULTDATA::dualboundvalid, FALSE, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::niterations, NULL, BRANCHINGRESULTDATA::objval, and SCIPinfinity().

Referenced by selectVarRecursive().

◆ branchingResultDataInit()

static void branchingResultDataInit ( SCIP scip,
BRANCHINGRESULTDATA resultdata 
)
static

Initiates the branching result with default values.

Parameters
scipSCIP data structure
resultdatapointer to the result to be initialized

Definition at line 638 of file branch_lookahead.c.

References BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::deeperscore, BRANCHINGRESULTDATA::dualbound, BRANCHINGRESULTDATA::dualboundvalid, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::niterations, NULL, and BRANCHINGRESULTDATA::objval.

Referenced by selectVarRecursive().

◆ branchingResultDataCopy()

static void branchingResultDataCopy ( BRANCHINGRESULTDATA sourcedata,
BRANCHINGRESULTDATA targetdata 
)
static

Copies the data from the source to the target.

Parameters
sourcedatathe source branching result
targetdatathe target branching result

Definition at line 661 of file branch_lookahead.c.

References NULL, SCIP_Real, and SCIPfreeBuffer.

Referenced by selectVarRecursive().

◆ branchingResultDataFree()

static void branchingResultDataFree ( SCIP scip,
BRANCHINGRESULTDATA **  resultdata 
)
static

Frees the allocated buffer memory of the branching result.

Parameters
scipSCIP data structure
resultdatapointer to the result to be freed

Definition at line 684 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ level2resultCreateFromData()

static SCIP_RETCODE level2resultCreateFromData ( SCIP scip,
LEVEL2DATA data,
LEVEL2RESULT **  result 
)
static

◆ level2resultFree()

static void level2resultFree ( SCIP scip,
LEVEL2RESULT **  result 
)
static

frees the allocated memory of the double branching result

Parameters
scipSCIP data structure
resultpointer to the result to be freed

Definition at line 787 of file branch_lookahead.c.

References LEVEL2RESULT::branchdir1, LEVEL2RESULT::branchdir2, LEVEL2RESULT::branchval1, LEVEL2RESULT::branchvar1, and LEVEL2RESULT::branchvar2.

Referenced by level2dataCreate(), level2dataGetResult(), and level2resultCreateFromData().

◆ level2resultEqual()

static SCIP_Bool level2resultEqual ( LEVEL2RESULT result1,
LEVEL2RESULT result2 
)
static

returns TRUE iff both level 2 results are equal; two branchings are equal if they branched on the same variables with the same values

Parameters
result1first level 2 result
result2second level 2 result

Definition at line 802 of file branch_lookahead.c.

References NULL, SCIP_CALL, SCIPallocBlockMemory, and SCIPinfinity().

Referenced by level2dataGetResult(), and level2dataStoreResult().

◆ level2dataCreate()

static SCIP_RETCODE level2dataCreate ( SCIP scip,
LEVEL2DATA **  data 
)
static

allocates the level2 data

Parameters
scipSCIP data structure
datapointer to the data to be allocated

Definition at line 826 of file branch_lookahead.c.

References level2resultFree(), and NULL.

◆ level2dataFree()

static void level2dataFree ( SCIP scip,
LEVEL2DATA **  data 
)
static

frees the allocated memory of the level2 data

Parameters
scipSCIP data structure
datapointer to the data to be freed

Definition at line 851 of file branch_lookahead.c.

References level2dataEnsureSize(), LEVEL2DATA::level2results, LEVEL2DATA::level2resultssize, LEVEL2DATA::nlevel2results, NULL, SCIP_CALL, SCIPcalcMemGrowSize(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPreallocBlockMemoryArray.

◆ level2dataEnsureSize()

static SCIP_RETCODE level2dataEnsureSize ( SCIP scip,
LEVEL2DATA data 
)
static

ensures that level2results can store at least one more element

Parameters
scipSCIP data structure
datalevel2 data

Definition at line 876 of file branch_lookahead.c.

References NULL.

Referenced by level2dataFree(), and level2dataStoreResult().

◆ level2dataGetResult()

static SCIP_RETCODE level2dataGetResult ( SCIP scip,
LEVEL2DATA data,
LEVEL2RESULT **  result 
)
static

get a result from the level 2 data

Parameters
scipSCIP data structure
datalevel2 data
resultpointer to store result

Definition at line 897 of file branch_lookahead.c.

References LEVEL2DATA::branchvar1, level2dataStoreResult(), level2resultCreateFromData(), level2resultEqual(), level2resultFree(), LEVEL2DATA::level2results, LEVEL2DATA::nlevel2results, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPgetVars(), and SCIPvarGetType().

Referenced by executeBranchingRecursive().

◆ level2dataStoreResult()

static SCIP_RETCODE level2dataStoreResult ( SCIP scip,
LEVEL2DATA data,
SCIP_Real  lpobjval,
SCIP_Bool  cutoff,
SCIP_Bool  valid,
SCIP_Bool duplicate 
)
static

store a new result in the level 2 data

Parameters
scipSCIP data structure
datalevel2 data
lpobjvalLP objective value
cutoffwas the LP infeasible?
validis the LP value a valid dual bound?
duplicatepointer to store whether information for the same branching decisions was already stored

Definition at line 937 of file branch_lookahead.c.

References LEVEL2DATA::branchvar1, LEVEL2RESULT::cutoff, LABdebugMessage, level2dataEnsureSize(), level2resultCreateFromData(), level2resultEqual(), level2resultPrint, LEVEL2DATA::level2results, LEVEL2DATA::level2resultssize, LEVEL2RESULT::lpobjval, LEVEL2DATA::nlevel2results, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VERBLEVEL_HIGH, SCIPgetVars(), SCIPvarGetType(), TRUE, and LEVEL2RESULT::valid.

Referenced by executeBranchingRecursive(), and level2dataGetResult().

◆ constraintListCreate()

static SCIP_RETCODE constraintListCreate ( SCIP scip,
CONSTRAINTLIST **  conslist,
int  startsize 
)
static

Allocate and initialize the list holding the constraints.

Parameters
scipSCIP data structure
conslistPointer to the list to be allocated and initialized.
startsizeThe number of entries the list initially can hold.

Definition at line 1368 of file branch_lookahead.c.

References CONSTRAINTLIST::memorysize, CONSTRAINTLIST::nelements, and NULL.

◆ constraintListAppend()

static SCIP_RETCODE constraintListAppend ( SCIP scip,
CONSTRAINTLIST list,
SCIP_VAR **  consvars,
int  nconsvars,
SCIP_Bool  violated 
)
static

Append an element to the end of the list of constraints.

Parameters
scipSCIP data structure
listlist to add the consvars to
consvarsarray of variables for the constraint to be created later
nconsvarsnumber of elements in 'consvars'
violatedindicates whether the constraint is violated by the base lp

Definition at line 1393 of file branch_lookahead.c.

References constraintListFree(), CONSTRAINTLIST::consvars, CONSTRAINTLIST::memorysize, CONSTRAINTLIST::nconsvars, CONSTRAINTLIST::nelements, NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPduplicateBlockMemoryArray, SCIPfreeBlockMemoryArray, SCIPreallocBlockMemoryArray, and CONSTRAINTLIST::violated.

◆ constraintListFree()

static void constraintListFree ( SCIP scip,
CONSTRAINTLIST **  conslist 
)
static

Free all resources of a constraint list in opposite order to the allocation.

Parameters
scipSCIP data structure
conslistPointer to the list to be freed.

Definition at line 1428 of file branch_lookahead.c.

Referenced by binConsDataCreate(), and constraintListAppend().

◆ binaryVarListCreate()

static SCIP_RETCODE binaryVarListCreate ( SCIP scip,
BINARYVARLIST **  list,
int  startsize 
)
static

Allocates and initializes the BINARYVARLIST struct.

Parameters
scipSCIP data structure
listPointer to the list to be allocated and initialized.
startsizeThe number of entries the list initially can hold.

Definition at line 1465 of file branch_lookahead.c.

References BINARYVARLIST::binaryvars, BINARYVARLIST::memorysize, BINARYVARLIST::nbinaryvars, NULL, and SCIPvarIsBinary().

◆ binaryVarListAppend()

static void binaryVarListAppend ( SCIP scip,
BINARYVARLIST list,
SCIP_VAR vartoadd 
)
static

Appends a binary variable to the list, reallocating the list if necessary.

Parameters
scipSCIP data structure
listThe list to add the var to.
vartoaddThe binary var to add to the list.

Definition at line 1487 of file branch_lookahead.c.

References binaryVarListFree(), BINARYVARLIST::binaryvars, BINARYVARLIST::nbinaryvars, and NULL.

Referenced by executeBranchingRecursive().

◆ binaryVarListDrop()

static void binaryVarListDrop ( BINARYVARLIST list)
static

Remove the last element from the list.

Parameters
listThe list to remove the last element from.

Definition at line 1506 of file branch_lookahead.c.

References NULL, SCIPfreeBuffer, and SCIPfreeBufferArray.

Referenced by executeBranchingRecursive().

◆ binaryVarListFree()

static void binaryVarListFree ( SCIP scip,
BINARYVARLIST **  list 
)
static

Frees all resources allocated by a BINARYVARLIST in opposite order of allocation.

Parameters
scipSCIP data structure
listPointer to the list to free

Definition at line 1520 of file branch_lookahead.c.

Referenced by binaryVarListAppend(), and binConsDataCreate().

◆ binConsDataCreate()

static SCIP_RETCODE binConsDataCreate ( SCIP scip,
BINCONSDATA **  consdata,
int  maxdepth,
int  nstartcons 
)
static

Allocate and initialize the BINCONSDATA struct.

Parameters
scipSCIP data structure
consdataPointer to the struct to be allocated and initialized.
maxdepthThe depth of the recursion as an upper bound of branch vars to hold.
nstartconsThe start size of the array containing the constraints.

Definition at line 1541 of file branch_lookahead.c.

References binaryVarListFree(), constraintListFree(), NULL, and SCIPfreeBuffer.

◆ binConsDataFree()

static void binConsDataFree ( SCIP scip,
BINCONSDATA **  consdata 
)
static

Free all resources in a BINCONSDATA in opposite order of allocation.

Parameters
scipSCIP data structure
consdataPointer to the struct to be freed.

Definition at line 1562 of file branch_lookahead.c.

References candidateListCreate().

◆ candidateListCreate()

static SCIP_RETCODE candidateListCreate ( SCIP scip,
CANDIDATELIST **  candidatelist,
int  ncandidates 
)
static

allocates the candidate list on the buffer WITHOUT initializing the contained array of candidates.

Parameters
scipSCIP data structure
candidatelistthe candidate list to allocate
ncandidatesthe number of candidates the list must hold

Definition at line 1586 of file branch_lookahead.c.

Referenced by binConsDataFree(), and ensureScoresPresent().

◆ candidateListGetAllFractionalCandidates()

static SCIP_RETCODE candidateListGetAllFractionalCandidates ( SCIP scip,
CANDIDATELIST **  candidatelist 
)
static

allocates the given list and fills it with all fractional candidates of the current LP solution.

Parameters
scipSCIP data structure
candidatelistthe list to allocate and fill

Definition at line 1612 of file branch_lookahead.c.

Referenced by executeBranchingRecursive().

◆ candidateListFree()

static SCIP_RETCODE candidateListFree ( SCIP scip,
CANDIDATELIST **  candidatelist 
)
static

frees the allocated buffer memory of the candidate list and frees the contained candidates.

Parameters
scipSCIP data structure
candidatelistthe list to be freed

Definition at line 1657 of file branch_lookahead.c.

References candidateFree(), candidateListKeep(), CANDIDATELIST::ncandidates, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBuffer, and SCIPfreeBufferArray.

Referenced by ensureScoresPresent(), and executeBranchingRecursive().

◆ candidateListKeep()

static SCIP_RETCODE candidateListKeep ( SCIP scip,
CANDIDATELIST candidatelist,
int  nindices 
)
static

keeps only the first candidates and frees the remaining ones

Parameters
scipSCIP data structure
candidatelistthe list to allocate and fill
nindicesthe number of candidates to keep (starting from 0)

Definition at line 1688 of file branch_lookahead.c.

References candidateFree(), CANDIDATELIST::candidates, CANDIDATELIST::ncandidates, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIP_Shortbool.

Referenced by candidateListFree(), and filterCandidates().

◆ domainReductionsCreate()

static SCIP_RETCODE domainReductionsCreate ( SCIP scip,
DOMAINREDUCTIONS **  domreds 
)
static

allocate the struct on the buffer and initialize it with the default values

Parameters
scipSCIP data structure
domredsThe struct that has to be allocated and initialized.

Definition at line 1735 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ domainReductionsFree()

static void domainReductionsFree ( SCIP scip,
DOMAINREDUCTIONS **  domreds 
)
static

frees the given DOMAINREDUCTIONS and all contained Arrays in the opposite order of allocation

Parameters
scipSCIP data structure
domredsPointer to the struct to be freed.

Definition at line 1777 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ statusCreate()

static SCIP_RETCODE statusCreate ( SCIP scip,
STATUS **  status 
)
static

Allocates the status on the buffer memory and initializes it with default values.

Parameters
scipSCIP data structure
statusthe status to be allocated

Definition at line 1811 of file branch_lookahead.c.

References NULL, SCIP_Real, and SCIPfreeBuffer.

Referenced by executeBranchingRecursive().

◆ statusFree()

static void statusFree ( SCIP scip,
STATUS **  status 
)
static

frees the allocated buffer memory of the status

Parameters
scipSCIP data structure
statusthe status to be freed

Definition at line 1835 of file branch_lookahead.c.

Referenced by executeBranchingRecursive().

◆ scoreContainterResetBestSortedCands()

static void scoreContainterResetBestSortedCands ( SCORECONTAINER scorecontainer)
static

resets the array containing the sorted indices w.r.t. their score.

Parameters
scorecontainerthe score container to reset

Definition at line 1859 of file branch_lookahead.c.

References NULL.

Referenced by ensureScoresPresent().

◆ scoreContainerCreate()

static SCIP_RETCODE scoreContainerCreate ( SCIP scip,
SCORECONTAINER **  scorecontainer,
CONFIGURATION config 
)
static

allocates the score container and inits it with default values

Parameters
scipSCIP data structure
scorecontainerpointer to the score container to init
configconfig struct with the user configuration

Definition at line 1870 of file branch_lookahead.c.

◆ findInsertionPoint()

static int findInsertionPoint ( SCIP scip,
SCORECONTAINER scorecontainer,
SCIP_Real  scoretoinsert,
CANDIDATE **  candidates,
int  ncandidates 
)
static

Finds the insertion index for the given score in the candidate list. The score of each candidate is taken from the scorecontainer. The first elements of the candidate list have to be sorted, as this method uses binary search to find the correct insertion point

Parameters
scipSCIP data structure
scorecontainercontainer with all the scores for each candidate
scoretoinsertscore to find the insertion index for
candidatescandidate list where the first nsorted elements are sorted (w.r.t. their score)
ncandidatesnumber of elements in candidates to consider, starting from 0

Definition at line 1918 of file branch_lookahead.c.

Referenced by sortFirstCandidatesByScore().

◆ scoreContainerUpdateSortOrder()

static CANDIDATE* scoreContainerUpdateSortOrder ( SCORECONTAINER scorecontainer,
CANDIDATE candidate,
int  insertpoint 
)
static

Inserts the given probindex into the sorted array in the container, moving all indices after it to the right. Then returns the element that does not fit into the array any longer.

Parameters
scorecontainercontainer to insert the index into
candidatethe probindex of a variable to store
insertpointpoint to store the index at

Definition at line 1963 of file branch_lookahead.c.

References NULL.

◆ scoreContainerSetScore()

static SCIP_RETCODE scoreContainerSetScore ( SCIP scip,
SCORECONTAINER scorecontainer,
CANDIDATE cand,
SCIP_Real  score,
SCIP_Real  downgain,
SCIP_Real  upgain 
)
static

sets the score for the variable in the score container

Parameters
scipSCIP data structure
scorecontainerthe container to write into
candcandidate to add the score for
scorescore to add
downgainLP gain in down child
upgainLP gain in up child

Definition at line 1988 of file branch_lookahead.c.

Referenced by ensureScoresPresent(), and selectVarRecursive().

◆ scoreContainerFree()

static SCIP_RETCODE scoreContainerFree ( SCIP scip,
SCORECONTAINER **  scorecontainer 
)
static

Frees the score container and all of its contained arrays.

Parameters
scipSCIP data structure
scorecontainerscore container to free

Definition at line 2045 of file branch_lookahead.c.

◆ selectVarRecursive()

static SCIP_RETCODE selectVarRecursive ( SCIP scip,
STATUS status,
PERSISTENTDATA persistent,
CONFIGURATION config,
SCIP_SOL baselpsol,
DOMAINREDUCTIONS domainreductions,
BINCONSDATA binconsdata,
CANDIDATELIST candidatelist,
BRANCHINGDECISION decision,
SCORECONTAINER scorecontainer,
LEVEL2DATA level2data,
int  recursiondepth,
SCIP_Real  lpobjval,
SCIP_Real  baselpobjval,
SCIP_Longint niterations,
int *  ndeepestcutoffs,
SCIP_Real bestgain,
SCIP_Real totalgains,
int *  ntotalgains,
int *  ndeepestnodes 
)
static

branches recursively on all given candidates

Parameters
scipSCIP data structure
statuscurrent status
persistentcontainer to store data over multiple calls to the branching rule; or NULL
configthe configuration of the branching rule
baselpsolbase lp solution
domainreductionscontainer collecting all domain reductions found
binconsdatacontainer collecting all binary constraints
candidatelistlist of candidates to branch on
decisionstruct to store the final decision
scorecontainercontainer to retrieve already calculated scores
level2datalevel 2 LP results data
recursiondepthremaining recursion depth
lpobjvalLP objective value of current probing node
baselpobjvalLP objective value of focus node (not probing)
niterationspointer to store the total number of iterations for this variable
ndeepestcutoffspointer to store the total number of cutoffs on the deepest level
bestgainpointer to store the best gain found with these candidates
totalgainspointer to store the sum over all gains that are valid in both children
ntotalgainspointer to store the number of gains summed in totalgains
ndeepestnodespointer to store the number of nodes processed in the deepest level

Definition at line 4722 of file branch_lookahead.c.

References CONFIGURATION::abbreviated, addLowerBound(), addUpperBound(), applyDeeperDomainReductions(), applySingleDeeperDomainReductions(), areBoundsChanged(), BMScopyMemoryArray, BRANCHINGDECISION::boundsvalid, branchingDecisionEnsureBoundArraysSize(), branchingResultDataCopy(), branchingResultDataCreate(), branchingResultDataFree(), branchingResultDataInit(), CANDIDATE::branchval, BRANCHINGDECISION::branchval, CANDIDATE::branchvar, BRANCHINGDECISION::branchvar, calculateScore(), CANDIDATELIST::candidates, BINCONSDATA::conslist, BRANCHINGRESULTDATA::cutoff, STATUS::cutoff, domainReductionsCreate(), domainReductionsFree(), STATUS::domred, BRANCHINGDECISION::downdb, BRANCHINGDECISION::downdbvalid, BRANCHINGDECISION::downlowerbounds, BRANCHINGDECISION::downupperbounds, BRANCHINGRESULTDATA::dualbound, BRANCHINGRESULTDATA::dualboundvalid, CONFIGURATION::enforcemaxdomreds, executeBranchingRecursive(), FALSE, getOldBranching(), CONFIGURATION::inscoring, isBranchFurtherLoopDecrement(), isStoreDecision(), isUseOldBranching(), LABdebugMessage, STATUS::limitreached, DOMAINREDUCTIONS::lowerbounds, STATUS::lperror, MAX, STATUS::maxnconsreached, CONFIGURATION::maxnviolatedbincons, CONFIGURATION::maxnviolatedcons, CONFIGURATION::maxnviolateddomreds, CONFIGURATION::mergedomainreductions, CANDIDATELIST::ncandidates, DOMAINREDUCTIONS::nchangedvars, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::ndeepestnodes, CONSTRAINTLIST::nelements, BRANCHINGRESULTDATA::niterations, DOMAINREDUCTIONS::nsimplebounds, NULL, CONSTRAINTLIST::nviolatedcons, DOMAINREDUCTIONS::nviolatedvars, BRANCHINGRESULTDATA::objval, CONFIGURATION::prefersimplebounds, BRANCHINGDECISION::proveddb, PERSISTENTDATA::restartindex, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIP_VERBLEVEL_NORMAL, SCIPallColsInLP(), SCIPgetBoolParam(), SCIPgetCutoffbound(), SCIPgetLPI(), SCIPgetNVars(), SCIPgetProbingDepth(), SCIPinfinity(), SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisRelGT(), SCIPisStopped(), SCIPisStrongbranchDownFirst(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), BRANCHINGDECISION::score, scoreContainerSetScore(), CONFIGURATION::storeunviolatedsol, TRUE, CONFIGURATION::updatebranchingresults, updateOldBranching(), BRANCHINGDECISION::updb, BRANCHINGDECISION::updbvalid, BRANCHINGDECISION::uplowerbounds, DOMAINREDUCTIONS::upperbounds, BRANCHINGDECISION::upupperbounds, and CONFIGURATION::usedomainreduction.

Referenced by executeBranchingRecursive(), and getFSBResult().

◆ addLowerBound()

static void addLowerBound ( SCIP scip,
SCIP_VAR var,
SCIP_Real  lowerbound,
SCIP_SOL baselpsol,
SCIP_Bool  simplechange,
DOMAINREDUCTIONS domainreductions 
)
static

Adds the given lower bound to the DOMAINREDUCTIONS struct.

Parameters
scipSCIP data structure
varThe variable the bound should be added for.
lowerboundThe new lower bound for the variable.
baselpsolThe LP solution of the base problem. Used to check whether the domain reduction is violated by it.
simplechangedoes the change result from an infeasible child node?
domainreductionsThe struct the domain reduction should be added to.

Definition at line 2100 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ addUpperBound()

static void addUpperBound ( SCIP scip,
SCIP_VAR var,
SCIP_Real  upperbound,
SCIP_SOL baselpsol,
SCIP_Bool  simplechange,
DOMAINREDUCTIONS domainreductions 
)
static

Adds the given upper bound to the DOMAINREDUCTIONS struct.

Parameters
scipSCIP data structure
varThe variable the bound should be added for.
upperboundThe new upper bound for the variable.
baselpsolThe LP solution of the base problem. Used to check whether the domain reduction is violated by it.
simplechangedoes the change result from an infeasible child node?
domainreductionsThe struct the domain reduction should be added to.

Definition at line 2165 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ applySingleDeeperDomainReductions()

static void applySingleDeeperDomainReductions ( SCIP scip,
SCIP_SOL baselpsol,
int  maxstoredomreds,
DOMAINREDUCTIONS targetdomreds,
DOMAINREDUCTIONS domreds 
)
static

apply the domain reductions from a single struct to another one; this may be used in case one of the two child problems of a variable is infeasible

Parameters
scipSCIP data structure
baselpsolThe LP solution of the base problem. Used to check whether the domain reduction is violated by it.
maxstoredomredsmaximum number of domain reductions to store
targetdomredsThe target that should be filled with the merged data.
domredssource domain reductions

Definition at line 2234 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ applyDeeperDomainReductions()

static void applyDeeperDomainReductions ( SCIP scip,
SCIP_SOL baselpsol,
int  maxstoredomreds,
DOMAINREDUCTIONS targetdomreds,
DOMAINREDUCTIONS downdomreds,
DOMAINREDUCTIONS updomreds 
)
static

merges the domain reduction data from the two given branching children data into the target parent data

Parameters
scipSCIP data structure
baselpsolThe LP solution of the base problem. Used to check whether the domain reduction is violated by it.
maxstoredomredsmaximum number of domain reductions to store
targetdomredsThe target that should be filled with the merged data.
downdomredsOne of the source DOMAINREDUCTIONS.
updomredsThe other source DOMAINREDUCTIONS.

Definition at line 2288 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ applyDomainReductions()

static SCIP_RETCODE applyDomainReductions ( SCIP scip,
CONFIGURATION config,
SCIP_SOL baselpsol,
DOMAINREDUCTIONS domreds,
SCIP_Bool domredcutoff,
SCIP_Bool domred 
)
static

Applies the domain reductions to the current node.

Parameters
scipSCIP data structure
configthe configuration of the branching rule
baselpsolThe LP solution of the base problem. Used to check whether the domain reduction is violated by it.
domredsThe domain reductions that should be applied to the current node.
domredcutoffpointer to store whether a cutoff was found due to domain reductions
domredpointer to store whether a domain change was added

Definition at line 2366 of file branch_lookahead.c.

◆ copyCurrentSolution()

static SCIP_RETCODE copyCurrentSolution ( SCIP scip,
SCIP_SOL **  lpsol 
)
static

Copies the current LP solution into the given pointer. Needs to be freed after usage!

Parameters
scipSCIP data structure
lpsolpointer to store the solution into

Definition at line 2541 of file branch_lookahead.c.

References NULL, and SCIP_Real.

◆ branchOnVar()

static SCIP_RETCODE branchOnVar ( SCIP scip,
CONFIGURATION config,
BRANCHINGDECISION decision 
)
static

Executes the branching on a given variable with a given value.

Parameters
scipSCIP data structure
configconfig struct with the user configuration
decisionthe decision with all the needed data

Definition at line 2560 of file branch_lookahead.c.

◆ getNIterationsLastLP()

static SCIP_RETCODE getNIterationsLastLP ( SCIP scip,
SCIP_Longint iterations 
)
static

Get the number of iterations the last LP needed

Parameters
scipSCIP data structure
iterationspointer to store the number of iterations

Definition at line 2694 of file branch_lookahead.c.

◆ executeBranching()

static SCIP_RETCODE executeBranching ( SCIP scip,
CONFIGURATION config,
SCIP_Bool  downbranching,
CANDIDATE candidate,
BRANCHINGRESULTDATA resultdata,
SCIP_SOL baselpsol,
DOMAINREDUCTIONS domreds,
STATUS status 
)
static

Creates a new probing node with a new bound for the given candidate and solves the corresponding LP.

Parameters
scipSCIP data structure
configconfiguration to control the behavior
downbranchingthe branching direction
candidatethe candidate to branch on
resultdatapointer to the result data which gets filled with the status
baselpsolthe base lp solution
domredsstruct to store the domain reduction found during propagation
statusstatus will contain updated lperror and limit fields

Definition at line 2718 of file branch_lookahead.c.

Referenced by executeBranchingRecursive().

◆ createBinaryConstraint()

static SCIP_RETCODE createBinaryConstraint ( SCIP scip,
CONFIGURATION config,
SCIP_CONS **  constraint,
char *  constraintname,
SCIP_VAR **  consvars,
int  nconsvars 
)
static

Creates a logic or constraint based on the given 'consvars'. This array has to consist of the negated versions of the variables present on a cutoff "path" (path means all variables from the root directly to the cutoff node). Let x_1, ..., x_n be the variables on a path to a cutoff with the branchings x_i <= 1 for all i. Summed up the constraints would look like x_1 + ... x_n <= n-1. Let y_i = 1 - x_i. Then we have y_1 + ... + y_n >= 1 which is a logic or constraint.

Parameters
scipSCIP data structure
configconfiguration containing flags changing the behavior
constraintpointer to store the created constraint in
constraintnamename of the new constraint
consvarsarray containing the negated binary vars
nconsvarsthe number of elements in 'consvars'

Definition at line 2918 of file branch_lookahead.c.

◆ createBinaryConstraintName()

static void createBinaryConstraintName ( SCIP_VAR **  binaryvars,
int  nbinaryvars,
char *  constraintname 
)
static

Create a name for the binary constraint.

Parameters
binaryvarsthe variables contained in the constraint
nbinaryvarsthe number of elements in 'binaryvars'
constraintnamethe char pointer to store the name in

Definition at line 2961 of file branch_lookahead.c.

References addBinaryConstraint(), BINCONSDATA::binaryvars, NULL, SCIP_MAXSTRLEN, and SCIPvarGetName().

◆ addBinaryConstraint()

static SCIP_RETCODE addBinaryConstraint ( SCIP scip,
CONFIGURATION config,
BINCONSDATA binconsdata,
SCIP_SOL baselpsol 
)
static

Add the constraints found during the lookahead branching. The implied binary bounds were found when two or more consecutive branchings of binary variables were cutoff. Then these branching constraints can be combined into a single 'binary constraint'.

Parameters
scipSCIP data structure
configthe configuration of the branching rule
binconsdatacollected binary constraints
baselpsolthe original lp solution, used to check the violation of the constraint

Definition at line 2994 of file branch_lookahead.c.

Referenced by createBinaryConstraintName(), and executeBranchingRecursive().

◆ applyBinaryConstraints()

static SCIP_RETCODE applyBinaryConstraints ( SCIP scip,
SCIP_NODE basenode,
CONSTRAINTLIST conslist,
CONFIGURATION config,
SCIP_Bool consadded,
SCIP_Bool cutoff,
SCIP_Bool boundchange 
)
static

applies the binary constraints to the original problem.

Parameters
scipSCIP data structure
basenodeoriginal branching node
conslistlist of constraints to be added
configthe configuration of the branching rule
consaddedpointer to store whether at least one constraint was added
cutoffpointer to store whether the original problem was made infeasible
boundchangepointer to store whether a bound change has been applied by adding the constraint as a clique

Definition at line 3064 of file branch_lookahead.c.

◆ areBoundsChanged()

static SCIP_Bool areBoundsChanged ( SCIP scip,
SCIP_VAR var,
SCIP_Real  lowerbound,
SCIP_Real  upperbound 
)
static

checks whether the given bounds are still the bounds of the given variable

Parameters
scipSCIP data structure
varvariable to check the bounds of
lowerboundreference lower bound
upperboundreference upper bound

Definition at line 3193 of file branch_lookahead.c.

References STATUS::cutoff, STATUS::domred, isBranchFurtherLoopDecrement(), STATUS::limitreached, STATUS::lperror, STATUS::maxnconsreached, NULL, and SCIP_Bool.

Referenced by selectVarRecursive().

◆ isBranchFurther()

static SCIP_Bool isBranchFurther ( STATUS status,
SCIP_Bool  checkdomreds 
)
static

Checks whether the branching rule should continue or terminate with the currently gathered data

Parameters
statuscurrent status
checkdomredsshould domain reductions be checked?

Definition at line 3213 of file branch_lookahead.c.

References FALSE, NULL, and SCIP_Bool.

Referenced by executeBranchingRecursive(), and filterCandidates().

◆ isBranchFurtherLoopDecrement()

static SCIP_Bool isBranchFurtherLoopDecrement ( STATUS status,
int *  loopcounter 
)
static

Checks whether the branching rule should continue or terminate with the currently gathered data. Additionally decrements the given loopcounter. This is needed to better emulate the behavior of FSB by LAB with a depth of 1.

Parameters
statuscurrent status
loopcounterthe counter to decrement

Definition at line 3227 of file branch_lookahead.c.

References CONFIGURATION::inscoring, NULL, SCIPgetNNodes(), and SCIPgetVarStrongbranchNode().

Referenced by areBoundsChanged(), and selectVarRecursive().

◆ isUseOldBranching()

static SCIP_Bool isUseOldBranching ( SCIP scip,
PERSISTENTDATA persistent,
CONFIGURATION config,
SCIP_VAR branchvar 
)
static

determines whether the previous LAB result of a variable should be reused

Parameters
scipSCIP data structure
persistentdata storage over multiple calls to the rule
configthe configuration of the branching rule
branchvarvariable to check

Definition at line 3247 of file branch_lookahead.c.

References getOldBranching(), NULL, CONFIGURATION::reevalage, SCIP_Real, SCIPgetNLPs(), SCIPgetNNodes(), and SCIPvarGetProbindex().

Referenced by selectVarRecursive().

◆ getOldBranching()

static SCIP_RETCODE getOldBranching ( SCIP scip,
PERSISTENTDATA persistent,
CONFIGURATION config,
SCIP_VAR branchvar,
BRANCHINGRESULTDATA downbranchingresult,
BRANCHINGRESULTDATA upbranchingresult,
SCIP_Real oldlpobjval 
)
static

retrieves previous LAB result for the given variable

Parameters
scipSCIP data structure
persistentdata storage over multiple calls to the rule
configthe configuration of the branching rule
branchvarvariable to get previous results for
downbranchingresultpointer to store the previous down result in
upbranchingresultpointer to store the previous up result in
oldlpobjvalpointer to store the previous base lp objval in

Definition at line 3273 of file branch_lookahead.c.

Referenced by isUseOldBranching(), and selectVarRecursive().

◆ updateOldBranching()

static SCIP_RETCODE updateOldBranching ( SCIP scip,
PERSISTENTDATA persistent,
CONFIGURATION config,
SCIP_VAR branchvar,
SCIP_Real  branchval,
BRANCHINGRESULTDATA downbranchingresult,
BRANCHINGRESULTDATA upbranchingresult,
SCIP_Real  lpobjval 
)
static

stores the LAB result for use in a later call to the branching rule

Parameters
scipSCIP data structure
persistentdata storage over multiple calls to the rule
configthe configuration of the branching rule
branchvarvariable to store previous results for
branchvalthe value of branchvar
downbranchingresultdown branching result to store
upbranchingresultup branching result to store
lpobjvalbase lp obj val

Definition at line 3326 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ getFSBResult()

static SCIP_RETCODE getFSBResult ( SCIP scip,
STATUS status,
PERSISTENTDATA persistent,
CONFIGURATION config,
SCIP_SOL baselpsol,
DOMAINREDUCTIONS domainreductions,
BINCONSDATA binconsdata,
CANDIDATELIST candidatelist,
BRANCHINGDECISION decision,
SCORECONTAINER scorecontainer,
LEVEL2DATA level2data,
SCIP_Real  lpobjval 
)
static

calculates the FSB scores for the given candidates

Parameters
scipSCIP data structure
statuscurrent status
persistentcontainer to store data over multiple calls to the branching rule; or NULL
configthe configuration of the branching rule
baselpsolbase lp solution
domainreductionscontainer collecting all domain reductions found; or NULL
binconsdatacontainer collecting all binary constraints; or NULL
candidatelistlist containing all candidates to consider
decisionstruct to store the final decision
scorecontainercontainer to retrieve already calculated scores; or NULL
level2datalevel 2 LP results data
lpobjvalbase LP objective value

Definition at line 3367 of file branch_lookahead.c.

References CANDIDATE::branchvar, calculateScoreFromResult(), CANDIDATELIST::candidates, FALSE, CONFIGURATION::inscoring, CANDIDATELIST::ncandidates, NULL, CONFIGURATION::recursiondepth, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetProbingDepth(), SCIPinProbing(), SCIPsumepsilon(), SCIPvarGetName(), selectVarRecursive(), and TRUE.

Referenced by ensureScoresPresent().

◆ calculateScoreFromResult()

static SCIP_Real calculateScoreFromResult ( SCIP scip,
SCIP_VAR branchvar,
BRANCHINGRESULTDATA downbranchingresult,
BRANCHINGRESULTDATA upbranchingresult,
SCIP_Real  lpobjval 
)
static

calculates the score based on the down and up branching result

Parameters
scipSCIP data structure
branchvarvariable to get the score for
downbranchingresultbranching result of the down branch
upbranchingresultbranching result of the up branch
lpobjvalobjective value to get difference to as gain

Definition at line 3452 of file branch_lookahead.c.

Referenced by getFSBResult().

◆ calculateScoreFromResult2()

static SCIP_Real calculateScoreFromResult2 ( SCIP scip,
SCIP_VAR branchvar,
BRANCHINGRESULTDATA downbranchingresult,
BRANCHINGRESULTDATA upbranchingresult,
SCIP_Real  lpobjval 
)
static

calculates the score based on the down and up branching result

Parameters
scipSCIP data structure
branchvarvariable to get the score for
downbranchingresultbranching result of the down branch
upbranchingresultbranching result of the up branch
lpobjvalobjective value to get difference to as gain

Definition at line 3496 of file branch_lookahead.c.

◆ calculateScoreFromDeeperscore()

static SCIP_Real calculateScoreFromDeeperscore ( SCIP scip,
SCIP_VAR branchvar,
BRANCHINGRESULTDATA downbranchingresult,
BRANCHINGRESULTDATA upbranchingresult 
)
static

calculates the score based on the down and up branching scores

Parameters
scipSCIP data structure
branchvarvariable to get the score for
downbranchingresultbranching result of the down branch
upbranchingresultbranching result of the up branch

Definition at line 3566 of file branch_lookahead.c.

◆ calculateScoreFromDeeperscoreAndCutoffs()

static SCIP_Real calculateScoreFromDeeperscoreAndCutoffs ( SCIP scip,
SCIP_VAR branchvar,
BRANCHINGRESULTDATA downbranchingresult,
BRANCHINGRESULTDATA upbranchingresult 
)
static

calculates the score based on the down and up branching scores

Parameters
scipSCIP data structure
branchvarvariable to get the score for
downbranchingresultbranching result of the down branch
upbranchingresultbranching result of the up branch

Definition at line 3603 of file branch_lookahead.c.

◆ calculateWeightedGain()

static SCIP_Real calculateWeightedGain ( SCIP scip,
CONFIGURATION config,
BRANCHINGRESULTDATA downbranchingresult,
BRANCHINGRESULTDATA upbranchingresult,
SCIP_Real  lpobjval 
)
static

calculates the combined gain, weighted with parameters given by the user configuration

Parameters
scipSCIP data structure
configLAB configuration
downbranchingresultbranching result of the down branch
upbranchingresultbranching result of the up branch
lpobjvalobjective value to get difference to as gain

Definition at line 3659 of file branch_lookahead.c.

◆ calculateScaledCutoffScore()

static SCIP_Real calculateScaledCutoffScore ( BRANCHINGRESULTDATA downbranchingresult,
BRANCHINGRESULTDATA upbranchingresult 
)
static

calculates the score as mentioned in the lookahead branching paper by Glankwamdee and Linderoth; their score scales the number of cutoffs on the last layer of a 2-level temporary branching tree with the average gain of every last level problem; together with the best gain for each branch of a variable we get the final score

Parameters
downbranchingresultbranching result of the down branch
upbranchingresultbranching result of the up branch

Definition at line 3709 of file branch_lookahead.c.

◆ calculateWeightedCutoffScore()

static SCIP_Real calculateWeightedCutoffScore ( CONFIGURATION config,
BRANCHINGRESULTDATA downbranchingresult,
BRANCHINGRESULTDATA upbranchingresult 
)
static

calculates the score as mentioned in the lookahead branching paper by Glankwamdee and Linderoth; their score scales the number of cutoffs on the last layer of a 2-level temporary branching tree with the average gain of every last level problem; together with the best gain for each branch of a variable we get the final score

Parameters
configLAB configuration
downbranchingresultbranching result of the down branch
upbranchingresultbranching result of the up branch

Definition at line 3741 of file branch_lookahead.c.

◆ calculateCutoffScore()

static SCIP_Real calculateCutoffScore ( SCIP scip,
SCIP_VAR branchvar,
BRANCHINGRESULTDATA downbranchingresult,
BRANCHINGRESULTDATA upbranchingresult,
SCIP_Real  lpobjval 
)
static
Parameters
scipSCIP data structure
branchvarvariable to get the score for
downbranchingresultbranching result of the down branch
upbranchingresultbranching result of the up branch
lpobjvalobjective value to get difference to as gain

Definition at line 3770 of file branch_lookahead.c.

◆ calculateRelCutoffScore()

static SCIP_Real calculateRelCutoffScore ( SCIP scip,
SCIP_VAR branchvar,
BRANCHINGRESULTDATA downbranchingresult,
BRANCHINGRESULTDATA upbranchingresult,
SCIP_Real  lpobjval 
)
static
Parameters
scipSCIP data structure
branchvarvariable to get the score for
downbranchingresultbranching result of the down branch
upbranchingresultbranching result of the up branch
lpobjvalobjective value to get difference to as gain

Definition at line 3829 of file branch_lookahead.c.

◆ calculateScore()

static SCIP_Real calculateScore ( SCIP scip,
CONFIGURATION config,
SCIP_VAR branchvar,
BRANCHINGRESULTDATA downbranchingresult,
BRANCHINGRESULTDATA upbranchingresult,
SCIP_Real  lpobjval,
SCIP_Real  baselpobjval 
)
static

scoring method that selects an actual scoring method based on the user configuration

Parameters
scipSCIP data structure
configLAB configuration
branchvarvariable to get the score for
downbranchingresultbranching result of the down branch
upbranchingresultbranching result of the up branch
lpobjvalobjective value to get difference to as gain
baselpobjvalbase objective value to get difference to as gain

Definition at line 3893 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ calculateScoreFromPseudocosts()

static SCIP_Real calculateScoreFromPseudocosts ( SCIP scip,
CANDIDATE lpcand 
)
static

calculates the score based on the pseudocosts of the given variable

Parameters
scipSCIP data structure
lpcandcandidate to get the score for

Definition at line 3958 of file branch_lookahead.c.

Referenced by ensureScoresPresent().

◆ sortFirstCandidatesByScore()

static void sortFirstCandidatesByScore ( SCIP scip,
CANDIDATELIST candidatelist,
SCORECONTAINER scorecontainer,
int  nbestcandidates 
)
static

sorts the best candidates (w.r.t. the score in the container) of the candidate list to the front of the list

Parameters
scipSCIP data structure
candidatelistcandidates to be sorted
scorecontainercontainer with the scores for each candidate
nbestcandidatesnumber of candidates that should be kept sorted at the start of the list

Definition at line 4007 of file branch_lookahead.c.

References CANDIDATE::branchvar, CANDIDATELIST::candidates, findInsertionPoint(), isCandidateReliable(), LABdebugMessage, CANDIDATELIST::ncandidates, NULL, SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPgetVarPseudocostCountCurrentRun(), SCIPvarGetProbindex(), and SCORECONTAINER::scores.

Referenced by filterCandidates().

◆ isCandidateReliable()

static SCIP_Bool isCandidateReliable ( SCIP scip,
SCIP_VAR branchvar 
)
static

checks whether the given candidates is reliable, so that its pseudocosts may be used

Parameters
scipSCIP data structure
branchvarvar to check for reliability

Definition at line 4072 of file branch_lookahead.c.

Referenced by ensureScoresPresent(), and sortFirstCandidatesByScore().

◆ isCurrentNodeCutoff()

static SCIP_Bool isCurrentNodeCutoff ( SCIP scip)
static

checks whether the current problem is feasible or cutoff

Parameters
scipSCIP data structure

Definition at line 4094 of file branch_lookahead.c.

Referenced by filterCandidates().

◆ ensureScoresPresent()

static SCIP_RETCODE ensureScoresPresent ( SCIP scip,
STATUS status,
PERSISTENTDATA persistent,
CONFIGURATION config,
SCIP_SOL baselpsol,
DOMAINREDUCTIONS domainreductions,
BINCONSDATA binconsdata,
CANDIDATELIST allcandidates,
BRANCHINGDECISION decision,
SCORECONTAINER scorecontainer,
LEVEL2DATA level2data,
SCIP_Real  lpobjval 
)
static

Ensures that the scores are present in the scorecontainer for each of the candidates to consider

Parameters
scipSCIP data structure
statuscurrent status
persistentcontainer to store data over multiple calls to the branching rule; or NULL
configthe configuration of the branching rule
baselpsolbase lp solution
domainreductionscontainer collecting all domain reductions found; or NULL
binconsdatacontainer collecting all binary constraints; or NULL
allcandidateslist containing all candidates to consider
decisionstruct to store the final decision
scorecontainercontainer to retrieve already calculated scores; or NULL
level2datalevel 2 LP results data
lpobjvalbase LP objective value

Definition at line 4105 of file branch_lookahead.c.

References CONFIGURATION::abbrevpseudo, CANDIDATE::branchvar, calculateScoreFromPseudocosts(), candidateListCreate(), candidateListFree(), CANDIDATELIST::candidates, filterCandidates(), getFSBResult(), isCandidateReliable(), LABdebugMessage, CONFIGURATION::level2avgscore, CONFIGURATION::level2zeroscore, CANDIDATELIST::ncandidates, SCORECONTAINER::nsetscores, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetProbingDepth(), SCIPisLT(), SCIPvarGetProbindex(), scoreContainerSetScore(), scoreContainterResetBestSortedCands(), SCORECONTAINER::scores, and SCORECONTAINER::scoresum.

Referenced by filterCandidates().

◆ filterCandidates()

static SCIP_RETCODE filterCandidates ( SCIP scip,
STATUS status,
PERSISTENTDATA persistent,
CONFIGURATION config,
SCIP_SOL baselpsol,
DOMAINREDUCTIONS domainreductions,
BINCONSDATA binconsdata,
CANDIDATELIST candidatelist,
BRANCHINGDECISION decision,
SCORECONTAINER scorecontainer,
LEVEL2DATA level2data,
SCIP_Real  lpobjval 
)
static

Get the candidates to temporarily branch on. In the LAB case this is the complete list of possible candidates. In the ALAB case only the 'best' candidates are returned.

Parameters
scipSCIP data structure
statuscurrent status
persistentcontainer to store data over multiple calls to the branching rule; or NULL
configthe configuration of the branching rule
baselpsolbase lp solution
domainreductionscontainer collecting all domain reductions found; or NULL
binconsdatacontainer collecting all binary constraints; or NULL
candidatelistlist of candidates to branch on
decisionstruct to store the final decision
scorecontainercontainer to retrieve already calculated scores; or NULL
level2datalevel 2 LP results data
lpobjvalbase LP objective value

Definition at line 4237 of file branch_lookahead.c.

References CONFIGURATION::abbreviated, CANDIDATE::branchvar, candidateListKeep(), CANDIDATELIST::candidates, STATUS::cutoff, SCORECONTAINER::downgains, ensureScoresPresent(), executeBranchingRecursive(), CONFIGURATION::filterbymaxgain, isBranchFurther(), isCurrentNodeCutoff(), LABdebugMessage, MAX, CONFIGURATION::maxncands, CONFIGURATION::maxndeepercands, CANDIDATELIST::ncandidates, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPgetProbingDepth(), SCIPinProbing(), SCIPisSumLE(), SCIPvarGetName(), SCIPvarGetProbindex(), SCORECONTAINER::scores, sortFirstCandidatesByScore(), TRUE, SCORECONTAINER::upgains, and CONFIGURATION::worsefactor.

Referenced by ensureScoresPresent(), and executeBranchingRecursive().

◆ executeBranchingRecursive()

static SCIP_RETCODE executeBranchingRecursive ( SCIP scip,
STATUS status,
CONFIGURATION config,
SCIP_SOL baselpsol,
CANDIDATE candidate,
SCIP_Real  localbaselpsolval,
SCIP_Real  baselpobjval,
int  recursiondepth,
DOMAINREDUCTIONS domainreductions,
BINCONSDATA binconsdata,
LEVEL2DATA level2data,
BRANCHINGRESULTDATA branchingresult,
SCORECONTAINER scorecontainer,
SCIP_Bool  downbranching 
)
static

Executes the general branching on a variable in a given direction (up/down) and repeats the algorithm from the new node

Parameters
scipSCIP data structure
statuscurrent status
configthe configuration of the branching rule
baselpsolthe base lp solution
candidatecandidate to branch on
localbaselpsolvalthe objective value of the current temporary problem
baselpobjvalLP objective value of focus node (not probing)
recursiondepthremaining recursion depth
domainreductionscontainer collecting all domain reductions found; or NULL
binconsdatacontainer collecting all binary constraints; or NULL
level2datalevel 2 LP results data
branchingresultcontainer to store the result of the branching in
scorecontainercontainer to retrieve already calculated scores; or NULL
downbranchingshould we branch up or down in here?

Definition at line 4373 of file branch_lookahead.c.

References addBinaryConstraint(), BRANCHINGRESULTDATA::bestgain, binaryVarListAppend(), binaryVarListDrop(), BINCONSDATA::binaryvars, LEVEL2DATA::branchdir1, LEVEL2DATA::branchdir2, branchingDecisionCreate(), branchingDecisionFree(), CANDIDATE::branchval, LEVEL2DATA::branchval1, LEVEL2DATA::branchval2, CANDIDATE::branchvar, LEVEL2DATA::branchvar1, LEVEL2DATA::branchvar2, candidateListFree(), candidateListGetAllFractionalCandidates(), candidateStoreWarmStartInfo(), BRANCHINGRESULTDATA::cutoff, LEVEL2RESULT::cutoff, STATUS::cutoff, BRANCHINGRESULTDATA::deeperscore, STATUS::domred, BRANCHINGRESULTDATA::dualbound, BRANCHINGRESULTDATA::dualboundvalid, executeBranching(), FALSE, filterCandidates(), CANDIDATE::fracval, CONFIGURATION::inscoring, isBranchFurther(), LABdebugMessage, level2dataGetResult(), level2dataStoreResult(), STATUS::limitreached, STATUS::lperror, LEVEL2RESULT::lpobjval, MAX, BINARYVARLIST::nbinaryvars, CANDIDATELIST::ncandidates, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::ndeepestnodes, BRANCHINGRESULTDATA::niterations, BRANCHINGRESULTDATA::ntotalgains, NULL, BRANCHINGRESULTDATA::objval, BRANCHINGDECISION::proveddb, CONFIGURATION::reusebasis, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPallColsInLP(), SCIPbacktrackProbing(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetCutoffbound(), SCIPgetLPSolstat(), SCIPgetNegatedVar(), SCIPgetProbingDepth(), SCIPisGE(), SCIPisStopped(), SCIPupdateVarPseudocost(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), BRANCHINGDECISION::score, selectVarRecursive(), statusCreate(), statusFree(), BRANCHINGRESULTDATA::totalgains, TRUE, and LEVEL2RESULT::valid.

Referenced by filterCandidates(), and selectVarRecursive().

◆ isStoreDecision()

static SCIP_Bool isStoreDecision ( CONFIGURATION config,
BINCONSDATA binconsdata,
DOMAINREDUCTIONS domainreductions 
)
static

checks whether the current decision should be stored. This is the case if we found domain reductions or constraints that will be applied, but none of them cuts off the current LP solution. Then our current decision still holds true for the next call and can be reused without further calculations

Parameters
configthe configuration of the branching rule
binconsdatacontainer collecting all binary constraints; or NULL
domainreductionscontainer collecting all domain reductions found; or NULL

Definition at line 5305 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ selectVarStart()

static SCIP_RETCODE selectVarStart ( SCIP scip,
CONFIGURATION config,
PERSISTENTDATA persistent,
STATUS status,
BRANCHINGDECISION decision,
SCORECONTAINER scorecontainer,
CANDIDATELIST candidatelist 
)
static

starting point to obtain a branching decision via LAB/ALAB.

Parameters
scipSCIP data structure
configthe configuration of the branching rule
persistentcontainer to store data over multiple calls to the branching rule; or NULL
statuscurrent status
decisionstruct to store the final decision
scorecontainercontainer to retrieve already calculated scores; or NULL
candidatelistlist of candidates to branch on

Definition at line 5331 of file branch_lookahead.c.

◆ isUsePreviousResult()

static SCIP_Bool isUsePreviousResult ( SCIP scip,
SCIP_BRANCHRULEDATA branchruledata 
)
static

We can use the previous result, stored in the branchruledata, if the branchingvariable (as an indicator) is set and the current lp solution is equal to the previous lp solution.

Returns
TRUE, if we can branch on the previous decision, FALSE, else.
Parameters
scipSCIP data structure
branchruledatabranching rule data

Definition at line 5666 of file branch_lookahead.c.

◆ usePreviousResult()

static SCIP_RETCODE usePreviousResult ( SCIP scip,
SCIP_BRANCHRULEDATA branchruledata,
SCIP_RESULT result 
)
static

Uses the results from the previous run saved in the branchruledata to branch. This is the case, if in the previous run only non-violating constraints were added. In that case we can use the branching decision we would have made then. If everything worked, the result pointer contains SCIP_BRANCHED.

Returns
SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See SCIP_RETCODE for a complete list of error codes.
Parameters
scipSCIP data structure
branchruledatabranching rule data
resultthe pointer to the branching result

Definition at line 5702 of file branch_lookahead.c.

◆ freePersistent()

static SCIP_RETCODE freePersistent ( SCIP scip,
SCIP_BRANCHRULEDATA branchruledata 
)
static

◆ initBranchruleData()

static SCIP_RETCODE initBranchruleData ( SCIP scip,
SCIP_BRANCHRULEDATA branchruledata 
)
static

initializes the branchruledata and the contained structs

Parameters
scipSCIP data structure
branchruledatathe branch rule data to initialize

Definition at line 5779 of file branch_lookahead.c.

References branchingDecisionInit(), BRANCHRULE_NAME, freePersistent(), LABdebugMessage, NULL, SCIP_CALL, SCIP_DECL_BRANCHCOPY(), SCIP_DECL_BRANCHFREE(), SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPbranchruleGetName(), SCIPgetNBinVars(), SCIPgetNIntVars(), and TRUE.

Referenced by freePersistent().

◆ SCIP_DECL_BRANCHCOPY()

static SCIP_DECL_BRANCHCOPY ( branchCopyLookahead  )
static

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

Definition at line 5842 of file branch_lookahead.c.

Referenced by initBranchruleData().

◆ SCIP_DECL_BRANCHFREE()

static SCIP_DECL_BRANCHFREE ( branchFreeLookahead  )
static

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

Definition at line 5853 of file branch_lookahead.c.

References LABdebugMessage, NULL, SCIP_VERBLEVEL_FULL, and SCIPbranchruleGetData().

Referenced by initBranchruleData().

◆ SCIP_DECL_BRANCHINIT()

static SCIP_DECL_BRANCHINIT ( branchInitLookahead  )
static

◆ SCIP_DECL_BRANCHEXIT()

static SCIP_DECL_BRANCHEXIT ( branchExitLookahead  )
static

deinitialization method of branching rule (called before transformed problem is freed)

Definition at line 5931 of file branch_lookahead.c.

Referenced by SCIP_DECL_BRANCHINIT().

◆ SCIP_DECL_BRANCHEXITSOL()

static SCIP_DECL_BRANCHEXITSOL ( branchExitSolLookahead  )
static

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

Definition at line 5968 of file branch_lookahead.c.

References BRANCHRULE_NAME, LABdebugMessage, NULL, SCIP_Bool, SCIP_VERBLEVEL_HIGH, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPgetCurrentNode(), and SCIPnodeGetNumber().

◆ SCIP_DECL_BRANCHEXECLP()

static SCIP_DECL_BRANCHEXECLP ( branchExeclpLookahead  )
static

branching execution method for fractional LP solutions

Definition at line 5985 of file branch_lookahead.c.

◆ SCIPincludeBranchruleLookahead()

SCIP_RETCODE SCIPincludeBranchruleLookahead ( SCIP scip)

creates the lookahead branching rule and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 6212 of file branch_lookahead.c.

Referenced by SCIPincludeDefaultPlugins().