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:
For a more mathematical description and a comparison between lookahead branching and other branching rules in SCIP, we refer to
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 |
#define BRANCHRULE_NAME "lookahead" |
Definition at line 84 of file branch_lookahead.c.
#define BRANCHRULE_DESC "full strong branching over multiple levels" |
Definition at line 85 of file branch_lookahead.c.
#define BRANCHRULE_PRIORITY 0 |
Definition at line 86 of file branch_lookahead.c.
#define BRANCHRULE_MAXDEPTH -1 |
Definition at line 87 of file branch_lookahead.c.
#define BRANCHRULE_MAXBOUNDDIST 1.0 |
Definition at line 88 of file branch_lookahead.c.
#define DEFAULT_USEBINARYCONSTRAINTS FALSE |
should binary constraints be collected and applied?
Definition at line 90 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#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.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_ADDBINCONSROW 0 |
should binary constraints be added as rows to the base LP? (0: no, 1: separate, 2: as initial rows)
Definition at line 92 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_USEDOMAINREDUCTION TRUE |
Should domain reductions be collected and applied?
Definition at line 94 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_MERGEDOMAINREDUCTIONS FALSE |
should domain reductions of feasible siblings should be merged?
Definition at line 95 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#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.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_ONLYVIOLDOMREDS FALSE |
Should only domain reductions that violate the LP solution be applied?
Definition at line 97 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#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 98 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#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 100 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#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 103 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_STOREUNVIOLATEDSOL TRUE |
If only non violating constraints are added, should the branching decision be stored till the next call?
Definition at line 105 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_REEVALAGE 10LL |
Max number of LPs solved after which a previous prob branching result is recalculated.
Definition at line 107 of file branch_lookahead.c.
#define DEFAULT_REEVALAGEFSB 10LL |
Max number of LPs solved after which a previous FSB scoring result is recalculated.
Definition at line 109 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_RECURSIONDEPTH 2 |
The max depth of LAB.
Definition at line 111 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_ADDNONVIOCONS FALSE |
Should binary constraints, that are not violated by the base LP, be collected and added?
Definition at line 112 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_PROPAGATE TRUE |
Should domain propagation be executed before each temporary node is solved?
Definition at line 114 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#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.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_APPLYCHILDBOUNDS FALSE |
should bounds known for child nodes be applied?
Definition at line 117 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_ENFORCEMAXDOMREDS FALSE |
should the maximum number of domain reductions maxnviolateddomreds be enforced?
Definition at line 118 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#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.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_MAXPROPROUNDS 0 |
maximum number of propagation rounds to perform at temporary nodes (-1: unlimited, 0: SCIP default)
Definition at line 120 of file branch_lookahead.c.
#define DEFAULT_ABBREVIATED TRUE |
Toggles the abbreviated LAB.
Definition at line 122 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#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.
#define DEFAULT_MAXNDEEPERCANDS 2 |
If abbreviated: The max number of candidates to consider per deeper node (0: same as base node)
Definition at line 124 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_REUSEBASIS TRUE |
If abbreviated: Should the information gathered to obtain the best candidates be reused?
Definition at line 126 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_ABBREVPSEUDO FALSE |
If abbreviated: Use pseudo costs to estimate the score of a candidate.
Definition at line 128 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#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.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_LEVEL2ZEROSCORE FALSE |
should uninitialized scores be set to 0?
Definition at line 131 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_SCORINGFUNCTION 'a' |
scoring function to be used at the base level
Definition at line 132 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_DEEPERSCORINGFUNCTION 'x' |
scoring function to be used at deeper levels
Definition at line 133 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#define DEFAULT_SCORINGSCORINGFUNCTION 'd' |
scoring function to be used for FSB scoring
Definition at line 134 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#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 135 of file branch_lookahead.c.
Referenced by SCIPincludeBranchruleLookahead().
#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.
Referenced by SCIPincludeBranchruleLookahead().
#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.
Referenced by SCIPincludeBranchruleLookahead().
#define LABdebugMessage | ( | scip, | |
lvl, | |||
... ) |
Definition at line 175 of file branch_lookahead.c.
Referenced by addBinaryConstraint(), applyBinaryConstraints(), applyDeeperDomainReductions(), applyDomainReductions(), branchOnVar(), candidateFree(), candidateFreeWarmStartInfo(), candidateListGetAllFractionalCandidates(), candidateLoadWarmStartInfo(), ensureScoresPresent(), executeBranching(), executeBranchingRecursive(), filterCandidates(), getOldBranching(), initBranchruleData(), isUsePreviousResult(), level2dataStoreResult(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_BRANCHINIT(), scoreContainerSetScore(), selectVarRecursive(), selectVarStart(), sortFirstCandidatesByScore(), and usePreviousResult().
#define level2resultPrint | ( | scip, | |
result ) |
Definition at line 767 of file branch_lookahead.c.
Referenced by level2dataStoreResult().
|
static |
Allocates the warm start information on the buffer and initializes it with default values.
scip | SCIP data structure |
warmstartinfo | the warmstartinfo to allocate and initialize |
Definition at line 195 of file branch_lookahead.c.
References assert(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.
Referenced by candidateStoreWarmStartInfo().
|
static |
checks that the warm start info can be read into the lp solver.
warmstartinfo | the warm start info to check (may be NULL) |
Definition at line 215 of file branch_lookahead.c.
References WARMSTARTINFO::lpistate, NULL, and SCIP_Bool.
Referenced by candidateHasWarmStartInfo().
|
static |
Frees the allocated buffer memory of the warm start info.
scip | SCIP data structure |
warmstartinfo | the warm start info to free |
Definition at line 224 of file branch_lookahead.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPfreeBlockMemory, SCIPgetLPI(), SCIPlpiFreeNorms(), and SCIPlpiFreeState().
Referenced by candidateFreeWarmStartInfo().
|
static |
Allocates the candidate on the buffer and initializes it with default values.
scip | SCIP data structure |
candidate | the candidate to allocate and initialize |
Definition at line 265 of file branch_lookahead.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.
Referenced by candidateListGetAllFractionalCandidates().
|
static |
free the warm starting information for the given candidate
scip | SCIP data structure |
candidate | the candidate to free the warm starting information for |
Definition at line 284 of file branch_lookahead.c.
References assert(), CANDIDATE::branchvar, CANDIDATE::downwarmstartinfo, LABdebugMessage, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIPvarGetName(), CANDIDATE::upwarmstartinfo, and warmStartInfoFree().
Referenced by candidateFree(), and scoreContainerSetScore().
|
static |
Frees the allocated buffer memory of the candidate and clears the contained lpi memories.
scip | SCIP data structure |
candidate | the candidate to free |
Definition at line 311 of file branch_lookahead.c.
References assert(), candidateFreeWarmStartInfo(), LABdebugMessage, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIPfreeBlockMemory, and SCIPvarGetName().
Referenced by candidateListFree(), and candidateListKeep().
|
static |
Store the current lp solution in the warm start info for further usage.
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 assert(), CANDIDATE::downwarmstartinfo, WARMSTARTINFO::dualfeas, WARMSTARTINFO::lpinorms, WARMSTARTINFO::lpistate, NULL, WARMSTARTINFO::primalfeas, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPgetLPI(), SCIPlpiGetNorms(), SCIPlpiGetState(), SCIPlpiIsDualFeasible(), SCIPlpiIsPrimalFeasible(), CANDIDATE::upwarmstartinfo, and warmStartInfoCreate().
Referenced by executeBranchingRecursive().
returns whether the candidate has stored warm starting information for the given direction
candidate | the branching candidate |
down | is the info for down branching? |
Definition at line 380 of file branch_lookahead.c.
References assert(), CANDIDATE::downwarmstartinfo, NULL, SCIP_Bool, CANDIDATE::upwarmstartinfo, and warmStartInfoIsAvailable().
Referenced by executeBranching().
|
static |
loads the warm starting information of the candidate for the given direction
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 assert(), CANDIDATE::downwarmstartinfo, WARMSTARTINFO::dualfeas, LABdebugMessage, WARMSTARTINFO::lpinorms, WARMSTARTINFO::lpistate, NULL, WARMSTARTINFO::primalfeas, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPsetProbingLPState(), and CANDIDATE::upwarmstartinfo.
Referenced by executeBranching().
|
static |
initialize a branching decsion with default values
scip | SCIP data structure |
decision | the decision to initialize |
Definition at line 451 of file branch_lookahead.c.
References assert(), 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().
|
static |
allocates a branching decision in the buffer and initializes it with default values.
scip | SCIP data structure |
decision | pointer to the decision to allocate and initialize |
Definition at line 478 of file branch_lookahead.c.
References assert(), branchingDecisionInit(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBuffer.
Referenced by executeBranchingRecursive(), and SCIP_DECL_BRANCHEXECLP().
|
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
sourcedecision | the source branching decision |
targetdecision | the target branching decision |
Definition at line 501 of file branch_lookahead.c.
References assert(), 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().
|
static |
Checks whether the given branching decision can be used to branch on.
decision | the branching decision to check |
Definition at line 528 of file branch_lookahead.c.
References assert(), BRANCHINGDECISION::branchvar, NULL, and SCIP_Bool.
Referenced by isUsePreviousResult(), SCIP_DECL_BRANCHEXECLP(), and selectVarStart().
|
static |
scip | SCIP data structure |
decision | branching decision |
nvars | number of problem variables |
Definition at line 540 of file branch_lookahead.c.
References assert(), BRANCHINGDECISION::boundssize, BRANCHINGDECISION::downlowerbounds, BRANCHINGDECISION::downupperbounds, NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, BRANCHINGDECISION::uplowerbounds, and BRANCHINGDECISION::upupperbounds.
Referenced by selectVarRecursive().
|
static |
Frees the allocated memory of the branching decision.
scip | SCIP data structure |
decision | pointer to the decision to be freed |
Definition at line 563 of file branch_lookahead.c.
References assert(), NULL, SCIPfreeBlockMemoryArray, and SCIPfreeBuffer.
Referenced by executeBranchingRecursive(), and SCIP_DECL_BRANCHEXECLP().
|
static |
Allocates a branching result in the buffer.
scip | SCIP data structure |
resultdata | pointer to the result to be allocated |
Definition at line 608 of file branch_lookahead.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBuffer.
Referenced by selectVarRecursive().
|
static |
Initiates the branching result with default values.
scip | SCIP data structure |
resultdata | pointer to the result to be initialized |
Definition at line 623 of file branch_lookahead.c.
References assert(), 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().
|
static |
Copies the data from the source to the target.
sourcedata | the source branching result |
targetdata | the target branching result |
Definition at line 646 of file branch_lookahead.c.
References assert(), 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().
|
static |
Frees the allocated buffer memory of the branching result.
scip | SCIP data structure |
resultdata | pointer to the result to be freed |
Definition at line 669 of file branch_lookahead.c.
References assert(), NULL, and SCIPfreeBuffer.
Referenced by selectVarRecursive().
|
static |
allocates a double branching result in the memory and fills it with the information stored in the level 2 data
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 assert(), LEVEL2DATA::branchdir1, LEVEL2DATA::branchdir2, LEVEL2DATA::branchval1, LEVEL2DATA::branchval2, LEVEL2DATA::branchvar1, LEVEL2DATA::branchvar2, NULL, result, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.
Referenced by level2dataGetResult(), and level2dataStoreResult().
|
static |
frees the allocated memory of the double branching result
scip | SCIP data structure |
result | pointer to the result to be freed |
Definition at line 772 of file branch_lookahead.c.
References assert(), NULL, result, and SCIPfreeBlockMemory.
Referenced by level2dataFree(), and level2dataGetResult().
|
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
result1 | first level 2 result |
result2 | second level 2 result |
Definition at line 787 of file branch_lookahead.c.
References assert(), LEVEL2RESULT::branchdir1, LEVEL2RESULT::branchdir2, LEVEL2RESULT::branchval1, LEVEL2RESULT::branchval2, LEVEL2RESULT::branchvar1, LEVEL2RESULT::branchvar2, FALSE, SCIP_Bool, and TRUE.
Referenced by level2dataGetResult(), and level2dataStoreResult().
|
static |
allocates the level2 data
scip | SCIP data structure |
data | pointer to the data to be allocated |
Definition at line 811 of file branch_lookahead.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, and SCIPinfinity().
Referenced by selectVarStart().
|
static |
frees the allocated memory of the level2 data
scip | SCIP data structure |
data | pointer to the data to be freed |
Definition at line 836 of file branch_lookahead.c.
References assert(), level2resultFree(), NULL, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.
Referenced by selectVarStart().
|
static |
ensures that level2results can store at least one more element
scip | SCIP data structure |
data | level2 data |
Definition at line 861 of file branch_lookahead.c.
References assert(), LEVEL2DATA::level2results, LEVEL2DATA::level2resultssize, LEVEL2DATA::nlevel2results, NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.
Referenced by level2dataStoreResult().
|
static |
get a result from the level 2 data
scip | SCIP data structure |
data | level2 data |
result | pointer to store result |
Definition at line 882 of file branch_lookahead.c.
References assert(), LEVEL2DATA::branchvar1, LEVEL2DATA::branchvar2, i, level2resultCreateFromData(), level2resultEqual(), level2resultFree(), LEVEL2DATA::level2results, LEVEL2DATA::nlevel2results, NULL, result, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPgetVars(), and SCIPvarGetType().
Referenced by executeBranchingRecursive().
|
static |
store a new result in the level 2 data
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 assert(), LEVEL2DATA::branchvar1, LEVEL2DATA::branchvar2, cutoff, FALSE, i, LABdebugMessage, level2dataEnsureSize(), level2resultCreateFromData(), level2resultEqual(), level2resultPrint, LEVEL2DATA::level2results, LEVEL2DATA::level2resultssize, LEVEL2DATA::nlevel2results, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VERBLEVEL_HIGH, SCIPgetVars(), SCIPvarGetType(), TRUE, and valid.
Referenced by executeBranchingRecursive().
|
static |
Allocate and initialize the list holding the constraints.
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 assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, and SCIPallocBuffer.
Referenced by binConsDataCreate().
|
static |
Append an element to the end of the list of constraints.
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 assert(), CONSTRAINTLIST::consvars, CONSTRAINTLIST::memorysize, CONSTRAINTLIST::nconsvars, CONSTRAINTLIST::nelements, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPduplicateBlockMemoryArray, SCIPreallocBlockMemoryArray, and CONSTRAINTLIST::violated.
Referenced by addBinaryConstraint().
|
static |
Free all resources of a constraint list in opposite order to the allocation.
scip | SCIP data structure |
conslist | Pointer to the list to be freed. |
Definition at line 1413 of file branch_lookahead.c.
References assert(), i, NULL, SCIPfreeBlockMemoryArray, and SCIPfreeBuffer.
Referenced by binConsDataFree().
|
static |
Allocates and initializes the BINARYVARLIST struct.
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 assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, and SCIPallocBufferArray.
Referenced by binConsDataCreate().
|
static |
Appends a binary variable to the list, reallocating the list if necessary.
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 assert(), BINARYVARLIST::binaryvars, BINARYVARLIST::memorysize, BINARYVARLIST::nbinaryvars, NULL, and SCIPvarIsBinary().
Referenced by executeBranchingRecursive().
|
static |
Remove the last element from the list.
list | The list to remove the last element from. |
Definition at line 1491 of file branch_lookahead.c.
References assert(), BINARYVARLIST::binaryvars, BINARYVARLIST::nbinaryvars, and NULL.
Referenced by executeBranchingRecursive().
|
static |
Frees all resources allocated by a BINARYVARLIST in opposite order of allocation.
scip | SCIP data structure |
list | Pointer to the list to free |
Definition at line 1505 of file branch_lookahead.c.
References assert(), NULL, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by binConsDataFree().
|
static |
Allocate and initialize the BINCONSDATA struct.
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 assert(), binaryVarListCreate(), constraintListCreate(), maxdepth, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBuffer.
Referenced by selectVarStart().
|
static |
Free all resources in a BINCONSDATA in opposite order of allocation.
scip | SCIP data structure |
consdata | Pointer to the struct to be freed. |
Definition at line 1547 of file branch_lookahead.c.
References assert(), binaryVarListFree(), constraintListFree(), NULL, and SCIPfreeBuffer.
Referenced by selectVarStart().
|
static |
allocates the candidate list on the buffer WITHOUT initializing the contained array of candidates.
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 assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, and SCIPallocBufferArray.
Referenced by candidateListGetAllFractionalCandidates(), and ensureScoresPresent().
|
static |
allocates the given list and fills it with all fractional candidates of the current LP solution.
scip | SCIP data structure |
candidatelist | the list to allocate and fill |
Definition at line 1597 of file branch_lookahead.c.
References assert(), CANDIDATE::branchval, CANDIDATE::branchvar, candidateCreate(), candidateListCreate(), CANDIDATE::fracval, i, LABdebugMessage, lpcands, lpcandsfrac, lpcandssol, nlpcands, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIPgetLPBranchCands(), and SCIPvarGetName().
Referenced by executeBranchingRecursive(), and SCIP_DECL_BRANCHEXECLP().
|
static |
frees the allocated buffer memory of the candidate list and frees the contained candidates.
scip | SCIP data structure |
candidatelist | the list to be freed |
Definition at line 1642 of file branch_lookahead.c.
References assert(), candidateFree(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by ensureScoresPresent(), executeBranchingRecursive(), and SCIP_DECL_BRANCHEXECLP().
|
static |
keeps only the first candidates and frees the remaining ones
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 assert(), candidateFree(), CANDIDATELIST::candidates, i, CANDIDATELIST::ncandidates, NULL, SCIP_CALL, and SCIP_OKAY.
Referenced by filterCandidates().
|
static |
allocate the struct on the buffer and initialize it with the default values
scip | SCIP data structure |
domreds | The struct that has to be allocated and initialized. |
Definition at line 1720 of file branch_lookahead.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPgetNVars(), SCIPgetVars(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and vars.
Referenced by selectVarRecursive(), and selectVarStart().
|
static |
frees the given DOMAINREDUCTIONS and all contained Arrays in the opposite order of allocation
scip | SCIP data structure |
domreds | Pointer to the struct to be freed. |
Definition at line 1762 of file branch_lookahead.c.
References assert(), NULL, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by selectVarRecursive(), and selectVarStart().
|
static |
Allocates the status on the buffer memory and initializes it with default values.
scip | SCIP data structure |
status | the status to be allocated |
Definition at line 1796 of file branch_lookahead.c.
References assert(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBuffer.
Referenced by executeBranchingRecursive(), and SCIP_DECL_BRANCHEXECLP().
frees the allocated buffer memory of the status
scip | SCIP data structure |
status | the status to be freed |
Definition at line 1820 of file branch_lookahead.c.
References assert(), NULL, and SCIPfreeBuffer.
Referenced by executeBranchingRecursive(), and SCIP_DECL_BRANCHEXECLP().
|
static |
resets the array containing the sorted indices w.r.t. their score.
scorecontainer | the score container to reset |
Definition at line 1844 of file branch_lookahead.c.
References assert(), SCORECONTAINER::bestsortedcands, BMSclearMemoryArray, SCORECONTAINER::nbestsortedcands, and NULL.
Referenced by ensureScoresPresent(), and scoreContainerCreate().
|
static |
allocates the score container and inits it with default values
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 assert(), i, CONFIGURATION::maxncands, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, SCIPallocBufferArray, SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNVars(), and scoreContainterResetBestSortedCands().
Referenced by SCIP_DECL_BRANCHEXECLP().
|
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
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 assert(), CANDIDATE::branchvar, NULL, SCIP_Real, SCIPinfinity(), SCIPisGT(), SCIPvarGetProbindex(), and SCORECONTAINER::scores.
Referenced by scoreContainerSetScore(), and sortFirstCandidatesByScore().
|
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.
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 assert(), SCORECONTAINER::bestsortedcands, i, SCORECONTAINER::nbestsortedcands, and NULL.
Referenced by scoreContainerSetScore().
|
static |
sets the score for the variable in the score container
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 assert(), SCORECONTAINER::bestsortedcands, CANDIDATE::branchvar, candidateFreeWarmStartInfo(), SCORECONTAINER::downgains, findInsertionPoint(), LABdebugMessage, SCORECONTAINER::nbestsortedcands, SCORECONTAINER::nsetscores, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPisGE(), SCIPvarGetName(), SCIPvarGetProbindex(), scoreContainerUpdateSortOrder(), SCORECONTAINER::scores, SCORECONTAINER::scoresum, and SCORECONTAINER::upgains.
Referenced by ensureScoresPresent(), and selectVarRecursive().
|
static |
Frees the score container and all of its contained arrays.
scip | SCIP data structure |
scorecontainer | score container to free |
Definition at line 2030 of file branch_lookahead.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by SCIP_DECL_BRANCHEXECLP().
|
static |
branches recursively on all given candidates
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(), assert(), BMScopyMemoryArray, BRANCHINGDECISION::boundsvalid, branchingDecisionEnsureBoundArraysSize(), branchingResultDataCopy(), branchingResultDataCreate(), branchingResultDataFree(), branchingResultDataInit(), BRANCHINGDECISION::branchval, CANDIDATE::branchval, BRANCHINGDECISION::branchvar, CANDIDATE::branchvar, c, 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(), i, 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, nlpcands, DOMAINREDUCTIONS::nsimplebounds, NULL, nvars, CONSTRAINTLIST::nviolatedcons, DOMAINREDUCTIONS::nviolatedvars, BRANCHINGRESULTDATA::objval, CONFIGURATION::prefersimplebounds, BRANCHINGDECISION::proveddb, PERSISTENTDATA::restartindex, SCIP_Bool, SCIP_CALL, SCIP_Longint, 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().
|
static |
Adds the given lower bound to the DOMAINREDUCTIONS struct.
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 assert(), NULL, SCIP_Bool, SCIP_Real, SCIPadjustedVarLb(), SCIPgetSolVal(), SCIPisEQ(), SCIPisFeasGT(), SCIPisLT(), SCIPvarGetProbindex(), TRUE, and var.
Referenced by applyDeeperDomainReductions(), applySingleDeeperDomainReductions(), executeBranching(), and selectVarRecursive().
|
static |
Adds the given upper bound to the DOMAINREDUCTIONS struct.
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 assert(), NULL, SCIP_Bool, SCIP_Real, SCIPadjustedVarUb(), SCIPgetSolVal(), SCIPisEQ(), SCIPisFeasLT(), SCIPisLE(), SCIPvarGetProbindex(), TRUE, and var.
Referenced by applyDeeperDomainReductions(), applySingleDeeperDomainReductions(), executeBranching(), and selectVarRecursive().
|
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
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(), assert(), FALSE, i, DOMAINREDUCTIONS::lowerbounds, NULL, nvars, DOMAINREDUCTIONS::nviolatedvars, SCIPgetNVars(), SCIPgetVars(), TRUE, DOMAINREDUCTIONS::upperbounds, and vars.
Referenced by selectVarRecursive().
|
static |
merges the domain reduction data from the two given branching children data into the target parent data
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(), assert(), FALSE, i, LABdebugMessage, DOMAINREDUCTIONS::lowerbounds, MAX, MIN, DOMAINREDUCTIONS::nchangedvars, NULL, nvars, DOMAINREDUCTIONS::nviolatedvars, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIPgetNVars(), SCIPgetVars(), DOMAINREDUCTIONS::upperbounds, and vars.
Referenced by selectVarRecursive().
|
static |
Applies the domain reductions to the current node.
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 assert(), FALSE, i, 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, DOMAINREDUCTIONS::upperbounds, and var.
Referenced by selectVarStart().
|
static |
Copies the current LP solution into the given pointer. Needs to be freed after usage!
scip | SCIP data structure |
lpsol | pointer to store the solution into |
Definition at line 2526 of file branch_lookahead.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateLPSol(), and SCIPunlinkSol().
Referenced by selectVarStart().
|
static |
Executes the branching on a given variable with a given value.
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, assert(), BRANCHINGDECISION::boundssize, BRANCHINGDECISION::boundsvalid, BRANCHINGDECISION::branchval, BRANCHINGDECISION::branchvar, BRANCHINGDECISION::downdb, BRANCHINGDECISION::downdbvalid, BRANCHINGDECISION::downlowerbounds, BRANCHINGDECISION::downupperbounds, i, LABdebugMessage, NULL, nvars, 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, BRANCHINGDECISION::upupperbounds, var, and vars.
Referenced by SCIP_DECL_BRANCHEXECLP(), and usePreviousResult().
|
static |
Get the number of iterations the last LP needed
scip | SCIP data structure |
iterations | pointer to store the number of iterations |
Definition at line 2679 of file branch_lookahead.c.
References assert(), NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIPgetLPI(), and SCIPlpiGetIterations().
Referenced by executeBranching().
|
static |
Creates a new probing node with a new bound for the given candidate and solves the corresponding LP.
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(), assert(), CANDIDATE::branchval, CANDIDATE::branchvar, candidateHasWarmStartInfo(), candidateLoadWarmStartInfo(), BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::dualbound, BRANCHINGRESULTDATA::dualboundvalid, FALSE, getNIterationsLastLP(), i, 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, CONFIGURATION::usedomainreduction, and var.
Referenced by executeBranchingRecursive().
|
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.
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, assert(), FALSE, NULL, propagate, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcreateConsLogicor(), and TRUE.
Referenced by applyBinaryConstraints().
|
static |
Create a name for the binary constraint.
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 assert(), i, NULL, SCIP_MAXSTRLEN, SCIPsnprintf(), SCIPvarGetName(), and var.
Referenced by applyBinaryConstraints().
|
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'.
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, assert(), BINARYVARLIST::binaryvars, BINCONSDATA::binaryvars, BINCONSDATA::conslist, constraintListAppend(), i, LABdebugMessage, BINARYVARLIST::nbinaryvars, NULL, CONSTRAINTLIST::nviolatedcons, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNegatedVar(), SCIPgetSolVal(), SCIPvarIsBinary(), and var.
Referenced by executeBranchingRecursive().
|
static |
applies the binary constraints to the original problem.
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, assert(), CONSTRAINTLIST::consvars, createBinaryConstraint(), createBinaryConstraintName(), cutoff, FALSE, i, LABdebugMessage, CONSTRAINTLIST::nconsvars, CONSTRAINTLIST::nelements, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPaddClique(), SCIPaddConsNode(), SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPgetNNodes(), SCIPinfoMessage(), SCIPprintCons(), SCIPreleaseCons(), SCIPvarGetLbLocal(), SCIPvarIsBinary(), TRUE, vars, and CONSTRAINTLIST::violated.
Referenced by selectVarStart().
|
static |
checks whether the given bounds are still the bounds of the given variable
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 assert(), NULL, SCIP_Bool, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPisEQ(), SCIPisFeasIntegral(), SCIPvarGetLbLocal(), SCIPvarGetType(), SCIPvarGetUbLocal(), and var.
Referenced by selectVarRecursive().
Checks whether the branching rule should continue or terminate with the currently gathered data
status | current status |
checkdomreds | should domain reductions be checked? |
Definition at line 3198 of file branch_lookahead.c.
References assert(), STATUS::cutoff, STATUS::domred, STATUS::limitreached, STATUS::lperror, STATUS::maxnconsreached, NULL, and SCIP_Bool.
Referenced by executeBranchingRecursive(), filterCandidates(), isBranchFurtherLoopDecrement(), and selectVarStart().
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.
status | current status |
loopcounter | the counter to decrement |
Definition at line 3212 of file branch_lookahead.c.
References assert(), FALSE, isBranchFurther(), NULL, and SCIP_Bool.
Referenced by selectVarRecursive().
|
static |
determines whether the previous LAB result of a variable should be reused
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 assert(), CONFIGURATION::inscoring, PERSISTENTDATA::lastbranchid, PERSISTENTDATA::lastbranchnlps, NULL, CONFIGURATION::reevalage, CONFIGURATION::reevalagefsb, SCIP_Bool, SCIPgetNLPs(), SCIPgetNNodes(), SCIPgetVarStrongbranchLPAge(), SCIPgetVarStrongbranchNode(), and SCIPvarGetProbindex().
Referenced by selectVarRecursive().
|
static |
retrieves previous LAB result for the given variable
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 assert(), 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().
|
static |
stores the LAB result for use in a later call to the branching rule
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 assert(), 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, SCIP_Real, SCIPgetNLPs(), SCIPgetNNodes(), SCIPsetVarStrongbranchData(), and SCIPvarGetProbindex().
Referenced by selectVarRecursive().
|
static |
calculates the FSB scores for the given candidates
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 assert(), FALSE, CONFIGURATION::inscoring, NULL, CONFIGURATION::recursiondepth, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetProbingDepth(), SCIPinProbing(), selectVarRecursive(), and TRUE.
Referenced by ensureScoresPresent().
|
static |
calculates the score based on the down and up branching result
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 assert(), BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::dualbound, MAX, NULL, SCIP_Real, SCIPgetBranchScore(), and SCIPsumepsilon().
Referenced by calculateScore().
|
static |
calculates the score based on the down and up branching result
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 assert(), BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::dualbound, MAX, NULL, BRANCHINGRESULTDATA::objval, SCIP_Real, SCIPgetBranchScore(), and SCIPsumepsilon().
Referenced by calculateScore().
|
static |
calculates the score based on the down and up branching scores
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 assert(), BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::deeperscore, MAX, NULL, SCIP_Real, SCIPgetBranchScore(), SCIPisStopped(), and SCIPsumepsilon().
Referenced by calculateScore().
|
static |
calculates the score based on the down and up branching scores
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 assert(), BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::deeperscore, MAX, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::ndeepestnodes, BRANCHINGRESULTDATA::ntotalgains, NULL, SCIP_Real, SCIPgetBranchScore(), SCIPisStopped(), SCIPsumepsilon(), and BRANCHINGRESULTDATA::totalgains.
Referenced by calculateScore().
|
static |
calculates the combined gain, weighted with parameters given by the user configuration
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 assert(), BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::dualbound, MAX, MIN, CONFIGURATION::minweight, NULL, SCIP_Real, SCIPinfinity(), and CONFIGURATION::scoringfunction.
Referenced by calculateScore().
|
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
downbranchingresult | branching result of the down branch |
upbranchingresult | branching result of the up branch |
Definition at line 3694 of file branch_lookahead.c.
References assert(), BRANCHINGRESULTDATA::bestgain, MAX, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::ntotalgains, NULL, SCIP_Real, and BRANCHINGRESULTDATA::totalgains.
Referenced by calculateScore().
|
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
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 assert(), BRANCHINGRESULTDATA::bestgain, MAX, MIN, CONFIGURATION::minweight, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::ndeepestnodes, BRANCHINGRESULTDATA::ntotalgains, NULL, SCIP_Real, and BRANCHINGRESULTDATA::totalgains.
Referenced by calculateScore().
|
static |
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 assert(), BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::dualbound, MAX, BRANCHINGRESULTDATA::ndeepestcutoffs, NULL, SCIP_Real, SCIPgetBranchScore(), SCIPgetCutoffbound(), SCIPgetNPseudoBranchCands(), and SCIPsumepsilon().
Referenced by calculateScore().
|
static |
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 assert(), BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::dualbound, MAX, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::ndeepestnodes, NULL, SCIP_Real, SCIPgetBranchScore(), SCIPgetCutoffbound(), SCIPgetNLPRows(), SCIPgetNPseudoBranchCands(), and SCIPsumepsilon().
Referenced by calculateScore().
|
static |
scoring method that selects an actual scoring method based on the user configuration
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 assert(), 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().
calculates the score based on the pseudocosts of the given variable
scip | SCIP data structure |
lpcand | candidate to get the score for |
Definition at line 3943 of file branch_lookahead.c.
References assert(), CANDIDATE::branchvar, CANDIDATE::fracval, NULL, SCIP_Real, SCIPgetBranchScore(), and SCIPgetVarPseudocostVal().
Referenced by ensureScoresPresent().
|
static |
sorts the best candidates (w.r.t. the score in the container) of the candidate list to the front of the list
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 assert(), CANDIDATE::branchvar, CANDIDATELIST::candidates, findInsertionPoint(), i, LABdebugMessage, MIN, CANDIDATELIST::ncandidates, NULL, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPvarGetProbindex(), and SCORECONTAINER::scores.
Referenced by filterCandidates().
checks whether the given candidates is reliable, so that its pseudocosts may be used
scip | SCIP data structure |
branchvar | var to check for reliability |
Definition at line 4057 of file branch_lookahead.c.
References assert(), MIN, NULL, SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_Real, and SCIPgetVarPseudocostCountCurrentRun().
Referenced by ensureScoresPresent().
checks whether the current problem is feasible or cutoff
scip | SCIP data structure |
Definition at line 4079 of file branch_lookahead.c.
References assert(), NULL, SCIP_Bool, SCIPgetCutoffdepth(), and SCIPgetDepth().
Referenced by filterCandidates().
|
static |
Ensures that the scores are present in the scorecontainer for each of the candidates to consider
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, assert(), CANDIDATE::branchvar, calculateScoreFromPseudocosts(), candidateListCreate(), candidateListFree(), CANDIDATELIST::candidates, getFSBResult(), i, 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().
|
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.
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, assert(), CANDIDATE::branchvar, candidateListKeep(), CANDIDATELIST::candidates, STATUS::cutoff, SCORECONTAINER::downgains, ensureScoresPresent(), CONFIGURATION::filterbymaxgain, i, 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().
|
static |
Executes the general branching on a variable in a given direction (up/down) and repeats the algorithm from the new node
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(), assert(), 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, 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, MAX, BINARYVARLIST::nbinaryvars, CANDIDATELIST::ncandidates, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::ndeepestnodes, BRANCHINGRESULTDATA::niterations, BRANCHINGRESULTDATA::ntotalgains, NULL, BRANCHINGRESULTDATA::objval, BRANCHINGDECISION::proveddb, result, 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, and TRUE.
Referenced by selectVarRecursive().
|
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
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 assert(), BINCONSDATA::conslist, FALSE, DOMAINREDUCTIONS::nchangedvars, CONSTRAINTLIST::nelements, NULL, CONSTRAINTLIST::nviolatedcons, DOMAINREDUCTIONS::nviolatedvars, SCIP_Bool, and CONFIGURATION::storeunviolatedsol.
Referenced by selectVarStart().
|
static |
starting point to obtain a branching decision via LAB/ALAB.
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(), assert(), BINCONSDATA::binaryvars, binConsDataCreate(), binConsDataFree(), branchingDecisionCopy(), branchingDecisionIsValid(), BRANCHINGDECISION::branchval, CANDIDATE::branchval, BRANCHINGDECISION::branchvar, CANDIDATE::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().
|
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.
scip | SCIP data structure |
branchruledata | branching rule data |
Definition at line 5651 of file branch_lookahead.c.
References assert(), branchingDecisionIsValid(), LABdebugMessage, NULL, PERSISTENTDATA::olddecision, PERSISTENTDATA::oldnnodelpiterations, PERSISTENTDATA::oldnnodelps, PERSISTENTDATA::oldntotalnodes, SCIP_Bool, SCIP_VERBLEVEL_HIGH, SCIPgetNNodeLPIterations(), SCIPgetNNodeLPs(), SCIPgetNNodeZeroIterationLPs(), and SCIPgetNTotalNodes().
Referenced by SCIP_DECL_BRANCHEXECLP().
|
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.
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 assert(), branchOnVar(), LABdebugMessage, NULL, result, SCIP_BRANCHED, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, and SCIPvarGetName().
Referenced by SCIP_DECL_BRANCHEXECLP().
|
static |
free persistent data structure
scip | SCIP data structure |
branchruledata | branching rule data |
Definition at line 5717 of file branch_lookahead.c.
References assert(), FALSE, i, PERSISTENTDATA::lastbranchdownres, PERSISTENTDATA::lastbranchid, PERSISTENTDATA::lastbranchlpobjval, PERSISTENTDATA::lastbranchnlps, PERSISTENTDATA::lastbranchupres, NULL, nvars, PERSISTENTDATA::nvars, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArray.
Referenced by initBranchruleData(), and SCIP_DECL_BRANCHEXITSOL().
|
static |
initializes the branchruledata and the contained structs
scip | SCIP data structure |
branchruledata | the branch rule data to initialize |
Definition at line 5764 of file branch_lookahead.c.
References assert(), branchingDecisionInit(), freePersistent(), i, LABdebugMessage, NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPgetNBinVars(), SCIPgetNIntVars(), and TRUE.
Referenced by SCIP_DECL_BRANCHEXECLP().
|
static |
copy method for branchrule plugins (called when SCIP copies plugins)
Definition at line 5827 of file branch_lookahead.c.
References assert(), BRANCHRULE_NAME, NULL, SCIP_OKAY, and SCIPbranchruleGetName().
|
static |
destructor of branching rule to free user data (called when SCIP is exiting)
Definition at line 5838 of file branch_lookahead.c.
References assert(), NULL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPbranchruleSetData(), and SCIPfreeBlockMemory.
|
static |
initialization method of branching rule (called after problem was transformed)
Definition at line 5857 of file branch_lookahead.c.
References assert(), LABdebugMessage, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIPallocMemory, SCIPallocMemoryArray, SCIPbranchruleGetData(), SCIPgetNBinVars(), and SCIPgetNIntVars().
|
static |
deinitialization method of branching rule (called before transformed problem is freed)
Definition at line 5916 of file branch_lookahead.c.
References assert(), NULL, SCIP_OKAY, SCIPbranchruleGetData(), SCIPfreeMemory, and SCIPfreeMemoryArray.
|
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 assert(), freePersistent(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPbranchruleGetData().
|
static |
branching execution method for fractional LP solutions
Definition at line 5970 of file branch_lookahead.c.
References CONFIGURATION::abbreviated, STATUS::addedbinconss, assert(), branchingDecisionCreate(), branchingDecisionFree(), branchingDecisionIsValid(), branchOnVar(), BRANCHRULE_NAME, BRANCHINGDECISION::branchval, CANDIDATE::branchval, BRANCHINGDECISION::branchvar, CANDIDATE::branchvar, candidateListFree(), candidateListGetAllFractionalCandidates(), CANDIDATELIST::candidates, STATUS::cutoff, STATUS::depthtoosmall, STATUS::domred, STATUS::domredcutoff, BRANCHINGDECISION::downdb, i, initBranchruleData(), isUsePreviousResult(), LABdebugMessage, STATUS::limitreached, STATUS::lperror, STATUS::maxnconsreached, CANDIDATELIST::ncandidates, NULL, BRANCHINGDECISION::proveddb, result, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CONSADDED, SCIP_CUTOFF, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIP_VERBLEVEL_NORMAL, SCIPallColsInLP(), SCIPbranchruleGetData(), SCIPbranchruleGetName(), SCIPgetCurrentNode(), SCIPisExactSolve(), SCIPisStopped(), SCIPnodeGetNumber(), SCIPupdateLocalLowerbound(), SCIPvarGetName(), scoreContainerCreate(), scoreContainerFree(), selectVarStart(), statusCreate(), statusFree(), CONFIGURATION::storeunviolatedsol, BRANCHINGDECISION::updb, CONFIGURATION::usebincons, and usePreviousResult().
SCIP_RETCODE SCIPincludeBranchruleLookahead | ( | SCIP * | scip | ) |
creates the lookahead branching rule and includes it in SCIP
scip | SCIP data structure |
Definition at line 6205 of file branch_lookahead.c.
References assert(), 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().