SCIP
Solving Constraint Integer Programs
branch_lookahead.c File Reference
Detailed Description
lookahead LP branching rule
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 |
Macro Definition Documentation
◆ BRANCHRULE_NAME
| #define BRANCHRULE_NAME "lookahead" |
Definition at line 75 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 76 of file branch_lookahead.c.
◆ BRANCHRULE_PRIORITY
| #define BRANCHRULE_PRIORITY 0 |
Definition at line 77 of file branch_lookahead.c.
◆ BRANCHRULE_MAXDEPTH
| #define BRANCHRULE_MAXDEPTH -1 |
Definition at line 78 of file branch_lookahead.c.
◆ BRANCHRULE_MAXBOUNDDIST
| #define BRANCHRULE_MAXBOUNDDIST 1.0 |
Definition at line 79 of file branch_lookahead.c.
◆ DEFAULT_USEBINARYCONSTRAINTS
| #define DEFAULT_USEBINARYCONSTRAINTS FALSE |
should binary constraints be collected and applied?
Definition at line 81 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 82 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 83 of file branch_lookahead.c.
◆ DEFAULT_USEDOMAINREDUCTION
| #define DEFAULT_USEDOMAINREDUCTION TRUE |
Should domain reductions be collected and applied?
Definition at line 86 of file branch_lookahead.c.
◆ DEFAULT_MERGEDOMAINREDUCTIONS
| #define DEFAULT_MERGEDOMAINREDUCTIONS FALSE |
should domain reductions of feasible siblings should be merged?
Definition at line 87 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 88 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 89 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 90 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 93 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 98 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 101 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 104 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 107 of file branch_lookahead.c.
◆ DEFAULT_RECURSIONDEPTH
| #define DEFAULT_RECURSIONDEPTH 2 |
The max depth of LAB.
Definition at line 110 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 111 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 114 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 117 of file branch_lookahead.c.
◆ DEFAULT_APPLYCHILDBOUNDS
| #define DEFAULT_APPLYCHILDBOUNDS FALSE |
should bounds known for child nodes be applied?
Definition at line 118 of file branch_lookahead.c.
◆ DEFAULT_ENFORCEMAXDOMREDS
| #define DEFAULT_ENFORCEMAXDOMREDS FALSE |
should the maximum number of domain reductions maxnviolateddomreds be enforced?
Definition at line 119 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 120 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 121 of file branch_lookahead.c.
◆ DEFAULT_ABBREVIATED
| #define DEFAULT_ABBREVIATED TRUE |
Toggles the abbreviated LAB.
Definition at line 124 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 125 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 126 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 129 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 132 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 135 of file branch_lookahead.c.
◆ DEFAULT_LEVEL2ZEROSCORE
| #define DEFAULT_LEVEL2ZEROSCORE FALSE |
should uninitialized scores be set to 0?
Definition at line 136 of file branch_lookahead.c.
◆ DEFAULT_SCORINGFUNCTION
| #define DEFAULT_SCORINGFUNCTION 'a' |
scoring function to be used at the base level
Definition at line 137 of file branch_lookahead.c.
◆ DEFAULT_DEEPERSCORINGFUNCTION
| #define DEFAULT_DEEPERSCORINGFUNCTION 'x' |
scoring function to be used at deeper levels
Definition at line 138 of file branch_lookahead.c.
◆ DEFAULT_SCORINGSCORINGFUNCTION
| #define DEFAULT_SCORINGSCORINGFUNCTION 'd' |
scoring function to be used for FSB scoring
Definition at line 139 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 140 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 143 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 144 of file branch_lookahead.c.
◆ LABdebugMessage
| #define LABdebugMessage | ( | scip, | |
| lvl, | |||
| ... | |||
| ) |
Definition at line 181 of file branch_lookahead.c.
Referenced by candidateCreate(), candidateFreeWarmStartInfo(), candidateHasWarmStartInfo(), ensureScoresPresent(), executeBranchingRecursive(), filterCandidates(), initBranchruleData(), level2dataStoreResult(), level2resultCreateFromData(), SCIP_DECL_BRANCHEXITSOL(), SCIP_DECL_BRANCHFREE(), SCIP_DECL_BRANCHINIT(), selectVarRecursive(), and sortFirstCandidatesByScore().
◆ level2resultPrint
| #define level2resultPrint | ( | scip, | |
| result | |||
| ) |
Definition at line 773 of file branch_lookahead.c.
Referenced by level2dataStoreResult(), and level2resultCreateFromData().
Function Documentation
◆ warmStartInfoCreate()
|
static |
Allocates the warm start information on the buffer and initializes it with default values.
- Parameters
-
scip SCIP data structure warmstartinfo the warmstartinfo to allocate and initialize
Definition at line 201 of file branch_lookahead.c.
References WARMSTARTINFO::lpistate, NULL, and warmStartInfoFree().
Referenced by candidateStoreWarmStartInfo().
◆ warmStartInfoIsAvailable()
|
static |
checks that the warm start info can be read into the lp solver.
- Parameters
-
warmstartinfo the warm start info to check (may be NULL)
Definition at line 221 of file branch_lookahead.c.
Referenced by candidateStoreWarmStartInfo().
◆ warmStartInfoFree()
|
static |
Frees the allocated buffer memory of the warm start info.
- Parameters
-
scip SCIP data structure warmstartinfo the warm start info to free
Definition at line 230 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 |
Allocates the candidate on the buffer and initializes it with default values.
- Parameters
-
scip SCIP data structure candidate the candidate to allocate and initialize
Definition at line 271 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 |
free the warm starting information for the given candidate
- Parameters
-
scip SCIP data structure candidate the candidate to free the warm starting information for
Definition at line 290 of file branch_lookahead.c.
References candidateFree(), CANDIDATE::downwarmstartinfo, LABdebugMessage, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIPvarGetName(), and warmStartInfoFree().
◆ candidateFree()
|
static |
Frees the allocated buffer memory of the candidate and clears the contained lpi memories.
- Parameters
-
scip SCIP data structure candidate the candidate to free
Definition at line 317 of file branch_lookahead.c.
Referenced by candidateFreeWarmStartInfo(), candidateListFree(), and candidateListKeep().
◆ candidateStoreWarmStartInfo()
|
static |
Store the current lp solution in the warm start info for further usage.
- Parameters
-
scip SCIP data structure candidate the branching candidate down is the info for down branching?
Definition at line 338 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()
returns whether the candidate has stored warm starting information for the given direction
- Parameters
-
candidate the branching candidate down is the info for down branching?
Definition at line 386 of file branch_lookahead.c.
References CANDIDATE::downwarmstartinfo, LABdebugMessage, NULL, and SCIP_VERBLEVEL_HIGH.
Referenced by candidateStoreWarmStartInfo().
◆ candidateLoadWarmStartInfo()
|
static |
loads the warm starting information of the candidate for the given direction
- Parameters
-
scip SCIP data structure candidate the branching candidate down is the info for down branching?
Definition at line 399 of file branch_lookahead.c.
Referenced by candidateStoreWarmStartInfo().
◆ branchingDecisionInit()
|
static |
initialize a branching decsion with default values
- Parameters
-
scip SCIP data structure decision the decision to initialize
Definition at line 457 of file branch_lookahead.c.
Referenced by initBranchruleData().
◆ branchingDecisionCreate()
|
static |
allocates a branching decision in the buffer and initializes it with default values.
- Parameters
-
scip SCIP data structure decision pointer to the decision to allocate and initialize
Definition at line 484 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 |
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
-
sourcedecision the source branching decision targetdecision the target branching decision
Definition at line 507 of file branch_lookahead.c.
◆ branchingDecisionIsValid()
|
static |
Checks whether the given branching decision can be used to branch on.
- Parameters
-
decision the branching decision to check
Definition at line 534 of file branch_lookahead.c.
References BRANCHINGDECISION::boundssize, BRANCHINGDECISION::downlowerbounds, BRANCHINGDECISION::downupperbounds, NULL, SCIP_CALL, SCIPallocBlockMemoryArray, BRANCHINGDECISION::uplowerbounds, and BRANCHINGDECISION::upupperbounds.
◆ branchingDecisionEnsureBoundArraysSize()
|
static |
- Parameters
-
scip SCIP data structure decision branching decision nvars number of problem variables
Definition at line 546 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ branchingDecisionFree()
|
static |
Frees the allocated memory of the branching decision.
- Parameters
-
scip SCIP data structure decision pointer to the decision to be freed
Definition at line 569 of file branch_lookahead.c.
Referenced by executeBranchingRecursive().
◆ branchingResultDataCreate()
|
static |
Allocates a branching result in the buffer.
- Parameters
-
scip SCIP data structure resultdata pointer to the result to be allocated
Definition at line 614 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 |
Initiates the branching result with default values.
- Parameters
-
scip SCIP data structure resultdata pointer to the result to be initialized
Definition at line 629 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 |
Copies the data from the source to the target.
- Parameters
-
sourcedata the source branching result targetdata the target branching result
Definition at line 652 of file branch_lookahead.c.
References NULL, SCIP_Real, and SCIPfreeBuffer.
Referenced by selectVarRecursive().
◆ branchingResultDataFree()
|
static |
Frees the allocated buffer memory of the branching result.
- Parameters
-
scip SCIP data structure resultdata pointer to the result to be freed
Definition at line 675 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ level2resultCreateFromData()
|
static |
allocates a double branching result in the memory and fills it with the information stored in the level 2 data
- Parameters
-
scip SCIP data structure data level2 data result pointer to the result to be allocated
Definition at line 717 of file branch_lookahead.c.
References LEVEL2RESULT::branchdir1, LEVEL2DATA::branchdir1, LEVEL2RESULT::branchdir2, LEVEL2DATA::branchdir2, LEVEL2RESULT::branchval1, LEVEL2DATA::branchval1, LEVEL2RESULT::branchval2, LEVEL2DATA::branchval2, LEVEL2RESULT::branchvar1, LEVEL2DATA::branchvar1, LEVEL2RESULT::branchvar2, LEVEL2DATA::branchvar2, LEVEL2RESULT::cutoff, LABdebugMessage, level2resultFree(), level2resultPrint, LEVEL2RESULT::lpobjval, NULL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPfreeBlockMemory, SCIPgetVars(), SCIPvarGetName(), and LEVEL2RESULT::valid.
Referenced by level2dataGetResult(), and level2dataStoreResult().
◆ level2resultFree()
|
static |
frees the allocated memory of the double branching result
- Parameters
-
scip SCIP data structure result pointer to the result to be freed
Definition at line 778 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 |
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
-
result1 first level 2 result result2 second level 2 result
Definition at line 793 of file branch_lookahead.c.
References NULL, SCIP_CALL, SCIPallocBlockMemory(), and SCIPinfinity().
Referenced by level2dataGetResult(), and level2dataStoreResult().
◆ level2dataCreate()
|
static |
allocates the level2 data
- Parameters
-
scip SCIP data structure data pointer to the data to be allocated
Definition at line 817 of file branch_lookahead.c.
References level2resultFree(), and NULL.
◆ level2dataFree()
|
static |
frees the allocated memory of the level2 data
- Parameters
-
scip SCIP data structure data pointer to the data to be freed
Definition at line 842 of file branch_lookahead.c.
References level2dataEnsureSize(), LEVEL2DATA::level2results, LEVEL2DATA::level2resultssize, LEVEL2DATA::nlevel2results, NULL, SCIP_CALL, SCIPcalcMemGrowSize(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPreallocBlockMemoryArray.
◆ level2dataEnsureSize()
|
static |
ensures that level2results can store at least one more element
- Parameters
-
scip SCIP data structure data level2 data
Definition at line 867 of file branch_lookahead.c.
References NULL.
Referenced by level2dataFree(), and level2dataStoreResult().
◆ level2dataGetResult()
|
static |
get a result from the level 2 data
- Parameters
-
scip SCIP data structure data level2 data result pointer to store result
Definition at line 888 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 |
store a new result in the level 2 data
- Parameters
-
scip SCIP data structure data level2 data lpobjval LP objective value cutoff was the LP infeasible? valid is the LP value a valid dual bound? duplicate pointer to store whether information for the same branching decisions was already stored
Definition at line 928 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 |
Allocate and initialize the list holding the constraints.
- Parameters
-
scip SCIP data structure conslist Pointer to the list to be allocated and initialized. startsize The number of entries the list initially can hold.
Definition at line 1359 of file branch_lookahead.c.
References CONSTRAINTLIST::memorysize, CONSTRAINTLIST::nelements, and NULL.
◆ constraintListAppend()
|
static |
Append an element to the end of the list of constraints.
- Parameters
-
scip SCIP data structure list list to add the consvars to consvars array of variables for the constraint to be created later nconsvars number of elements in 'consvars' violated indicates whether the constraint is violated by the base lp
Definition at line 1384 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 |
Free all resources of a constraint list in opposite order to the allocation.
- Parameters
-
scip SCIP data structure conslist Pointer to the list to be freed.
Definition at line 1419 of file branch_lookahead.c.
Referenced by binConsDataCreate(), and constraintListAppend().
◆ binaryVarListCreate()
|
static |
Allocates and initializes the BINARYVARLIST struct.
- Parameters
-
scip SCIP data structure list Pointer to the list to be allocated and initialized. startsize The number of entries the list initially can hold.
Definition at line 1456 of file branch_lookahead.c.
References BINARYVARLIST::binaryvars, BINARYVARLIST::memorysize, BINARYVARLIST::nbinaryvars, NULL, and SCIPvarIsBinary().
◆ binaryVarListAppend()
|
static |
Appends a binary variable to the list, reallocating the list if necessary.
- Parameters
-
scip SCIP data structure list The list to add the var to. vartoadd The binary var to add to the list.
Definition at line 1478 of file branch_lookahead.c.
References binaryVarListFree(), BINARYVARLIST::binaryvars, BINARYVARLIST::nbinaryvars, and NULL.
Referenced by executeBranchingRecursive().
◆ binaryVarListDrop()
|
static |
Remove the last element from the list.
- Parameters
-
list The list to remove the last element from.
Definition at line 1497 of file branch_lookahead.c.
References NULL, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by executeBranchingRecursive().
◆ binaryVarListFree()
|
static |
Frees all resources allocated by a BINARYVARLIST in opposite order of allocation.
- Parameters
-
scip SCIP data structure list Pointer to the list to free
Definition at line 1511 of file branch_lookahead.c.
Referenced by binaryVarListAppend(), and binConsDataCreate().
◆ binConsDataCreate()
|
static |
Allocate and initialize the BINCONSDATA struct.
- Parameters
-
scip SCIP data structure consdata Pointer to the struct to be allocated and initialized. maxdepth The depth of the recursion as an upper bound of branch vars to hold. nstartcons The start size of the array containing the constraints.
Definition at line 1532 of file branch_lookahead.c.
References binaryVarListFree(), constraintListFree(), NULL, and SCIPfreeBuffer.
◆ binConsDataFree()
|
static |
Free all resources in a BINCONSDATA in opposite order of allocation.
- Parameters
-
scip SCIP data structure consdata Pointer to the struct to be freed.
Definition at line 1553 of file branch_lookahead.c.
References candidateListCreate().
◆ candidateListCreate()
|
static |
allocates the candidate list on the buffer WITHOUT initializing the contained array of candidates.
- Parameters
-
scip SCIP data structure candidatelist the candidate list to allocate ncandidates the number of candidates the list must hold
Definition at line 1577 of file branch_lookahead.c.
Referenced by binConsDataFree(), and ensureScoresPresent().
◆ candidateListGetAllFractionalCandidates()
|
static |
allocates the given list and fills it with all fractional candidates of the current LP solution.
- Parameters
-
scip SCIP data structure candidatelist the list to allocate and fill
Definition at line 1603 of file branch_lookahead.c.
Referenced by executeBranchingRecursive().
◆ candidateListFree()
|
static |
frees the allocated buffer memory of the candidate list and frees the contained candidates.
- Parameters
-
scip SCIP data structure candidatelist the list to be freed
Definition at line 1648 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 |
keeps only the first candidates and frees the remaining ones
- Parameters
-
scip SCIP data structure candidatelist the list to allocate and fill nindices the number of candidates to keep (starting from 0)
Definition at line 1679 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 |
allocate the struct on the buffer and initialize it with the default values
- Parameters
-
scip SCIP data structure domreds The struct that has to be allocated and initialized.
Definition at line 1726 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ domainReductionsFree()
|
static |
frees the given DOMAINREDUCTIONS and all contained Arrays in the opposite order of allocation
- Parameters
-
scip SCIP data structure domreds Pointer to the struct to be freed.
Definition at line 1768 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ statusCreate()
|
static |
Allocates the status on the buffer memory and initializes it with default values.
- Parameters
-
scip SCIP data structure status the status to be allocated
Definition at line 1802 of file branch_lookahead.c.
References NULL, SCIP_Real, and SCIPfreeBuffer.
Referenced by executeBranchingRecursive().
◆ statusFree()
frees the allocated buffer memory of the status
- Parameters
-
scip SCIP data structure status the status to be freed
Definition at line 1826 of file branch_lookahead.c.
Referenced by executeBranchingRecursive().
◆ scoreContainterResetBestSortedCands()
|
static |
resets the array containing the sorted indices w.r.t. their score.
- Parameters
-
scorecontainer the score container to reset
Definition at line 1850 of file branch_lookahead.c.
References NULL.
Referenced by ensureScoresPresent().
◆ scoreContainerCreate()
|
static |
allocates the score container and inits it with default values
- Parameters
-
scip SCIP data structure scorecontainer pointer to the score container to init config config struct with the user configuration
Definition at line 1861 of file branch_lookahead.c.
◆ findInsertionPoint()
|
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
-
scip SCIP data structure scorecontainer container with all the scores for each candidate scoretoinsert score to find the insertion index for candidates candidate list where the first nsorted elements are sorted (w.r.t. their score) ncandidates number of elements in candidates to consider, starting from 0
Definition at line 1909 of file branch_lookahead.c.
Referenced by sortFirstCandidatesByScore().
◆ scoreContainerUpdateSortOrder()
|
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
-
scorecontainer container to insert the index into candidate the probindex of a variable to store insertpoint point to store the index at
Definition at line 1954 of file branch_lookahead.c.
References NULL.
◆ scoreContainerSetScore()
|
static |
sets the score for the variable in the score container
- Parameters
-
scip SCIP data structure scorecontainer the container to write into cand candidate to add the score for score score to add downgain LP gain in down child upgain LP gain in up child
Definition at line 1979 of file branch_lookahead.c.
Referenced by ensureScoresPresent(), and selectVarRecursive().
◆ scoreContainerFree()
|
static |
Frees the score container and all of its contained arrays.
- Parameters
-
scip SCIP data structure scorecontainer score container to free
Definition at line 2036 of file branch_lookahead.c.
◆ selectVarRecursive()
|
static |
branches recursively on all given candidates
- Parameters
-
scip SCIP data structure status current status persistent container to store data over multiple calls to the branching rule; or NULL config the configuration of the branching rule baselpsol base lp solution domainreductions container collecting all domain reductions found binconsdata container collecting all binary constraints candidatelist list of candidates to branch on decision struct to store the final decision scorecontainer container to retrieve already calculated scores level2data level 2 LP results data recursiondepth remaining recursion depth lpobjval LP objective value of current probing node baselpobjval LP objective value of focus node (not probing) niterations pointer to store the total number of iterations for this variable ndeepestcutoffs pointer to store the total number of cutoffs on the deepest level bestgain pointer to store the best gain found with these candidates totalgains pointer to store the sum over all gains that are valid in both children ntotalgains pointer to store the number of gains summed in totalgains ndeepestnodes pointer to store the number of nodes processed in the deepest level
Definition at line 4713 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 |
Adds the given lower bound to the DOMAINREDUCTIONS struct.
- Parameters
-
scip SCIP data structure var The variable the bound should be added for. lowerbound The new lower bound for the variable. baselpsol The LP solution of the base problem. Used to check whether the domain reduction is violated by it. simplechange does the change result from an infeasible child node? domainreductions The struct the domain reduction should be added to.
Definition at line 2091 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ addUpperBound()
|
static |
Adds the given upper bound to the DOMAINREDUCTIONS struct.
- Parameters
-
scip SCIP data structure var The variable the bound should be added for. upperbound The new upper bound for the variable. baselpsol The LP solution of the base problem. Used to check whether the domain reduction is violated by it. simplechange does the change result from an infeasible child node? domainreductions The struct the domain reduction should be added to.
Definition at line 2156 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ applySingleDeeperDomainReductions()
|
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
-
scip SCIP data structure baselpsol The LP solution of the base problem. Used to check whether the domain reduction is violated by it. maxstoredomreds maximum number of domain reductions to store targetdomreds The target that should be filled with the merged data. domreds source domain reductions
Definition at line 2225 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ applyDeeperDomainReductions()
|
static |
merges the domain reduction data from the two given branching children data into the target parent data
- Parameters
-
scip SCIP data structure baselpsol The LP solution of the base problem. Used to check whether the domain reduction is violated by it. maxstoredomreds maximum number of domain reductions to store targetdomreds The target that should be filled with the merged data. downdomreds One of the source DOMAINREDUCTIONS. updomreds The other source DOMAINREDUCTIONS.
Definition at line 2279 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ applyDomainReductions()
|
static |
Applies the domain reductions to the current node.
- Parameters
-
scip SCIP data structure config the configuration of the branching rule baselpsol The LP solution of the base problem. Used to check whether the domain reduction is violated by it. domreds The domain reductions that should be applied to the current node. domredcutoff pointer to store whether a cutoff was found due to domain reductions domred pointer to store whether a domain change was added
Definition at line 2357 of file branch_lookahead.c.
◆ copyCurrentSolution()
|
static |
Copies the current LP solution into the given pointer. Needs to be freed after usage!
- Parameters
-
scip SCIP data structure lpsol pointer to store the solution into
Definition at line 2532 of file branch_lookahead.c.
◆ branchOnVar()
|
static |
Executes the branching on a given variable with a given value.
- Parameters
-
scip SCIP data structure config config struct with the user configuration decision the decision with all the needed data
Definition at line 2551 of file branch_lookahead.c.
◆ getNIterationsLastLP()
|
static |
Get the number of iterations the last LP needed
- Parameters
-
scip SCIP data structure iterations pointer to store the number of iterations
Definition at line 2685 of file branch_lookahead.c.
◆ executeBranching()
|
static |
Creates a new probing node with a new bound for the given candidate and solves the corresponding LP.
- Parameters
-
scip SCIP data structure config configuration to control the behavior downbranching the branching direction candidate the candidate to branch on resultdata pointer to the result data which gets filled with the status baselpsol the base lp solution domreds struct to store the domain reduction found during propagation status status will contain updated lperror and limit fields
Definition at line 2709 of file branch_lookahead.c.
Referenced by executeBranchingRecursive().
◆ createBinaryConstraint()
|
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
-
scip SCIP data structure config configuration containing flags changing the behavior constraint pointer to store the created constraint in constraintname name of the new constraint consvars array containing the negated binary vars nconsvars the number of elements in 'consvars'
Definition at line 2909 of file branch_lookahead.c.
◆ createBinaryConstraintName()
|
static |
Create a name for the binary constraint.
- Parameters
-
binaryvars the variables contained in the constraint nbinaryvars the number of elements in 'binaryvars' constraintname the char pointer to store the name in
Definition at line 2952 of file branch_lookahead.c.
References addBinaryConstraint(), BINCONSDATA::binaryvars, NULL, SCIP_MAXSTRLEN, and SCIPvarGetName().
◆ addBinaryConstraint()
|
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
-
scip SCIP data structure config the configuration of the branching rule binconsdata collected binary constraints baselpsol the original lp solution, used to check the violation of the constraint
Definition at line 2985 of file branch_lookahead.c.
Referenced by createBinaryConstraintName(), and executeBranchingRecursive().
◆ applyBinaryConstraints()
|
static |
applies the binary constraints to the original problem.
- Parameters
-
scip SCIP data structure basenode original branching node conslist list of constraints to be added config the configuration of the branching rule consadded pointer to store whether at least one constraint was added cutoff pointer to store whether the original problem was made infeasible boundchange pointer to store whether a bound change has been applied by adding the constraint as a clique
Definition at line 3055 of file branch_lookahead.c.
◆ areBoundsChanged()
|
static |
checks whether the given bounds are still the bounds of the given variable
- Parameters
-
scip SCIP data structure var variable to check the bounds of lowerbound reference lower bound upperbound reference upper bound
Definition at line 3184 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()
Checks whether the branching rule should continue or terminate with the currently gathered data
- Parameters
-
status current status checkdomreds should domain reductions be checked?
Definition at line 3204 of file branch_lookahead.c.
References FALSE, NULL, and SCIP_Bool.
Referenced by executeBranchingRecursive(), and filterCandidates().
◆ isBranchFurtherLoopDecrement()
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
-
status current status loopcounter the counter to decrement
Definition at line 3218 of file branch_lookahead.c.
References CONFIGURATION::inscoring, NULL, SCIPgetNNodes(), and SCIPgetVarStrongbranchNode().
Referenced by areBoundsChanged(), and selectVarRecursive().
◆ isUseOldBranching()
|
static |
determines whether the previous LAB result of a variable should be reused
- Parameters
-
scip SCIP data structure persistent data storage over multiple calls to the rule config the configuration of the branching rule branchvar variable to check
Definition at line 3238 of file branch_lookahead.c.
References getOldBranching(), NULL, CONFIGURATION::reevalage, SCIP_Real, SCIPgetNLPs(), SCIPgetNNodes(), and SCIPvarGetProbindex().
Referenced by selectVarRecursive().
◆ getOldBranching()
|
static |
retrieves previous LAB result for the given variable
- Parameters
-
scip SCIP data structure persistent data storage over multiple calls to the rule config the configuration of the branching rule branchvar variable to get previous results for downbranchingresult pointer to store the previous down result in upbranchingresult pointer to store the previous up result in oldlpobjval pointer to store the previous base lp objval in
Definition at line 3264 of file branch_lookahead.c.
Referenced by isUseOldBranching(), and selectVarRecursive().
◆ updateOldBranching()
|
static |
stores the LAB result for use in a later call to the branching rule
- Parameters
-
scip SCIP data structure persistent data storage over multiple calls to the rule config the configuration of the branching rule branchvar variable to store previous results for branchval the value of branchvar downbranchingresult down branching result to store upbranchingresult up branching result to store lpobjval base lp obj val
Definition at line 3317 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ getFSBResult()
|
static |
calculates the FSB scores for the given candidates
- Parameters
-
scip SCIP data structure status current status persistent container to store data over multiple calls to the branching rule; or NULL config the configuration of the branching rule baselpsol base lp solution domainreductions container collecting all domain reductions found; or NULL binconsdata container collecting all binary constraints; or NULL candidatelist list containing all candidates to consider decision struct to store the final decision scorecontainer container to retrieve already calculated scores; or NULL level2data level 2 LP results data lpobjval base LP objective value
Definition at line 3358 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 |
calculates the score based on the down and up branching result
- Parameters
-
scip SCIP data structure branchvar variable to get the score for downbranchingresult branching result of the down branch upbranchingresult branching result of the up branch lpobjval objective value to get difference to as gain
Definition at line 3443 of file branch_lookahead.c.
Referenced by getFSBResult().
◆ calculateScoreFromResult2()
|
static |
calculates the score based on the down and up branching result
- Parameters
-
scip SCIP data structure branchvar variable to get the score for downbranchingresult branching result of the down branch upbranchingresult branching result of the up branch lpobjval objective value to get difference to as gain
Definition at line 3487 of file branch_lookahead.c.
◆ calculateScoreFromDeeperscore()
|
static |
calculates the score based on the down and up branching scores
- Parameters
-
scip SCIP data structure branchvar variable to get the score for downbranchingresult branching result of the down branch upbranchingresult branching result of the up branch
Definition at line 3557 of file branch_lookahead.c.
◆ calculateScoreFromDeeperscoreAndCutoffs()
|
static |
calculates the score based on the down and up branching scores
- Parameters
-
scip SCIP data structure branchvar variable to get the score for downbranchingresult branching result of the down branch upbranchingresult branching result of the up branch
Definition at line 3594 of file branch_lookahead.c.
◆ calculateWeightedGain()
|
static |
calculates the combined gain, weighted with parameters given by the user configuration
- Parameters
-
scip SCIP data structure config LAB configuration downbranchingresult branching result of the down branch upbranchingresult branching result of the up branch lpobjval objective value to get difference to as gain
Definition at line 3650 of file branch_lookahead.c.
◆ calculateScaledCutoffScore()
|
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
-
downbranchingresult branching result of the down branch upbranchingresult branching result of the up branch
Definition at line 3700 of file branch_lookahead.c.
◆ calculateWeightedCutoffScore()
|
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
-
config LAB configuration downbranchingresult branching result of the down branch upbranchingresult branching result of the up branch
Definition at line 3732 of file branch_lookahead.c.
◆ calculateCutoffScore()
|
static |
- Parameters
-
scip SCIP data structure branchvar variable to get the score for downbranchingresult branching result of the down branch upbranchingresult branching result of the up branch lpobjval objective value to get difference to as gain
Definition at line 3761 of file branch_lookahead.c.
◆ calculateRelCutoffScore()
|
static |
- Parameters
-
scip SCIP data structure branchvar variable to get the score for downbranchingresult branching result of the down branch upbranchingresult branching result of the up branch lpobjval objective value to get difference to as gain
Definition at line 3820 of file branch_lookahead.c.
◆ calculateScore()
|
static |
scoring method that selects an actual scoring method based on the user configuration
- Parameters
-
scip SCIP data structure config LAB configuration branchvar variable to get the score for downbranchingresult branching result of the down branch upbranchingresult branching result of the up branch lpobjval objective value to get difference to as gain baselpobjval base objective value to get difference to as gain
Definition at line 3884 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ calculateScoreFromPseudocosts()
calculates the score based on the pseudocosts of the given variable
- Parameters
-
scip SCIP data structure lpcand candidate to get the score for
Definition at line 3949 of file branch_lookahead.c.
Referenced by ensureScoresPresent().
◆ sortFirstCandidatesByScore()
|
static |
sorts the best candidates (w.r.t. the score in the container) of the candidate list to the front of the list
- Parameters
-
scip SCIP data structure candidatelist candidates to be sorted scorecontainer container with the scores for each candidate nbestcandidates number of candidates that should be kept sorted at the start of the list
Definition at line 3998 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()
checks whether the given candidates is reliable, so that its pseudocosts may be used
- Parameters
-
scip SCIP data structure branchvar var to check for reliability
Definition at line 4063 of file branch_lookahead.c.
Referenced by ensureScoresPresent(), and sortFirstCandidatesByScore().
◆ isCurrentNodeCutoff()
checks whether the current problem is feasible or cutoff
- Parameters
-
scip SCIP data structure
Definition at line 4085 of file branch_lookahead.c.
Referenced by filterCandidates().
◆ ensureScoresPresent()
|
static |
Ensures that the scores are present in the scorecontainer for each of the candidates to consider
- Parameters
-
scip SCIP data structure status current status persistent container to store data over multiple calls to the branching rule; or NULL config the configuration of the branching rule baselpsol base lp solution domainreductions container collecting all domain reductions found; or NULL binconsdata container collecting all binary constraints; or NULL allcandidates list containing all candidates to consider decision struct to store the final decision scorecontainer container to retrieve already calculated scores; or NULL level2data level 2 LP results data lpobjval base LP objective value
Definition at line 4096 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 |
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
-
scip SCIP data structure status current status persistent container to store data over multiple calls to the branching rule; or NULL config the configuration of the branching rule baselpsol base lp solution domainreductions container collecting all domain reductions found; or NULL binconsdata container collecting all binary constraints; or NULL candidatelist list of candidates to branch on decision struct to store the final decision scorecontainer container to retrieve already calculated scores; or NULL level2data level 2 LP results data lpobjval base LP objective value
Definition at line 4228 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 |
Executes the general branching on a variable in a given direction (up/down) and repeats the algorithm from the new node
- Parameters
-
scip SCIP data structure status current status config the configuration of the branching rule baselpsol the base lp solution candidate candidate to branch on localbaselpsolval the objective value of the current temporary problem baselpobjval LP objective value of focus node (not probing) recursiondepth remaining recursion depth domainreductions container collecting all domain reductions found; or NULL binconsdata container collecting all binary constraints; or NULL level2data level 2 LP results data branchingresult container to store the result of the branching in scorecontainer container to retrieve already calculated scores; or NULL downbranching should we branch up or down in here?
Definition at line 4364 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 |
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
-
config the configuration of the branching rule binconsdata container collecting all binary constraints; or NULL domainreductions container collecting all domain reductions found; or NULL
Definition at line 5296 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ selectVarStart()
|
static |
starting point to obtain a branching decision via LAB/ALAB.
- Parameters
-
scip SCIP data structure config the configuration of the branching rule persistent container to store data over multiple calls to the branching rule; or NULL status current status decision struct to store the final decision scorecontainer container to retrieve already calculated scores; or NULL candidatelist list of candidates to branch on
Definition at line 5322 of file branch_lookahead.c.
◆ isUsePreviousResult()
|
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.
- Parameters
-
scip SCIP data structure branchruledata branching rule data
Definition at line 5657 of file branch_lookahead.c.
◆ usePreviousResult()
|
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
-
scip SCIP data structure branchruledata branching rule data result the pointer to the branching result
Definition at line 5693 of file branch_lookahead.c.
◆ freePersistent()
|
static |
free persistent data structure
- Parameters
-
scip SCIP data structure branchruledata branching rule data
Definition at line 5723 of file branch_lookahead.c.
References FALSE, initBranchruleData(), PERSISTENTDATA::lastbranchdownres, PERSISTENTDATA::lastbranchid, PERSISTENTDATA::lastbranchlpobjval, PERSISTENTDATA::lastbranchnlps, PERSISTENTDATA::lastbranchupres, NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPgetNBinVars(), and SCIPgetNIntVars().
Referenced by initBranchruleData().
◆ initBranchruleData()
|
static |
initializes the branchruledata and the contained structs
- Parameters
-
scip SCIP data structure branchruledata the branch rule data to initialize
Definition at line 5770 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 |
copy method for branchrule plugins (called when SCIP copies plugins)
Definition at line 5833 of file branch_lookahead.c.
Referenced by initBranchruleData().
◆ SCIP_DECL_BRANCHFREE()
|
static |
destructor of branching rule to free user data (called when SCIP is exiting)
Definition at line 5844 of file branch_lookahead.c.
References LABdebugMessage, NULL, SCIP_VERBLEVEL_FULL, and SCIPbranchruleGetData().
Referenced by initBranchruleData().
◆ SCIP_DECL_BRANCHINIT()
|
static |
initialization method of branching rule (called after problem was transformed)
Definition at line 5863 of file branch_lookahead.c.
References LABdebugMessage, NULL, SCIP_CALL, SCIP_DECL_BRANCHEXIT(), SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIPallocMemory, SCIPallocMemoryArray, SCIPbranchruleGetData(), SCIPfreeMemoryArray, SCIPgetNBinVars(), and SCIPgetNIntVars().
◆ SCIP_DECL_BRANCHEXIT()
|
static |
deinitialization method of branching rule (called before transformed problem is freed)
Definition at line 5922 of file branch_lookahead.c.
Referenced by SCIP_DECL_BRANCHINIT().
◆ SCIP_DECL_BRANCHEXITSOL()
|
static |
solving process deinitialization method of branching rule (called before branch and bound process data is freed)
Definition at line 5959 of file branch_lookahead.c.
References BRANCHRULE_NAME, LABdebugMessage, NULL, SCIP_Bool, SCIP_VERBLEVEL_HIGH, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPgetCurrentNode(), and SCIPnodeGetNumber().
◆ SCIP_DECL_BRANCHEXECLP()
|
static |
branching execution method for fractional LP solutions
Definition at line 5976 of file branch_lookahead.c.
◆ SCIPincludeBranchruleLookahead()
| SCIP_RETCODE SCIPincludeBranchruleLookahead | ( | SCIP * | scip | ) |
creates the lookahead branching rule and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 6203 of file branch_lookahead.c.
Referenced by SCIPincludeDefaultPlugins().