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  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   TRUE
 
#define DEFAULT_ADDCLIQUE   FALSE
 
#define DEFAULT_ADDBINCONSROW   0
 
#define DEFAULT_USEDOMAINREDUCTION   TRUE
 
#define DEFAULT_MAXNVIOLATEDCONS   1
 
#define DEFAULT_MAXNVIOLATEDBINCONS   0
 
#define DEFAULT_MAXNVIOLATEDDOMREDS   0
 
#define DEFAULT_STOREUNVIOLATEDSOL   TRUE
 
#define DEFAULT_REEVALAGE   10LL
 
#define DEFAULT_RECURSIONDEPTH   2
 
#define DEFAULT_ADDNONVIOCONS   FALSE
 
#define DEFAULT_PROPAGATE   TRUE
 
#define DEFAULT_MAXPROPROUNDS   -1
 
#define DEFAULT_ABBREVIATED   FALSE
 
#define DEFAULT_MAXNCANDS   4
 
#define DEFAULT_REUSEBASIS   TRUE
 
#define DEFAULT_ABBREVPSEUDO   FALSE
 
#define DEFAULT_SCORINGFUNCTION   'd'
 
#define DEFAULT_MINWEIGHT   4.0
 
#define DEFAULT_MAXWEIGHT   1.0
 
#define LABdebugMessage(scip, lvl, ...)
 

Functions

static SCIP_RETCODE warmStartInfoCreate (SCIP *scip, WARMSTARTINFO **warmstartinfo)
 
static SCIP_Bool warmStartInfoIsReadable (WARMSTARTINFO *warmstartinfo)
 
static SCIP_RETCODE warmStartInfoFree (SCIP *scip, WARMSTARTINFO **warmstartinfo)
 
static SCIP_RETCODE candidateCreate (SCIP *scip, CANDIDATE **candidate, SCIP_Bool storelpi)
 
static SCIP_RETCODE candidateFree (SCIP *scip, CANDIDATE **candidate)
 
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 configurationCreate (SCIP *scip, CONFIGURATION **config)
 
static void configurationCopy (CONFIGURATION *config, CONFIGURATION *copysource)
 
static void configurationFree (SCIP *scip, CONFIGURATION **config)
 
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 SCIP_RETCODE 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 candidateListCreateWithCandidates (SCIP *scip, CANDIDATELIST **candidatelist, int ncandidates, SCIP_Bool storewarmstartinfo)
 
static SCIP_RETCODE candidateListGetAllFractionalCandidates (SCIP *scip, CANDIDATELIST **candidatelist, SCIP_Bool storewarmstartinfo)
 
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 scoreContainterResetBestSortedIndices (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)
 
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, SCIP_Bool storewarmstartinfo, int recursiondepth, SCIP_Real lpobjval, SCIP_Longint *niterations, int *ndeepestcutoffs, SCIP_Real *bestgain, SCIP_Real *totalgains, int *ntotalgains)
 
static SCIP_RETCODE selectVarStart (SCIP *scip, CONFIGURATION *config, PERSISTENTDATA *persistent, STATUS *status, BRANCHINGDECISION *decision, SCORECONTAINER *scorecontainer, SCIP_Bool storewarmstartinfo, CANDIDATELIST *candidatelist)
 
static void addLowerBoundProofNode (SCIP *scip, SCIP_VAR *var, SCIP_Real lowerbound, SCIP_SOL *baselpsol, DOMAINREDUCTIONS *domainreductions)
 
static void addLowerBound (SCIP *scip, SCIP_VAR *var, SCIP_Real lowerbound, SCIP_SOL *baselpsol, DOMAINREDUCTIONS *domainreductions)
 
static void addUpperBoundProofNode (SCIP *scip, SCIP_VAR *var, SCIP_Real upperbound, SCIP_SOL *baselpsol, DOMAINREDUCTIONS *domainreductions)
 
static void addUpperBound (SCIP *scip, SCIP_VAR *var, SCIP_Real upperbound, SCIP_SOL *baselpsol, DOMAINREDUCTIONS *domainreductions)
 
