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 84 of file branch_lookahead.c.
◆ BRANCHRULE_DESC
| #define BRANCHRULE_DESC "full strong branching over multiple levels" |
Definition at line 85 of file branch_lookahead.c.
◆ BRANCHRULE_PRIORITY
| #define BRANCHRULE_PRIORITY 0 |
Definition at line 86 of file branch_lookahead.c.
◆ BRANCHRULE_MAXDEPTH
| #define BRANCHRULE_MAXDEPTH -1 |
Definition at line 87 of file branch_lookahead.c.
◆ BRANCHRULE_MAXBOUNDDIST
| #define BRANCHRULE_MAXBOUNDDIST 1.0 |
Definition at line 88 of file branch_lookahead.c.
◆ DEFAULT_USEBINARYCONSTRAINTS
| #define DEFAULT_USEBINARYCONSTRAINTS FALSE |
should binary constraints be collected and applied?
Definition at line 90 of file branch_lookahead.c.
◆ DEFAULT_ADDCLIQUE
| #define DEFAULT_ADDCLIQUE FALSE |
add binary constraints with two variables found at the root node also as a clique?
Definition at line 91 of file branch_lookahead.c.
◆ DEFAULT_ADDBINCONSROW
| #define DEFAULT_ADDBINCONSROW 0 |
should binary constraints be added as rows to the base LP? (0: no, 1: separate, 2: as initial rows)
Definition at line 93 of file branch_lookahead.c.
◆ DEFAULT_USEDOMAINREDUCTION
| #define DEFAULT_USEDOMAINREDUCTION TRUE |
Should domain reductions be collected and applied?
Definition at line 94 of file branch_lookahead.c.
◆ DEFAULT_MERGEDOMAINREDUCTIONS
| #define DEFAULT_MERGEDOMAINREDUCTIONS FALSE |
should domain reductions of feasible siblings should be merged?
Definition at line 95 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 96 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 97 of file branch_lookahead.c.
◆ DEFAULT_MAXNVIOLATEDCONS
| #define DEFAULT_MAXNVIOLATEDCONS 1 |
How many constraints that are violated by the base lp solution should be gathered until the rule is stopped and they are added?
Definition at line 99 of file branch_lookahead.c.
◆ DEFAULT_MAXNVIOLATEDBINCONS
| #define DEFAULT_MAXNVIOLATEDBINCONS 0 |
How many binary constraints that are violated by the base lp solution should be gathered until the rule is stopped and they are added?
Definition at line 102 of file branch_lookahead.c.
◆ DEFAULT_MAXNVIOLATEDDOMREDS
| #define DEFAULT_MAXNVIOLATEDDOMREDS 1 |
How many domain reductions that are violated by the base lp solution should be gathered until the rule is stopped and they are added?
Definition at line 104 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 106 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 108 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 110 of file branch_lookahead.c.
◆ DEFAULT_RECURSIONDEPTH
| #define DEFAULT_RECURSIONDEPTH 2 |
The max depth of LAB.
Definition at line 111 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 113 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 115 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 116 of file branch_lookahead.c.
◆ DEFAULT_APPLYCHILDBOUNDS
| #define DEFAULT_APPLYCHILDBOUNDS FALSE |
should bounds known for child nodes be applied?
Definition at line 117 of file branch_lookahead.c.
◆ DEFAULT_ENFORCEMAXDOMREDS
| #define DEFAULT_ENFORCEMAXDOMREDS FALSE |
should the maximum number of domain reductions maxnviolateddomreds be enforced?
Definition at line 118 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 119 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 122 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 123 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 125 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 127 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 129 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 130 of file branch_lookahead.c.
◆ DEFAULT_LEVEL2ZEROSCORE
| #define DEFAULT_LEVEL2ZEROSCORE FALSE |
should uninitialized scores be set to 0?
Definition at line 131 of file branch_lookahead.c.
◆ DEFAULT_SCORINGFUNCTION
| #define DEFAULT_SCORINGFUNCTION 'a' |
scoring function to be used at the base level
Definition at line 132 of file branch_lookahead.c.
◆ DEFAULT_DEEPERSCORINGFUNCTION
| #define DEFAULT_DEEPERSCORINGFUNCTION 'x' |
scoring function to be used at deeper levels
Definition at line 133 of file branch_lookahead.c.
◆ DEFAULT_SCORINGSCORINGFUNCTION
| #define DEFAULT_SCORINGSCORINGFUNCTION 'd' |
scoring function to be used for FSB scoring
Definition at line 134 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 136 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 137 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 138 of file branch_lookahead.c.
◆ LABdebugMessage
| #define LABdebugMessage | ( | scip, | |
| lvl, | |||
| ... | |||
| ) |
Definition at line 175 of file branch_lookahead.c.
◆ level2resultPrint
| #define level2resultPrint | ( | scip, | |
| result | |||
| ) |
Definition at line 767 of file branch_lookahead.c.
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 195 of file branch_lookahead.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.
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 215 of file branch_lookahead.c.
References WARMSTARTINFO::lpistate, and NULL.
Referenced by candidateHasWarmStartInfo().
◆ 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 224 of file branch_lookahead.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPfreeBlockMemory, SCIPgetLPI(), SCIPlpiFreeNorms(), and SCIPlpiFreeState().
Referenced by candidateFreeWarmStartInfo().
◆ 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 265 of file branch_lookahead.c.
References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.
Referenced by candidateListGetAllFractionalCandidates().
◆ 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 284 of file branch_lookahead.c.
References CANDIDATE::branchvar, CANDIDATE::downwarmstartinfo, LABdebugMessage, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIPvarGetName(), CANDIDATE::upwarmstartinfo, and warmStartInfoFree().
Referenced by candidateFree(), and scoreContainerSetScore().
◆ 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 311 of file branch_lookahead.c.
References candidateFreeWarmStartInfo(), LABdebugMessage, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIPfreeBlockMemory, and SCIPvarGetName().
Referenced by 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 332 of file branch_lookahead.c.
References CANDIDATE::downwarmstartinfo, WARMSTARTINFO::dualfeas, WARMSTARTINFO::lpinorms, WARMSTARTINFO::lpistate, NULL, WARMSTARTINFO::primalfeas, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPgetLPI(), SCIPlpiGetNorms(), SCIPlpiGetState(), SCIPlpiIsDualFeasible(), SCIPlpiIsPrimalFeasible(), CANDIDATE::upwarmstartinfo, and warmStartInfoCreate().
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 380 of file branch_lookahead.c.
References CANDIDATE::downwarmstartinfo, NULL, CANDIDATE::upwarmstartinfo, and warmStartInfoIsAvailable().
Referenced by executeBranching().
◆ 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 393 of file branch_lookahead.c.
References CANDIDATE::downwarmstartinfo, WARMSTARTINFO::dualfeas, LABdebugMessage, WARMSTARTINFO::lpinorms, WARMSTARTINFO::lpistate, NULL, WARMSTARTINFO::primalfeas, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPsetProbingLPState(), and CANDIDATE::upwarmstartinfo.
Referenced by executeBranching().
◆ branchingDecisionInit()
|
static |
initialize a branching decsion with default values
- Parameters
-
scip SCIP data structure decision the decision to initialize
Definition at line 451 of file branch_lookahead.c.
References BRANCHINGDECISION::boundssize, BRANCHINGDECISION::boundsvalid, BRANCHINGDECISION::branchval, BRANCHINGDECISION::branchvar, BRANCHINGDECISION::downdb, BRANCHINGDECISION::downdbvalid, BRANCHINGDECISION::downlowerbounds, BRANCHINGDECISION::downupperbounds, FALSE, NULL, BRANCHINGDECISION::proveddb, SCIP_INVALID, SCIPinfinity(), BRANCHINGDECISION::score, BRANCHINGDECISION::updb, BRANCHINGDECISION::updbvalid, BRANCHINGDECISION::uplowerbounds, and BRANCHINGDECISION::upupperbounds.
Referenced by branchingDecisionCreate(), and 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 478 of file branch_lookahead.c.
References branchingDecisionInit(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBuffer.
Referenced by executeBranchingRecursive(), and SCIP_DECL_BRANCHEXECLP().
◆ 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 501 of file branch_lookahead.c.
References BRANCHINGDECISION::boundssize, BRANCHINGDECISION::boundsvalid, BRANCHINGDECISION::branchval, BRANCHINGDECISION::branchvar, BRANCHINGDECISION::downdb, BRANCHINGDECISION::downdbvalid, BRANCHINGDECISION::downlowerbounds, BRANCHINGDECISION::downupperbounds, FALSE, NULL, BRANCHINGDECISION::proveddb, BRANCHINGDECISION::score, BRANCHINGDECISION::updb, BRANCHINGDECISION::updbvalid, BRANCHINGDECISION::uplowerbounds, and BRANCHINGDECISION::upupperbounds.
Referenced by selectVarStart().
◆ branchingDecisionIsValid()
|
static |
Checks whether the given branching decision can be used to branch on.
- Parameters
-
decision the branching decision to check
Definition at line 528 of file branch_lookahead.c.
References BRANCHINGDECISION::branchvar, and NULL.
Referenced by isUsePreviousResult(), SCIP_DECL_BRANCHEXECLP(), and selectVarStart().
◆ branchingDecisionEnsureBoundArraysSize()
|
static |
- Parameters
-
scip SCIP data structure decision branching decision nvars number of problem variables
Definition at line 540 of file branch_lookahead.c.
References BRANCHINGDECISION::boundssize, BRANCHINGDECISION::downlowerbounds, BRANCHINGDECISION::downupperbounds, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, BRANCHINGDECISION::uplowerbounds, and BRANCHINGDECISION::upupperbounds.
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 563 of file branch_lookahead.c.
References NULL, SCIPfreeBlockMemoryArray, and SCIPfreeBuffer.
Referenced by executeBranchingRecursive(), and SCIP_DECL_BRANCHEXECLP().
◆ 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 608 of file branch_lookahead.c.
References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBuffer.
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 623 of file branch_lookahead.c.
References BRANCHINGRESULTDATA::bestgain, BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::deeperscore, BRANCHINGRESULTDATA::dualbound, BRANCHINGRESULTDATA::dualboundvalid, FALSE, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::ndeepestnodes, BRANCHINGRESULTDATA::niterations, BRANCHINGRESULTDATA::ntotalgains, NULL, BRANCHINGRESULTDATA::objval, SCIPinfinity(), and BRANCHINGRESULTDATA::totalgains.
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 646 of file branch_lookahead.c.
References BRANCHINGRESULTDATA::bestgain, BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::deeperscore, BRANCHINGRESULTDATA::dualbound, BRANCHINGRESULTDATA::dualboundvalid, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::ndeepestnodes, BRANCHINGRESULTDATA::niterations, BRANCHINGRESULTDATA::ntotalgains, NULL, BRANCHINGRESULTDATA::objval, and BRANCHINGRESULTDATA::totalgains.
Referenced by getOldBranching(), selectVarRecursive(), and updateOldBranching().
◆ 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 669 of file branch_lookahead.c.
References NULL, and SCIPfreeBuffer.
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 711 of file branch_lookahead.c.
References LEVEL2DATA::branchdir1, LEVEL2DATA::branchdir2, LEVEL2DATA::branchval1, LEVEL2DATA::branchval2, LEVEL2DATA::branchvar1, LEVEL2DATA::branchvar2, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.
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 772 of file branch_lookahead.c.
References NULL, and SCIPfreeBlockMemory.
Referenced by level2dataFree(), and level2dataGetResult().
◆ 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 787 of file branch_lookahead.c.
References LEVEL2RESULT::branchdir1, LEVEL2RESULT::branchdir2, LEVEL2RESULT::branchval1, LEVEL2RESULT::branchval2, LEVEL2RESULT::branchvar1, LEVEL2RESULT::branchvar2, FALSE, and TRUE.
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 811 of file branch_lookahead.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, and SCIPinfinity().
Referenced by selectVarStart().
◆ 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 836 of file branch_lookahead.c.
References level2resultFree(), NULL, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.
Referenced by selectVarStart().
◆ level2dataEnsureSize()
|
static |
ensures that level2results can store at least one more element
- Parameters
-
scip SCIP data structure data level2 data
Definition at line 861 of file branch_lookahead.c.
References LEVEL2DATA::level2results, LEVEL2DATA::level2resultssize, LEVEL2DATA::nlevel2results, NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.
Referenced by 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 882 of file branch_lookahead.c.
References LEVEL2DATA::branchvar1, LEVEL2DATA::branchvar2, level2resultCreateFromData(), level2resultEqual(), level2resultFree(), LEVEL2DATA::level2results, LEVEL2DATA::nlevel2results, NULL, SCIP_CALL, SCIP_OKAY, 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 922 of file branch_lookahead.c.
References LEVEL2DATA::branchvar1, LEVEL2DATA::branchvar2, LEVEL2RESULT::cutoff, FALSE, LABdebugMessage, level2dataEnsureSize(), level2resultCreateFromData(), level2resultEqual(), level2resultPrint, LEVEL2DATA::level2results, LEVEL2DATA::level2resultssize, LEVEL2RESULT::lpobjval, LEVEL2DATA::nlevel2results, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIP_VERBLEVEL_HIGH, SCIPgetVars(), SCIPvarGetType(), TRUE, and LEVEL2RESULT::valid.
Referenced by executeBranchingRecursive().
◆ 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 1353 of file branch_lookahead.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, and SCIPallocBuffer.
Referenced by binConsDataCreate().
◆ 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 1378 of file branch_lookahead.c.
References CONSTRAINTLIST::consvars, CONSTRAINTLIST::memorysize, CONSTRAINTLIST::nconsvars, CONSTRAINTLIST::nelements, NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPduplicateBlockMemoryArray, SCIPreallocBlockMemoryArray, and CONSTRAINTLIST::violated.
Referenced by addBinaryConstraint().
◆ 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 1413 of file branch_lookahead.c.
References NULL, SCIPfreeBlockMemoryArray, and SCIPfreeBuffer.
Referenced by binConsDataFree().
◆ 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 1450 of file branch_lookahead.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, and SCIPallocBufferArray.
Referenced by binConsDataCreate().
◆ 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 1472 of file branch_lookahead.c.
References BINARYVARLIST::binaryvars, BINARYVARLIST::memorysize, BINARYVARLIST::nbinaryvars, NULL, and SCIPvarIsBinary().
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 1491 of file branch_lookahead.c.
References BINARYVARLIST::binaryvars, BINARYVARLIST::nbinaryvars, and NULL.
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 1505 of file branch_lookahead.c.
References NULL, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by binConsDataFree().
◆ 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 1526 of file branch_lookahead.c.
References binaryVarListCreate(), constraintListCreate(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBuffer.
Referenced by selectVarStart().
◆ 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 1547 of file branch_lookahead.c.
References binaryVarListFree(), constraintListFree(), NULL, and SCIPfreeBuffer.
Referenced by selectVarStart().
◆ 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 1571 of file branch_lookahead.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, and SCIPallocBufferArray.
Referenced by candidateListGetAllFractionalCandidates(), 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 1597 of file branch_lookahead.c.
References CANDIDATE::branchval, CANDIDATE::branchvar, candidateCreate(), candidateListCreate(), CANDIDATE::fracval, LABdebugMessage, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIPgetLPBranchCands(), and SCIPvarGetName().
Referenced by executeBranchingRecursive(), and SCIP_DECL_BRANCHEXECLP().
◆ 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 1642 of file branch_lookahead.c.
References candidateFree(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by ensureScoresPresent(), executeBranchingRecursive(), and SCIP_DECL_BRANCHEXECLP().
◆ 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 1673 of file branch_lookahead.c.
References candidateFree(), CANDIDATELIST::candidates, CANDIDATELIST::ncandidates, NULL, SCIP_CALL, and SCIP_OKAY.
Referenced by 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 1720 of file branch_lookahead.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPgetNVars(), SCIPgetVars(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
Referenced by selectVarRecursive(), and selectVarStart().
◆ 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 1762 of file branch_lookahead.c.
References NULL, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by selectVarRecursive(), and selectVarStart().
◆ 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 1796 of file branch_lookahead.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBuffer.
Referenced by executeBranchingRecursive(), and SCIP_DECL_BRANCHEXECLP().
◆ statusFree()
frees the allocated buffer memory of the status
- Parameters
-
scip SCIP data structure status the status to be freed
Definition at line 1820 of file branch_lookahead.c.
References NULL, and SCIPfreeBuffer.
Referenced by executeBranchingRecursive(), and SCIP_DECL_BRANCHEXECLP().
◆ scoreContainterResetBestSortedCands()
|
static |
resets the array containing the sorted indices w.r.t. their score.
- Parameters
-
scorecontainer the score container to reset
Definition at line 1844 of file branch_lookahead.c.
References SCORECONTAINER::bestsortedcands, BMSclearMemoryArray, SCORECONTAINER::nbestsortedcands, and NULL.
Referenced by ensureScoresPresent(), and scoreContainerCreate().
◆ 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 1855 of file branch_lookahead.c.
References CONFIGURATION::maxncands, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, SCIPallocBufferArray, SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNVars(), and scoreContainterResetBestSortedCands().
Referenced by SCIP_DECL_BRANCHEXECLP().
◆ 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 1903 of file branch_lookahead.c.
References CANDIDATE::branchvar, NULL, SCIP_Real, SCIPinfinity(), SCIPisGT(), SCIPvarGetProbindex(), and SCORECONTAINER::scores.
Referenced by scoreContainerSetScore(), and 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 1948 of file branch_lookahead.c.
References SCORECONTAINER::bestsortedcands, SCORECONTAINER::nbestsortedcands, and NULL.
Referenced by scoreContainerSetScore().
◆ 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 1973 of file branch_lookahead.c.
References SCORECONTAINER::bestsortedcands, CANDIDATE::branchvar, candidateFreeWarmStartInfo(), SCORECONTAINER::downgains, findInsertionPoint(), LABdebugMessage, SCORECONTAINER::nbestsortedcands, SCORECONTAINER::nsetscores, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPisGE(), SCIPvarGetName(), SCIPvarGetProbindex(), scoreContainerUpdateSortOrder(), SCORECONTAINER::scores, SCORECONTAINER::scoresum, and SCORECONTAINER::upgains.
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 2030 of file branch_lookahead.c.
References NULL, SCIP_OKAY, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by SCIP_DECL_BRANCHEXECLP().
◆ 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 4707 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(), isUseOldBranching(), LABdebugMessage, STATUS::limitreached, DOMAINREDUCTIONS::lowerbounds, STATUS::lperror, MAX, STATUS::maxnconsreached, CONFIGURATION::maxnviolatedbincons, CONFIGURATION::maxnviolatedcons, CONFIGURATION::maxnviolateddomreds, CONFIGURATION::mergedomainreductions, MIN, 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(), TRUE, CONFIGURATION::updatebranchingresults, updateOldBranching(), BRANCHINGDECISION::updb, BRANCHINGDECISION::updbvalid, BRANCHINGDECISION::uplowerbounds, DOMAINREDUCTIONS::upperbounds, BRANCHINGDECISION::upupperbounds, and CONFIGURATION::usedomainreduction.
Referenced by executeBranchingRecursive(), getFSBResult(), and selectVarStart().
◆ 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 2085 of file branch_lookahead.c.
References NULL, SCIP_Real, SCIPadjustedVarLb(), SCIPgetSolVal(), SCIPisEQ(), SCIPisFeasGT(), SCIPisLT(), SCIPvarGetProbindex(), and TRUE.
Referenced by applyDeeperDomainReductions(), applySingleDeeperDomainReductions(), executeBranching(), and 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 2150 of file branch_lookahead.c.
References NULL, SCIP_Real, SCIPadjustedVarUb(), SCIPgetSolVal(), SCIPisEQ(), SCIPisFeasLT(), SCIPisLE(), SCIPvarGetProbindex(), and TRUE.
Referenced by applyDeeperDomainReductions(), applySingleDeeperDomainReductions(), executeBranching(), and 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 2219 of file branch_lookahead.c.
References addLowerBound(), addUpperBound(), FALSE, DOMAINREDUCTIONS::lowerbounds, NULL, DOMAINREDUCTIONS::nviolatedvars, SCIPgetNVars(), SCIPgetVars(), TRUE, and DOMAINREDUCTIONS::upperbounds.
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 2273 of file branch_lookahead.c.
References addLowerBound(), addUpperBound(), FALSE, LABdebugMessage, DOMAINREDUCTIONS::lowerbounds, MAX, MIN, DOMAINREDUCTIONS::nchangedvars, NULL, DOMAINREDUCTIONS::nviolatedvars, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIPgetNVars(), SCIPgetVars(), and DOMAINREDUCTIONS::upperbounds.
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 2351 of file branch_lookahead.c.
References FALSE, LABdebugMessage, DOMAINREDUCTIONS::lowerbounds, DOMAINREDUCTIONS::nsimplebounds, NULL, CONFIGURATION::onlyvioldomreds, CONFIGURATION::prefersimplebounds, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), TRUE, and DOMAINREDUCTIONS::upperbounds.
Referenced by selectVarStart().
◆ 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 2526 of file branch_lookahead.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateLPSol(), and SCIPunlinkSol().
Referenced by selectVarStart().
◆ 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 2545 of file branch_lookahead.c.
References CONFIGURATION::applychildbounds, BRANCHINGDECISION::boundssize, BRANCHINGDECISION::boundsvalid, BRANCHINGDECISION::branchval, BRANCHINGDECISION::branchvar, BRANCHINGDECISION::downdb, BRANCHINGDECISION::downdbvalid, BRANCHINGDECISION::downlowerbounds, BRANCHINGDECISION::downupperbounds, LABdebugMessage, MAX, NULL, BRANCHINGDECISION::proveddb, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPallColsInLP(), SCIPbranchVarVal(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPdebugMsg, SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisExactSolve(), SCIPisGT(), SCIPisIntegral(), SCIPisLT(), SCIPnodeGetEstimate(), SCIPnodeGetLowerbound(), SCIPnodeGetNumber(), SCIPupdateNodeLowerbound(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), BRANCHINGDECISION::updb, BRANCHINGDECISION::updbvalid, BRANCHINGDECISION::uplowerbounds, and BRANCHINGDECISION::upupperbounds.
Referenced by SCIP_DECL_BRANCHEXECLP(), and usePreviousResult().
◆ 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 2679 of file branch_lookahead.c.
References NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPgetLPI(), and SCIPlpiGetIterations().
Referenced by executeBranching().
◆ 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 2703 of file branch_lookahead.c.
References addLowerBound(), addUpperBound(), CANDIDATE::branchval, CANDIDATE::branchvar, candidateHasWarmStartInfo(), candidateLoadWarmStartInfo(), BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::dualbound, BRANCHINGRESULTDATA::dualboundvalid, FALSE, getNIterationsLastLP(), LABdebugMessage, STATUS::limitreached, STATUS::lperror, CONFIGURATION::maxproprounds, BRANCHINGRESULTDATA::niterations, NULL, BRANCHINGRESULTDATA::objval, CONFIGURATION::propagate, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_LPSOLSTAT_ITERLIMIT, SCIP_LPSOLSTAT_NOTSOLVED, SCIP_LPSOLSTAT_TIMELIMIT, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPchgVarLbProbing(), SCIPchgVarUbProbing(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetCutoffbound(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPgetNVars(), SCIPgetVars(), SCIPinfinity(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLT(), SCIPisGE(), SCIPnewProbingNode(), SCIPpropagateProbing(), SCIPsolveProbingLP(), SCIPtryStrongbranchLPSol(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), TRUE, and CONFIGURATION::usedomainreduction.
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 2903 of file branch_lookahead.c.
References CONFIGURATION::addbinconsrow, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcreateConsLogicor(), and TRUE.
Referenced by applyBinaryConstraints().
◆ 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 2946 of file branch_lookahead.c.
References NULL, SCIP_MAXSTRLEN, SCIPsnprintf(), and SCIPvarGetName().
Referenced by applyBinaryConstraints().
◆ addBinaryConstraint()
|
static |
Add the constraints found during the lookahead branching. The implicit 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 2979 of file branch_lookahead.c.
References CONFIGURATION::addnonviocons, BINARYVARLIST::binaryvars, BINCONSDATA::binaryvars, BINCONSDATA::conslist, constraintListAppend(), LABdebugMessage, BINARYVARLIST::nbinaryvars, NULL, CONSTRAINTLIST::nviolatedcons, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNegatedVar(), SCIPgetSolVal(), and SCIPvarIsBinary().
Referenced by 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 3049 of file branch_lookahead.c.
References CONFIGURATION::addclique, CONSTRAINTLIST::consvars, createBinaryConstraint(), createBinaryConstraintName(), FALSE, LABdebugMessage, CONSTRAINTLIST::nconsvars, CONSTRAINTLIST::nelements, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPaddClique(), SCIPaddConsNode(), SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPgetNNodes(), SCIPinfoMessage(), SCIPprintCons(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarIsBinary(), TRUE, and CONSTRAINTLIST::violated.
Referenced by selectVarStart().
◆ 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 3178 of file branch_lookahead.c.
References NULL, SCIP_VARTYPE_CONTINUOUS, SCIPisEQ(), SCIPisFeasIntegral(), SCIPvarGetLbLocal(), SCIPvarGetType(), and SCIPvarGetUbLocal().
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 3198 of file branch_lookahead.c.
References STATUS::cutoff, STATUS::domred, STATUS::limitreached, STATUS::lperror, STATUS::maxnconsreached, and NULL.
Referenced by executeBranchingRecursive(), filterCandidates(), isBranchFurtherLoopDecrement(), and selectVarStart().
◆ 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 3212 of file branch_lookahead.c.
References FALSE, isBranchFurther(), NULL, and SCIP_Bool.
Referenced by 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 3232 of file branch_lookahead.c.
References CONFIGURATION::inscoring, PERSISTENTDATA::lastbranchid, PERSISTENTDATA::lastbranchnlps, NULL, CONFIGURATION::reevalage, CONFIGURATION::reevalagefsb, SCIPgetNLPs(), SCIPgetNNodes(), SCIPgetVarStrongbranchLPAge(), SCIPgetVarStrongbranchNode(), 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 3258 of file branch_lookahead.c.
References branchingResultDataCopy(), BRANCHINGRESULTDATA::dualbound, BRANCHINGRESULTDATA::dualboundvalid, CONFIGURATION::inscoring, LABdebugMessage, PERSISTENTDATA::lastbranchdownres, PERSISTENTDATA::lastbranchlpobjval, PERSISTENTDATA::lastbranchnlps, PERSISTENTDATA::lastbranchupres, MAX, NULL, BRANCHINGRESULTDATA::objval, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPgetNLPs(), SCIPgetVarStrongbranchLast(), SCIPvarGetName(), and SCIPvarGetProbindex().
Referenced by 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 3311 of file branch_lookahead.c.
References branchingResultDataCopy(), BRANCHINGRESULTDATA::dualbound, BRANCHINGRESULTDATA::dualboundvalid, CONFIGURATION::inscoring, PERSISTENTDATA::lastbranchdownres, PERSISTENTDATA::lastbranchid, PERSISTENTDATA::lastbranchlpobjval, PERSISTENTDATA::lastbranchnlps, PERSISTENTDATA::lastbranchupres, BRANCHINGRESULTDATA::niterations, NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPgetNLPs(), SCIPgetNNodes(), SCIPsetVarStrongbranchData(), and SCIPvarGetProbindex().
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 3352 of file branch_lookahead.c.
References FALSE, CONFIGURATION::inscoring, NULL, CONFIGURATION::recursiondepth, SCIP_CALL, SCIP_OKAY, SCIPgetProbingDepth(), SCIPinProbing(), 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 3437 of file branch_lookahead.c.
References BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::dualbound, MAX, NULL, SCIP_Real, SCIPgetBranchScore(), and SCIPsumepsilon().
Referenced by calculateScore().
◆ 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 3481 of file branch_lookahead.c.
References BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::dualbound, MAX, NULL, BRANCHINGRESULTDATA::objval, SCIP_Real, SCIPgetBranchScore(), and SCIPsumepsilon().
Referenced by calculateScore().
◆ 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 3551 of file branch_lookahead.c.
References BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::deeperscore, MAX, NULL, SCIP_Real, SCIPgetBranchScore(), SCIPisStopped(), and SCIPsumepsilon().
Referenced by calculateScore().
◆ 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 3588 of file branch_lookahead.c.
References BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::deeperscore, MAX, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::ndeepestnodes, BRANCHINGRESULTDATA::ntotalgains, NULL, SCIP_Real, SCIPgetBranchScore(), SCIPisStopped(), SCIPsumepsilon(), and BRANCHINGRESULTDATA::totalgains.
Referenced by calculateScore().
◆ 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 3644 of file branch_lookahead.c.
References BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::dualbound, MAX, MIN, CONFIGURATION::minweight, NULL, SCIP_Real, SCIPinfinity(), and CONFIGURATION::scoringfunction.
Referenced by calculateScore().
◆ 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 3694 of file branch_lookahead.c.
References BRANCHINGRESULTDATA::bestgain, MAX, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::ntotalgains, NULL, SCIP_Real, and BRANCHINGRESULTDATA::totalgains.
Referenced by calculateScore().
◆ 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 3726 of file branch_lookahead.c.
References BRANCHINGRESULTDATA::bestgain, MAX, MIN, CONFIGURATION::minweight, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::ndeepestnodes, BRANCHINGRESULTDATA::ntotalgains, NULL, SCIP_Real, and BRANCHINGRESULTDATA::totalgains.
Referenced by calculateScore().
◆ 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 3755 of file branch_lookahead.c.
References BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::dualbound, MAX, BRANCHINGRESULTDATA::ndeepestcutoffs, NULL, SCIP_Real, SCIPgetBranchScore(), SCIPgetCutoffbound(), SCIPgetNPseudoBranchCands(), and SCIPsumepsilon().
Referenced by calculateScore().
◆ 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 3814 of file branch_lookahead.c.
References BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::dualbound, MAX, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::ndeepestnodes, NULL, SCIP_Real, SCIPgetBranchScore(), SCIPgetCutoffbound(), SCIPgetNLPRows(), SCIPgetNPseudoBranchCands(), and SCIPsumepsilon().
Referenced by calculateScore().
◆ 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 3878 of file branch_lookahead.c.
References calculateCutoffScore(), calculateRelCutoffScore(), calculateScaledCutoffScore(), calculateScoreFromDeeperscore(), calculateScoreFromDeeperscoreAndCutoffs(), calculateScoreFromResult(), calculateScoreFromResult2(), calculateWeightedCutoffScore(), calculateWeightedGain(), CONFIGURATION::deeperscoringfunction, CONFIGURATION::inscoring, NULL, SCIP_Real, SCIPgetProbingDepth(), CONFIGURATION::scoringfunction, and CONFIGURATION::scoringscoringfunction.
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 3943 of file branch_lookahead.c.
References CANDIDATE::branchvar, CANDIDATE::fracval, NULL, SCIP_Real, SCIPgetBranchScore(), and SCIPgetVarPseudocostVal().
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 3992 of file branch_lookahead.c.
References CANDIDATE::branchvar, CANDIDATELIST::candidates, findInsertionPoint(), LABdebugMessage, MIN, CANDIDATELIST::ncandidates, NULL, SCIP_Real, SCIP_VERBLEVEL_HIGH, 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 4057 of file branch_lookahead.c.
References MIN, NULL, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_Real, and SCIPgetVarPseudocostCountCurrentRun().
Referenced by ensureScoresPresent().
◆ isCurrentNodeCutoff()
checks whether the current problem is feasible or cutoff
- Parameters
-
scip SCIP data structure
Definition at line 4079 of file branch_lookahead.c.
References NULL, SCIPgetCutoffdepth(), and SCIPgetDepth().
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 4090 of file branch_lookahead.c.
References CONFIGURATION::abbrevpseudo, CANDIDATE::branchvar, calculateScoreFromPseudocosts(), candidateListCreate(), candidateListFree(), CANDIDATELIST::candidates, 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 4222 of file branch_lookahead.c.
References CONFIGURATION::abbreviated, CANDIDATE::branchvar, candidateListKeep(), CANDIDATELIST::candidates, STATUS::cutoff, SCORECONTAINER::downgains, ensureScoresPresent(), CONFIGURATION::filterbymaxgain, isBranchFurther(), isCurrentNodeCutoff(), LABdebugMessage, MAX, CONFIGURATION::maxncands, CONFIGURATION::maxndeepercands, MIN, CANDIDATELIST::ncandidates, NULL, 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 executeBranchingRecursive(), and selectVarStart().
◆ 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 4358 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_LONGINT_FORMAT, 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 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 5290 of file branch_lookahead.c.
References BINCONSDATA::conslist, FALSE, DOMAINREDUCTIONS::nchangedvars, CONSTRAINTLIST::nelements, NULL, CONSTRAINTLIST::nviolatedcons, DOMAINREDUCTIONS::nviolatedvars, and CONFIGURATION::storeunviolatedsol.
Referenced by selectVarStart().
◆ 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 5316 of file branch_lookahead.c.
References CONFIGURATION::abbreviated, STATUS::addedbinconss, applyBinaryConstraints(), applyDomainReductions(), BINCONSDATA::binaryvars, binConsDataCreate(), binConsDataFree(), branchingDecisionCopy(), branchingDecisionIsValid(), CANDIDATE::branchval, BRANCHINGDECISION::branchval, CANDIDATE::branchvar, BRANCHINGDECISION::branchvar, CANDIDATELIST::candidates, BINCONSDATA::conslist, copyCurrentSolution(), STATUS::cutoff, STATUS::depthtoosmall, domainReductionsCreate(), domainReductionsFree(), STATUS::domred, STATUS::domredcutoff, BRANCHINGDECISION::downdb, BRANCHINGDECISION::downdbvalid, FALSE, filterCandidates(), CONFIGURATION::inscoring, isBranchFurther(), isStoreDecision(), LABdebugMessage, level2dataCreate(), level2dataFree(), STATUS::lperror, STATUS::maxnconsreached, BINARYVARLIST::nbinaryvars, CANDIDATELIST::ncandidates, CONSTRAINTLIST::nelements, NULL, PERSISTENTDATA::olddecision, PERSISTENTDATA::oldnnodelpiterations, PERSISTENTDATA::oldnnodelps, PERSISTENTDATA::oldntotalnodes, BRANCHINGDECISION::proveddb, CONFIGURATION::recursiondepth, SCIP_Bool, SCIP_CALL, SCIP_MAXTREEDEPTH, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIPABORT, SCIPceil(), SCIPenableVarHistory(), SCIPendStrongbranch(), SCIPfreeSol(), SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetNNodeLPIterations(), SCIPgetNNodeLPs(), SCIPgetNNodeZeroIterationLPs(), SCIPgetNTotalNodes(), SCIPgetProbingDepth(), SCIPgetSolVal(), SCIPinProbing(), SCIPnodeGetNumber(), SCIPstartStrongbranch(), SCIPstatistic, SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetUbLocal(), SCORECONTAINER::scores, selectVarRecursive(), TRUE, BRANCHINGDECISION::updb, BRANCHINGDECISION::updbvalid, CONFIGURATION::usebincons, CONFIGURATION::usedomainreduction, and CONFIGURATION::uselevel2data.
Referenced by SCIP_DECL_BRANCHEXECLP().
◆ 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 5651 of file branch_lookahead.c.
References branchingDecisionIsValid(), LABdebugMessage, NULL, PERSISTENTDATA::olddecision, PERSISTENTDATA::oldnnodelpiterations, PERSISTENTDATA::oldnnodelps, PERSISTENTDATA::oldntotalnodes, SCIP_VERBLEVEL_HIGH, SCIPgetNNodeLPIterations(), SCIPgetNNodeLPs(), SCIPgetNNodeZeroIterationLPs(), and SCIPgetNTotalNodes().
Referenced by SCIP_DECL_BRANCHEXECLP().
◆ 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 5687 of file branch_lookahead.c.
References branchOnVar(), LABdebugMessage, NULL, SCIP_BRANCHED, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, and SCIPvarGetName().
Referenced by SCIP_DECL_BRANCHEXECLP().
◆ freePersistent()
|
static |
free persistent data structure
- Parameters
-
scip SCIP data structure branchruledata branching rule data
Definition at line 5717 of file branch_lookahead.c.
References FALSE, PERSISTENTDATA::lastbranchdownres, PERSISTENTDATA::lastbranchid, PERSISTENTDATA::lastbranchlpobjval, PERSISTENTDATA::lastbranchnlps, PERSISTENTDATA::lastbranchupres, NULL, PERSISTENTDATA::nvars, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.
Referenced by initBranchruleData(), and SCIP_DECL_BRANCHEXITSOL().
◆ initBranchruleData()
|
static |
initializes the branchruledata and the contained structs
- Parameters
-
scip SCIP data structure branchruledata the branch rule data to initialize
Definition at line 5764 of file branch_lookahead.c.
References branchingDecisionInit(), freePersistent(), LABdebugMessage, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPgetNBinVars(), SCIPgetNIntVars(), and TRUE.
Referenced by SCIP_DECL_BRANCHEXECLP().
◆ SCIP_DECL_BRANCHCOPY()
|
static |
copy method for branchrule plugins (called when SCIP copies plugins)
Definition at line 5827 of file branch_lookahead.c.
References BRANCHRULE_NAME, NULL, SCIP_OKAY, and SCIPbranchruleGetName().
◆ SCIP_DECL_BRANCHFREE()
|
static |
destructor of branching rule to free user data (called when SCIP is exiting)
Definition at line 5838 of file branch_lookahead.c.
References NULL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleSetData(), and SCIPfreeBlockMemory.
◆ SCIP_DECL_BRANCHINIT()
|
static |
initialization method of branching rule (called after problem was transformed)
Definition at line 5857 of file branch_lookahead.c.
References LABdebugMessage, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIPallocMemory, SCIPallocMemoryArray, SCIPbranchruleGetData(), SCIPgetNBinVars(), and SCIPgetNIntVars().
◆ SCIP_DECL_BRANCHEXIT()
|
static |
deinitialization method of branching rule (called before transformed problem is freed)
Definition at line 5916 of file branch_lookahead.c.
References NULL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPfreeMemory, and SCIPfreeMemoryArray.
◆ SCIP_DECL_BRANCHEXITSOL()
|
static |
solving process deinitialization method of branching rule (called before branch and bound process data is freed)
Definition at line 5953 of file branch_lookahead.c.
References freePersistent(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPbranchruleGetData().
◆ SCIP_DECL_BRANCHEXECLP()
|
static |
branching execution method for fractional LP solutions
Definition at line 5970 of file branch_lookahead.c.
References CONFIGURATION::abbreviated, STATUS::addedbinconss, branchingDecisionCreate(), branchingDecisionFree(), branchingDecisionIsValid(), branchOnVar(), BRANCHRULE_NAME, CANDIDATE::branchval, BRANCHINGDECISION::branchval, CANDIDATE::branchvar, BRANCHINGDECISION::branchvar, candidateListFree(), candidateListGetAllFractionalCandidates(), CANDIDATELIST::candidates, STATUS::cutoff, STATUS::depthtoosmall, STATUS::domred, STATUS::domredcutoff, BRANCHINGDECISION::downdb, initBranchruleData(), isUsePreviousResult(), LABdebugMessage, STATUS::limitreached, STATUS::lperror, STATUS::maxnconsreached, CANDIDATELIST::ncandidates, NULL, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CONSADDED, SCIP_CUTOFF, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIP_VERBLEVEL_NORMAL, SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPgetCurrentNode(), SCIPisStopped(), SCIPnodeGetNumber(), SCIPvarGetName(), scoreContainerCreate(), scoreContainerFree(), selectVarStart(), statusCreate(), statusFree(), CONFIGURATION::storeunviolatedsol, BRANCHINGDECISION::updb, CONFIGURATION::usebincons, and usePreviousResult().
◆ SCIPincludeBranchruleLookahead()
| SCIP_RETCODE SCIPincludeBranchruleLookahead | ( | SCIP * | scip | ) |
creates the lookahead branching rule and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 6197 of file branch_lookahead.c.
References BRANCHRULE_DESC, BRANCHRULE_MAXBOUNDDIST, BRANCHRULE_MAXDEPTH, BRANCHRULE_NAME, BRANCHRULE_PRIORITY, DEFAULT_ABBREVIATED, DEFAULT_ABBREVPSEUDO, DEFAULT_ADDBINCONSROW, DEFAULT_ADDCLIQUE, DEFAULT_ADDNONVIOCONS, DEFAULT_APPLYCHILDBOUNDS, DEFAULT_DEEPERSCORINGFUNCTION, DEFAULT_ENFORCEMAXDOMREDS, DEFAULT_FILTERBYMAXGAIN, DEFAULT_LEVEL2AVGSCORE, DEFAULT_LEVEL2ZEROSCORE, DEFAULT_MAXNCANDS, DEFAULT_MAXNDEEPERCANDS, DEFAULT_MAXNVIOLATEDBINCONS, DEFAULT_MAXNVIOLATEDCONS, DEFAULT_MAXNVIOLATEDDOMREDS, DEFAULT_MAXPROPROUNDS, DEFAULT_MERGEDOMAINREDUCTIONS, DEFAULT_MINWEIGHT, DEFAULT_ONLYVIOLDOMREDS, DEFAULT_PREFERSIMPLEBOUNDS, DEFAULT_PROPAGATE, DEFAULT_RECURSIONDEPTH, DEFAULT_REEVALAGE, DEFAULT_REEVALAGEFSB, DEFAULT_REUSEBASIS, DEFAULT_SCORINGFUNCTION, DEFAULT_SCORINGSCORINGFUNCTION, DEFAULT_STOREUNVIOLATEDSOL, DEFAULT_UPDATEBRANCHINGRESULTS, DEFAULT_USEBINARYCONSTRAINTS, DEFAULT_USEDOMAINREDUCTION, DEFAULT_USELEVEL2DATA, DEFAULT_WORSEFACTOR, FALSE, NULL, SCIP_CALL, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_REAL_MAX, SCIPaddBoolParam(), SCIPaddCharParam(), SCIPaddIntParam(), SCIPaddLongintParam(), SCIPaddRealParam(), SCIPallocBlockMemory, SCIPincludeBranchruleBasic(), SCIPsetBranchruleCopy(), SCIPsetBranchruleExecLp(), SCIPsetBranchruleExit(), SCIPsetBranchruleExitsol(), SCIPsetBranchruleFree(), SCIPsetBranchruleInit(), and TRUE.
Referenced by SCIPincludeDefaultPlugins().