static void applySingleDeeperDomainReductions (SCIP *scip, SCIP_SOL *baselpsol, DOMAINREDUCTIONS *targetdomreds, DOMAINREDUCTIONS *domreds)
 
static void applyDeeperDomainReductions (SCIP *scip, SCIP_SOL *baselpsol, DOMAINREDUCTIONS *targetdomreds, DOMAINREDUCTIONS *downdomreds, DOMAINREDUCTIONS *updomreds)
 
static SCIP_RETCODE applyDomainReductions (SCIP *scip, 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, BRANCHINGDECISION *decision)
 
static SCIP_RETCODE storeWarmStartInfo (SCIP *scip, WARMSTARTINFO *warmstartinfo)
 
static SCIP_RETCODE restoreFromWarmStartInfo (SCIP *scip, WARMSTARTINFO *warmstartinfo)
 
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, CONFIGURATION *config, SCIP_VAR *branchvar)
 
static SCIP_RETCODE getOldBranching (SCIP *scip, PERSISTENTDATA *persistent, SCIP_VAR *branchvar, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult, SCIP_Real *oldlpobjval)
 
static SCIP_RETCODE updateOldBranching (SCIP *scip, PERSISTENTDATA *persistent, SCIP_VAR *branchvar, SCIP_Real branchval, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult, SCIP_Real lpobjval)
 
static SCIP_RETCODE getFSBResult (SCIP *scip, CONFIGURATION *parentconfig, CANDIDATELIST *candidatelist, STATUS *status, SCORECONTAINER *scorecontainer)
 
static SCIP_Real calculateScoreFromResult (SCIP *scip, SCIP_VAR *branchvar, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult, SCIP_Real lpobjval)
 
static SCIP_Real calculateWeightedGain (CONFIGURATION *config, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult, SCIP_Real lpobjval)
 
static SCIP_Real calculateScaledCutoffScore (BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult)
 
static SCIP_Real calculateScore (SCIP *scip, CONFIGURATION *config, SCIP_VAR *branchvar, BRANCHINGRESULTDATA *downbranchingresult, BRANCHINGRESULTDATA *upbranchingresult, SCIP_Real lpobjval)
 
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, CONFIGURATION *config, STATUS *status, CANDIDATELIST *allcandidates, SCORECONTAINER *scorecontainer)
 
static SCIP_RETCODE filterBestCandidates (SCIP *scip, CONFIGURATION *config, SCORECONTAINER *scorecontainer, CANDIDATELIST *candidatelist)
 
static SCIP_RETCODE getBestCandidates (SCIP *scip, CONFIGURATION *config, STATUS *status, CANDIDATELIST *candidatelist, SCORECONTAINER *scorecontainer)
 
static SCIP_RETCODE filterCandidates (SCIP *scip, CONFIGURATION *config, STATUS *status, SCORECONTAINER *scorecontainer, CANDIDATELIST *candidatelist)
 
static SCIP_RETCODE executeBranchingRecursive (SCIP *scip, STATUS *status, CONFIGURATION *config, SCIP_SOL *baselpsol, CANDIDATE *candidate, SCIP_Real localbaselpsolval, int recursiondepth, DOMAINREDUCTIONS *domainreductions, BINCONSDATA *binconsdata, BRANCHINGRESULTDATA *branchingresult, SCORECONTAINER *scorecontainer, SCIP_Bool storewarmstartinfo, SCIP_Bool downbranching)
 
static SCIP_Bool isStoreDecision (CONFIGURATION *config, BINCONSDATA *binconsdata, DOMAINREDUCTIONS *domainreductions)
 
static SCIP_Bool isUsePreviousResult (SCIP *scip, SCIP_SOL *currentsol, PERSISTENTDATA *persistent)
 
static SCIP_RETCODE usePreviousResult (SCIP *scip, BRANCHINGDECISION *decision, SCIP_RESULT *result)
 
static SCIP_RETCODE freePersistent (SCIP *scip, SCIP_BRANCHRULEDATA *branchruledata)
 
static SCIP_Bool isInitBranchruleData (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_BRANCHEXITSOL (branchExitSolLookahead)
 
static SCIP_DECL_BRANCHEXECLP (branchExeclpLookahead)
 
SCIP_RETCODE SCIPincludeBranchruleLookahead (SCIP *scip)
 

Macro Definition Documentation

◆ BRANCHRULE_NAME

#define BRANCHRULE_NAME   "lookahead"

Definition at line 74 of file branch_lookahead.c.

Referenced by SCIP_DECL_BRANCHEXITSOL().

◆ BRANCHRULE_DESC

#define BRANCHRULE_DESC   "full strong branching over multiple levels"

Definition at line 75 of file branch_lookahead.c.

◆ BRANCHRULE_PRIORITY

#define BRANCHRULE_PRIORITY   0

Definition at line 76 of file branch_lookahead.c.

◆ BRANCHRULE_MAXDEPTH

#define BRANCHRULE_MAXDEPTH   -1

Definition at line 77 of file branch_lookahead.c.

◆ BRANCHRULE_MAXBOUNDDIST

#define BRANCHRULE_MAXBOUNDDIST   1.0

Definition at line 78 of file branch_lookahead.c.

◆ DEFAULT_USEBINARYCONSTRAINTS

#define DEFAULT_USEBINARYCONSTRAINTS   TRUE

should binary constraints be collected and applied?

Definition at line 80 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 81 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 82 of file branch_lookahead.c.

◆ DEFAULT_USEDOMAINREDUCTION

#define DEFAULT_USEDOMAINREDUCTION   TRUE

Should domain reductions be collected and applied?

Definition at line 85 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 86 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 89 of file branch_lookahead.c.

◆ DEFAULT_MAXNVIOLATEDDOMREDS

#define DEFAULT_MAXNVIOLATEDDOMREDS   0

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 94 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 97 of file branch_lookahead.c.

◆ DEFAULT_REEVALAGE

#define DEFAULT_REEVALAGE   10LL

Max number of LPs solved after which a previous prob branching results are recalculated.

Definition at line 100 of file branch_lookahead.c.

◆ DEFAULT_RECURSIONDEPTH

#define DEFAULT_RECURSIONDEPTH   2

The max depth of LAB.

Definition at line 103 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 104 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 107 of file branch_lookahead.c.

◆ DEFAULT_MAXPROPROUNDS

#define DEFAULT_MAXPROPROUNDS   -1

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

Definition at line 110 of file branch_lookahead.c.

◆ DEFAULT_ABBREVIATED

#define DEFAULT_ABBREVIATED   FALSE

Toggles the abbreviated LAB.

Definition at line 113 of file branch_lookahead.c.

◆ DEFAULT_MAXNCANDS

#define DEFAULT_MAXNCANDS   4

If abbreviated: The max number of candidates to consider per node

Definition at line 114 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 115 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 118 of file branch_lookahead.c.

◆ DEFAULT_SCORINGFUNCTION

#define DEFAULT_SCORINGFUNCTION   'd'

default scoring function to be used

Definition at line 121 of file branch_lookahead.c.

◆ DEFAULT_MINWEIGHT

#define DEFAULT_MINWEIGHT   4.0

default value for the min weight to get a weighted score of two child gains (taken from the paper)

Definition at line 122 of file branch_lookahead.c.

◆ DEFAULT_MAXWEIGHT

#define DEFAULT_MAXWEIGHT   1.0

default value for the max weight to get a weighted score of two child gains (taken from the paper)

Definition at line 125 of file branch_lookahead.c.

◆ LABdebugMessage

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 184 of file branch_lookahead.c.

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

◆ warmStartInfoIsReadable()

static SCIP_Bool warmStartInfoIsReadable ( 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 204 of file branch_lookahead.c.

References NULL, SCIP_CALL, SCIPblkmem(), and SCIPgetLPI().

◆ 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 214 of file branch_lookahead.c.

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

Referenced by candidateFree(), and warmStartInfoCreate().

◆ candidateCreate()

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

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

Parameters
scipSCIP data structure
candidatethe candidate to allocate and initialize
storelpishould the candidate be able to store its lpi information?

Definition at line 257 of file branch_lookahead.c.

Referenced by candidateListCreateWithCandidates(), 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 286 of file branch_lookahead.c.

References SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfreeBlockMemory, and warmStartInfoFree().

Referenced by candidateListFree(), and candidateListKeep().

◆ branchingDecisionCreate()

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

Allocates a branching decision in the buffer and initiates it with default values.

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

Definition at line 331 of file branch_lookahead.c.

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 364 of file branch_lookahead.c.

References branchingDecisionEnsureBoundArraysSize(), BRANCHINGDECISION::cand, and NULL.

Referenced by selectVarStart().

◆ 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 382 of file branch_lookahead.c.

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

Referenced by selectVarStart().

◆ 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 394 of file branch_lookahead.c.

Referenced by branchingDecisionCopy(), and 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 417 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 460 of file branch_lookahead.c.

References BRANCHINGRESULTDATA::cutoff, 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 475 of file branch_lookahead.c.

References BRANCHINGRESULTDATA::cutoff, 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 496 of file branch_lookahead.c.

References NULL, and SCIPfreeBuffer.

◆ 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 517 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ configurationCreate()

static SCIP_RETCODE configurationCreate ( SCIP scip,
CONFIGURATION **  config 
)
static

allocates a configuration in the buffer

Parameters
scipSCIP data structure
configpointer to the configuration to allocate in initialize

Definition at line 589 of file branch_lookahead.c.

References CONFIGURATION::addbinconsrow, CONFIGURATION::addnonviocons, CONFIGURATION::forcebranching, CONFIGURATION::maxnviolatedbincons, CONFIGURATION::maxnviolatedcons, CONFIGURATION::maxnviolateddomreds, and NULL.

◆ configurationCopy()

static void configurationCopy ( CONFIGURATION config,
CONFIGURATION copysource 
)
static

copies the fields from configuration copysource to config

Parameters
configpointer to the configuration to allocate in initialize
copysourcecopy the settings from this config

Definition at line 604 of file branch_lookahead.c.

References NULL, and SCIPfreeBuffer.

◆ configurationFree()

◆ 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 1026 of file branch_lookahead.c.

References NULL.

Referenced by configurationFree().

◆ 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 1051 of file branch_lookahead.c.

References constraintListFree(), CONSTRAINTLIST::consvars, CONSTRAINTLIST::memorysize, CONSTRAINTLIST::nconsvars, CONSTRAINTLIST::nelements, NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPduplicateBlockMemoryArray, SCIPfreeBlockMemoryArray, SCIPreallocBufferArray, 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 1086 of file branch_lookahead.c.

Referenced by 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 1123 of file branch_lookahead.c.

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

◆ binaryVarListAppend()

static SCIP_RETCODE 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 1145 of file branch_lookahead.c.

References 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 1166 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 1180 of file branch_lookahead.c.

References 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 1201 of file branch_lookahead.c.

Referenced by binaryVarListFree(), and selectVarStart().

◆ 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 1222 of file branch_lookahead.c.

References candidateListCreate().

Referenced by selectVarStart().

◆ 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 1246 of file branch_lookahead.c.

Referenced by binConsDataFree().

◆ candidateListCreateWithCandidates()

static SCIP_RETCODE candidateListCreateWithCandidates ( SCIP scip,
CANDIDATELIST **  candidatelist,
int  ncandidates,
SCIP_Bool  storewarmstartinfo 
)
static
Parameters
scipSCIP data structure
candidatelistthe candidate list to allocate
ncandidatesthe number of candidates the list must hold
storewarmstartinfoshould the candidates be able to store warm start information?

Definition at line 1272 of file branch_lookahead.c.

References candidateCreate(), candidateListGetAllFractionalCandidates(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, and SCIP_Real.

◆ candidateListGetAllFractionalCandidates()

static SCIP_RETCODE candidateListGetAllFractionalCandidates ( SCIP scip,
CANDIDATELIST **  candidatelist,
SCIP_Bool  storewarmstartinfo 
)
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
storewarmstartinfoshould warm start info of the LP be stored in the candidates?

Definition at line 1297 of file branch_lookahead.c.

Referenced by candidateListCreateWithCandidates(), and 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 1336 of file branch_lookahead.c.

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

Referenced by 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 1367 of file branch_lookahead.c.

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

Referenced by candidateListFree().

◆ 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 1413 of file branch_lookahead.c.

Referenced by selectVarRecursive(), and selectVarStart().

◆ 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 1454 of file branch_lookahead.c.

Referenced by selectVarRecursive(), and selectVarStart().

◆ 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 1488 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 1512 of file branch_lookahead.c.

References NULL.

Referenced by executeBranchingRecursive().

◆ scoreContainterResetBestSortedIndices()

static void scoreContainterResetBestSortedIndices ( SCORECONTAINER scorecontainer)
static

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

Parameters
scorecontainerthe score container to reset

Definition at line 1532 of file branch_lookahead.c.

References NULL.

◆ 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 1543 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 1579 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 1624 of file branch_lookahead.c.

References SCORECONTAINER::bestsortedcands, NULL, SCIP_Real, and scoreContainerSetScore().

◆ scoreContainerSetScore()

static SCIP_RETCODE scoreContainerSetScore ( SCIP scip,
SCORECONTAINER scorecontainer,
CANDIDATE cand,
SCIP_Real  score 
)
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

Definition at line 1649 of file branch_lookahead.c.

Referenced by scoreContainerUpdateSortOrder(), 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 1693 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,
SCIP_Bool  storewarmstartinfo,
int  recursiondepth,
SCIP_Real  lpobjval,
SCIP_Longint niterations,
int *  ndeepestcutoffs,
SCIP_Real bestgain,
SCIP_Real totalgains,
int *  ntotalgains 
)
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
storewarmstartinfoshould LP information be stored?
recursiondepthremaining recursion depth
lpobjvalbase LP objective value
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

Definition at line 3978 of file branch_lookahead.c.

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

Referenced by executeBranchingRecursive(), and selectVarStart().

◆ selectVarStart()

static SCIP_RETCODE selectVarStart ( SCIP scip,
CONFIGURATION config,
PERSISTENTDATA persistent,
STATUS status,
BRANCHINGDECISION decision,
SCORECONTAINER scorecontainer,
SCIP_Bool  storewarmstartinfo,
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
statuscurrent status
decisionstruct to store the final decision
scorecontainercontainer to retrieve already calculated scores
storewarmstartinfoshould lp information be stored?
candidatelistlist of candidates to branch on

Definition at line 4494 of file branch_lookahead.c.

References CONFIGURATION::abbreviated, STATUS::addedbinconss, applyBinaryConstraints(), applyDomainReductions(), BINCONSDATA::binaryvars, binConsDataCreate(), binConsDataFree(), branchingDecisionCopy(), branchingDecisionIsValid(), CANDIDATE::branchvar, BRANCHINGDECISION::cand, CANDIDATELIST::candidates, BINCONSDATA::conslist, copyCurrentSolution(), STATUS::cutoff, STATUS::depthtoosmall, domainReductionsCreate(), domainReductionsFree(), STATUS::domred, STATUS::domredcutoff, BRANCHINGDECISION::downdb, BRANCHINGDECISION::downdbvalid, FALSE, filterCandidates(), CONFIGURATION::forcebranching, isBranchFurther(), isStoreDecision(), isUsePreviousResult(), LABdebugMessage, BINARYVARLIST::nbinaryvars, CANDIDATELIST::ncandidates, NULL, PERSISTENTDATA::prevbinsolution, PERSISTENTDATA::prevdecision, BRANCHINGDECISION::proveddb, CONFIGURATION::recursiondepth, SCIP_Bool, SCIP_CALL, SCIP_MAXTREEDEPTH, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPABORT, SCIPareSolsEqual(), SCIPceil(), SCIPenableVarHistory(), SCIPendStrongbranch(), SCIPfreeSol(), SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetProbingDepth(), SCIPinProbing(), SCIPlinkLPSol(), SCIPstartStrongbranch(), SCIPunlinkSol(), SCIPvarGetName(), selectVarRecursive(), TRUE, BRANCHINGDECISION::updb, BRANCHINGDECISION::updbvalid, CONFIGURATION::usebincons, and CONFIGURATION::usedomainreduction.

◆ addLowerBoundProofNode()

static void addLowerBoundProofNode ( SCIP scip,
SCIP_VAR var,
SCIP_Real  lowerbound,
SCIP_SOL baselpsol,
DOMAINREDUCTIONS domainreductions 
)
static

Adds the given lower bound to the container 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.
domainreductionsThe struct the domain reduction should be added to.

Definition at line 1759 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ addLowerBound()

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

Add a lower bound to the DOMAINREDUCTIONS struct. This is used as a wrapper to the 'addLowerBoundProofNode' method.

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.
domainreductionsThe struct the domain reduction should be added to.

Definition at line 1819 of file branch_lookahead.c.

◆ addUpperBoundProofNode()

static void addUpperBoundProofNode ( SCIP scip,
SCIP_VAR var,
SCIP_Real  upperbound,
SCIP_SOL baselpsol,
DOMAINREDUCTIONS domainreductions 
)
static

Adds the given upper bound to the container 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.
domainreductionsThe struct the domain reduction should be added to.

Definition at line 1840 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ addUpperBound()

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

Add a lower bound to the DOMAINREDUCTIONS struct. This is used as a wrapper to the 'addUpperBoundProofNode' method.

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.
domainreductionsThe struct the domain reduction should be added to.

Definition at line 1902 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ applySingleDeeperDomainReductions()

static void applySingleDeeperDomainReductions ( SCIP scip,
SCIP_SOL baselpsol,
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.
targetdomredsThe target that should be filled with the merged data.
domredssource domain reductions

Definition at line 1925 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ applyDeeperDomainReductions()

static void applyDeeperDomainReductions ( SCIP scip,
SCIP_SOL baselpsol,
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.
targetdomredsThe target that should be filled with the merged data.
downdomredsOne of the source DOMAINREDUCTIONS.
updomredsThe other source DOMAINREDUCTIONS.

Definition at line 1968 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ applyDomainReductions()

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

Applies the domain reductions to the current node.

Parameters
scipSCIP data structure
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 2039 of file branch_lookahead.c.

Referenced by selectVarStart().

◆ 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 2208 of file branch_lookahead.c.

References CANDIDATE::branchvar, BRANCHINGDECISION::cand, NULL, and SCIP_Real.

Referenced by selectVarStart().

◆ branchOnVar()

static SCIP_RETCODE branchOnVar ( SCIP scip,
BRANCHINGDECISION decision 
)
static

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

Parameters
scipSCIP data structure
decisionthe decision with all the needed data

Definition at line 2227 of file branch_lookahead.c.

Referenced by isUsePreviousResult().

◆ storeWarmStartInfo()

static SCIP_RETCODE storeWarmStartInfo ( SCIP scip,
WARMSTARTINFO warmstartinfo 
)
static

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

Parameters
scipSCIP data structure
warmstartinfothe warm start info in which the data should be stored

Definition at line 2355 of file branch_lookahead.c.

Referenced by executeBranchingRecursive().

◆ restoreFromWarmStartInfo()

static SCIP_RETCODE restoreFromWarmStartInfo ( SCIP scip,
WARMSTARTINFO warmstartinfo 
)
static

Sets the lp state and norms of the current node to the values stored in the warm start info.

Parameters
scipSCIP data structure
warmstartinfothe warm start info containing the stored data

Definition at line 2386 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 2411 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 2435 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 2639 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 2682 of file branch_lookahead.c.

References addBinaryConstraint(), 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 2715 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 2785 of file branch_lookahead.c.

Referenced by selectVarStart().

◆ 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 2914 of file branch_lookahead.c.

References STATUS::cutoff, STATUS::domred, STATUS::limitreached, STATUS::lperror, STATUS::maxnconsreached, and NULL.

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 2934 of file branch_lookahead.c.

References FALSE, NULL, and SCIP_Bool.

Referenced by executeBranchingRecursive(), and selectVarStart().

◆ 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 2948 of file branch_lookahead.c.

References NULL, CONFIGURATION::reevalage, SCIPgetNNodes(), SCIPgetVarStrongbranchLPAge(), and SCIPgetVarStrongbranchNode().

Referenced by selectVarRecursive().

◆ isUseOldBranching()

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

Determines whether previous branching results of a variable can be reused

Parameters
scipSCIP data structure
configthe configuration of the branching rule
branchvarvariable to check

Definition at line 2968 of file branch_lookahead.c.

References NULL.

Referenced by selectVarRecursive().

◆ getOldBranching()

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

Retrieves previous branching results for the given variable

Parameters
scipSCIP data structure
persistentdata storage over multiple calls to the rulel
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 2985 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ updateOldBranching()

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

Stores the data for use in a later call to the branching rule

Parameters
scipSCIP data structure
persistentdata storage over multiple calls to the 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 3036 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ getFSBResult()

static SCIP_RETCODE getFSBResult ( SCIP scip,
CONFIGURATION parentconfig,
CANDIDATELIST candidatelist,
STATUS status,
SCORECONTAINER scorecontainer 
)
static

calculates the FSB scores for the given candidates

Parameters
scipSCIP data structure
parentconfigmain configuration
candidatelistthe candidates to get the scores for
statusstatus getting updated by the FSB routine
scorecontainercontainer for the scores and lpi information

Definition at line 3073 of file branch_lookahead.c.

◆ 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 3186 of file branch_lookahead.c.

◆ calculateWeightedGain()

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

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

Parameters
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 3227 of file branch_lookahead.c.

Referenced by selectVarRecursive().

◆ 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 3266 of file branch_lookahead.c.

◆ calculateScore()

static SCIP_Real calculateScore ( SCIP scip,
CONFIGURATION config,
SCIP_VAR branchvar,
BRANCHINGRESULTDATA downbranchingresult,
BRANCHINGRESULTDATA upbranchingresult,
SCIP_Real  lpobjval 
)
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

Definition at line 3295 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 3330 of file branch_lookahead.c.

◆ 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 3379 of file branch_lookahead.c.

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

◆ 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 3444 of file branch_lookahead.c.

Referenced by 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 3466 of file branch_lookahead.c.

◆ ensureScoresPresent()

static SCIP_RETCODE ensureScoresPresent ( SCIP scip,
CONFIGURATION config,
STATUS status,
CANDIDATELIST allcandidates,
SCORECONTAINER scorecontainer 
)
static

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

Parameters
scipSCIP data structure
configmain configuration
statuscurrent status
allcandidateslist containing all candidates to consider
scorecontainercontainer to store the scores for later usage

Definition at line 3477 of file branch_lookahead.c.

◆ filterBestCandidates()

static SCIP_RETCODE filterBestCandidates ( SCIP scip,
CONFIGURATION config,
SCORECONTAINER scorecontainer,
CANDIDATELIST candidatelist 
)
static

Gets the best candidates w.r.t. the scores stored in the scorecontainer and stores them in the given list

Parameters
scipSCIP data structure
configthe configuration of the branching rule
scorecontainercontainer to store the scores for later usage
candidatelistlist containing all candidates to consider

Definition at line 3594 of file branch_lookahead.c.

◆ getBestCandidates()

static SCIP_RETCODE getBestCandidates ( SCIP scip,
CONFIGURATION config,
STATUS status,
CANDIDATELIST candidatelist,
SCORECONTAINER scorecontainer 
)
static

Gets the best candidates, according the FSB score of each candidate

Parameters
scipSCIP data structure
configthe configuration of the branching rule
statuscurrent status
candidatelistlist containing all candidates to consider
scorecontainercontainer to store the scores for later usage

Definition at line 3636 of file branch_lookahead.c.

◆ filterCandidates()

static SCIP_RETCODE filterCandidates ( SCIP scip,
CONFIGURATION config,
STATUS status,
SCORECONTAINER scorecontainer,
CANDIDATELIST candidatelist 
)
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
configthe configuration of the branching rule
statuscurrent status
scorecontainercontainer to store the scores for later usage; or NULL if not running the abbreviated version of lookahead branching
candidatelistlist with the candidates

Definition at line 3697 of file branch_lookahead.c.

Referenced by executeBranchingRecursive(), and selectVarStart().

◆ executeBranchingRecursive()

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

Executes the general branching on a node 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
recursiondepthremaining recursion depth
domainreductionscontainer collecting all domain reductions found
binconsdatacontainer collecting all binary constraints
branchingresultcontainer to store the result of the branching in
scorecontainercontainer to retrieve already calculated scores; or NULL
storewarmstartinfoshould lp information be stored?
downbranchingshould we branch up or down in here?

Definition at line 3736 of file branch_lookahead.c.

References CONFIGURATION::abbreviated, addBinaryConstraint(), BRANCHINGRESULTDATA::bestgain, binaryVarListAppend(), binaryVarListDrop(), BINCONSDATA::binaryvars, branchingDecisionCreate(), branchingDecisionFree(), CANDIDATE::branchval, CANDIDATE::branchvar, candidateListFree(), candidateListGetAllFractionalCandidates(), BRANCHINGRESULTDATA::cutoff, STATUS::cutoff, CANDIDATE::downwarmstartinfo, BRANCHINGRESULTDATA::dualbound, BRANCHINGRESULTDATA::dualboundvalid, executeBranching(), FALSE, filterCandidates(), CANDIDATE::fracval, isBranchFurther(), LABdebugMessage, STATUS::limitreached, STATUS::lperror, MAX, BINARYVARLIST::nbinaryvars, CANDIDATELIST::ncandidates, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::niterations, BRANCHINGRESULTDATA::ntotalgains, NULL, BRANCHINGRESULTDATA::objval, BRANCHINGDECISION::proveddb, CONFIGURATION::reusebasis, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIPallColsInLP(), SCIPbacktrackProbing(), SCIPgetNegatedVar(), SCIPgetProbingDepth(), SCIPisGE(), SCIPupdateVarPseudocost(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), selectVarRecursive(), statusCreate(), statusFree(), storeWarmStartInfo(), BRANCHINGRESULTDATA::totalgains, TRUE, CANDIDATE::upwarmstartinfo, and CONFIGURATION::usebincons.

Referenced by 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 4474 of file branch_lookahead.c.

Referenced by selectVarRecursive(), and selectVarStart().

◆ isUsePreviousResult()

static SCIP_Bool isUsePreviousResult ( SCIP scip,
SCIP_SOL currentsol,
PERSISTENTDATA persistent 
)
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
currentsolthe current base lp solution
persistentcontainer to store data over multiple calls to the branching rule

Definition at line 4756 of file branch_lookahead.c.

References branchOnVar(), LABdebugMessage, NULL, SCIP_CALL, and SCIP_VERBLEVEL_FULL.

Referenced by selectVarStart().

◆ usePreviousResult()

static SCIP_RETCODE usePreviousResult ( SCIP scip,
BRANCHINGDECISION decision,
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
decisiondecision to branch on
resultthe pointer to the branching result

Definition at line 4780 of file branch_lookahead.c.

◆ freePersistent()

◆ isInitBranchruleData()

static SCIP_Bool isInitBranchruleData ( SCIP scip,
SCIP_BRANCHRULEDATA branchruledata 
)
static

checks whether the branchruledata struct has to be (re-)initialized

Parameters
scipSCIP data structure
branchruledatabranch rule data that may get initialized

Definition at line 4856 of file branch_lookahead.c.

References NULL.

Referenced by freePersistent().

◆ 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 4871 of file branch_lookahead.c.

◆ SCIP_DECL_BRANCHCOPY()

static SCIP_DECL_BRANCHCOPY ( branchCopyLookahead  )
static

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

Definition at line 4929 of file branch_lookahead.c.

References NULL, SCIPbranchruleGetData(), and SCIPfreeBlockMemory.

◆ 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 4942 of file branch_lookahead.c.

◆ SCIP_DECL_BRANCHINIT()

static SCIP_DECL_BRANCHINIT ( branchInitLookahead  )
static

◆ 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 5047 of file branch_lookahead.c.

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

Referenced by SCIP_DECL_BRANCHINIT().

◆ SCIP_DECL_BRANCHEXECLP()

static SCIP_DECL_BRANCHEXECLP ( branchExeclpLookahead  )
static

branching execution method for fractional LP solutions

Definition at line 5064 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 5266 of file branch_lookahead.c.

Referenced by SCIPincludeDefaultPlugins().