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 | PERSISTENTDATA |
| struct | CONFIGURATION |
| struct | CONSTRAINTLIST |
| struct | BINARYVARLIST |
| struct | BINCONSDATA |
| struct | CANDIDATELIST |
| struct | DOMAINREDUCTIONS |
| struct | STATUS |
| struct | SCORECONTAINER |
Macros | |
| #define | BRANCHRULE_NAME "lookahead" |
| #define | BRANCHRULE_DESC "full strong branching over multiple levels" |
| #define | BRANCHRULE_PRIORITY 0 |
| #define | BRANCHRULE_MAXDEPTH -1 |
| #define | BRANCHRULE_MAXBOUNDDIST 1.0 |
| #define | DEFAULT_USEBINARYCONSTRAINTS TRUE |
| #define | DEFAULT_ADDCLIQUE FALSE |
| #define | DEFAULT_ADDBINCONSROW 0 |
| #define | DEFAULT_USEDOMAINREDUCTION TRUE |
| #define | DEFAULT_MAXNVIOLATEDCONS 1 |
| #define | DEFAULT_MAXNVIOLATEDBINCONS 0 |
| #define | DEFAULT_MAXNVIOLATEDDOMREDS 0 |
| #define | DEFAULT_STOREUNVIOLATEDSOL TRUE |
| #define | DEFAULT_REEVALAGE 10LL |
| #define | DEFAULT_RECURSIONDEPTH 2 |
| #define | DEFAULT_ADDNONVIOCONS FALSE |
| #define | DEFAULT_PROPAGATE TRUE |
| #define | DEFAULT_MAXPROPROUNDS -1 |
| #define | DEFAULT_ABBREVIATED FALSE |
| #define | DEFAULT_MAXNCANDS 4 |
| #define | DEFAULT_REUSEBASIS TRUE |
| #define | DEFAULT_ABBREVPSEUDO FALSE |
| #define | DEFAULT_SCORINGFUNCTION 'd' |
| #define | DEFAULT_MINWEIGHT 4.0 |
| #define | DEFAULT_MAXWEIGHT 1.0 |
| #define | LABdebugMessage(scip, lvl, ...) |
Macro Definition Documentation
◆ BRANCHRULE_NAME
| #define BRANCHRULE_NAME "lookahead" |
Definition at line 74 of file branch_lookahead.c.
Referenced by SCIP_DECL_BRANCHEXITSOL().
◆ BRANCHRULE_DESC
| #define BRANCHRULE_DESC "full strong branching over multiple levels" |
Definition at line 75 of file branch_lookahead.c.
◆ BRANCHRULE_PRIORITY
| #define BRANCHRULE_PRIORITY 0 |
Definition at line 76 of file branch_lookahead.c.
◆ BRANCHRULE_MAXDEPTH
| #define BRANCHRULE_MAXDEPTH -1 |
Definition at line 77 of file branch_lookahead.c.
◆ BRANCHRULE_MAXBOUNDDIST
| #define BRANCHRULE_MAXBOUNDDIST 1.0 |
Definition at line 78 of file branch_lookahead.c.
◆ DEFAULT_USEBINARYCONSTRAINTS
| #define DEFAULT_USEBINARYCONSTRAINTS TRUE |
should binary constraints be collected and applied?
Definition at line 80 of file branch_lookahead.c.
◆ DEFAULT_ADDCLIQUE
| #define DEFAULT_ADDCLIQUE FALSE |
add binary constraints with two variables found at the root node also as a clique?
Definition at line 81 of file branch_lookahead.c.
◆ DEFAULT_ADDBINCONSROW
| #define DEFAULT_ADDBINCONSROW 0 |
should binary constraints be added as rows to the base LP? (0: no, 1: separate, 2: as initial rows)
Definition at line 82 of file branch_lookahead.c.
◆ DEFAULT_USEDOMAINREDUCTION
| #define DEFAULT_USEDOMAINREDUCTION TRUE |
Should domain reductions be collected and applied?
Definition at line 85 of file branch_lookahead.c.
◆ DEFAULT_MAXNVIOLATEDCONS
| #define DEFAULT_MAXNVIOLATEDCONS 1 |
How many constraints that are violated by the base lp solution should be gathered until the rule is stopped and they are added?
Definition at line 86 of file branch_lookahead.c.
◆ DEFAULT_MAXNVIOLATEDBINCONS
| #define DEFAULT_MAXNVIOLATEDBINCONS 0 |
How many binary constraints that are violated by the base lp solution should be gathered until the rule is stopped and they are added?
Definition at line 89 of file branch_lookahead.c.
◆ DEFAULT_MAXNVIOLATEDDOMREDS
| #define DEFAULT_MAXNVIOLATEDDOMREDS 0 |
How many domain reductions that are violated by the base lp solution should be gathered until the rule is stopped and they are added?
Definition at line 94 of file branch_lookahead.c.
◆ DEFAULT_STOREUNVIOLATEDSOL
| #define DEFAULT_STOREUNVIOLATEDSOL TRUE |
If only non violating constraints are added, should the branching decision be stored till the next call?
Definition at line 97 of file branch_lookahead.c.
◆ DEFAULT_REEVALAGE
| #define DEFAULT_REEVALAGE 10LL |
Max number of LPs solved after which a previous prob branching results are recalculated.
Definition at line 100 of file branch_lookahead.c.
◆ DEFAULT_RECURSIONDEPTH
| #define DEFAULT_RECURSIONDEPTH 2 |
The max depth of LAB.
Definition at line 103 of file branch_lookahead.c.
◆ DEFAULT_ADDNONVIOCONS
| #define DEFAULT_ADDNONVIOCONS FALSE |
Should binary constraints, that are not violated by the base LP, be collected and added?
Definition at line 104 of file branch_lookahead.c.
◆ DEFAULT_PROPAGATE
| #define DEFAULT_PROPAGATE TRUE |
Should domain propagation be executed before each temporary node is solved?
Definition at line 107 of file branch_lookahead.c.
◆ DEFAULT_MAXPROPROUNDS
| #define DEFAULT_MAXPROPROUNDS -1 |
maximum number of propagation rounds to perform at temporary nodes (-1: unlimited)
Definition at line 110 of file branch_lookahead.c.
◆ DEFAULT_ABBREVIATED
| #define DEFAULT_ABBREVIATED FALSE |
Toggles the abbreviated LAB.
Definition at line 113 of file branch_lookahead.c.
◆ DEFAULT_MAXNCANDS
| #define DEFAULT_MAXNCANDS 4 |
If abbreviated: The max number of candidates to consider per node
Definition at line 114 of file branch_lookahead.c.
◆ DEFAULT_REUSEBASIS
| #define DEFAULT_REUSEBASIS TRUE |
If abbreviated: Should the information gathered to obtain the best candidates be reused?
Definition at line 115 of file branch_lookahead.c.
◆ DEFAULT_ABBREVPSEUDO
| #define DEFAULT_ABBREVPSEUDO FALSE |
If abbreviated: Use pseudo costs to estimate the score of a candidate.
Definition at line 118 of file branch_lookahead.c.
◆ DEFAULT_SCORINGFUNCTION
| #define DEFAULT_SCORINGFUNCTION 'd' |
default scoring function to be used
Definition at line 121 of file branch_lookahead.c.
◆ DEFAULT_MINWEIGHT
| #define DEFAULT_MINWEIGHT 4.0 |
default value for the min weight to get a weighted score of two child gains (taken from the paper)
Definition at line 122 of file branch_lookahead.c.
◆ DEFAULT_MAXWEIGHT
| #define DEFAULT_MAXWEIGHT 1.0 |
default value for the max weight to get a weighted score of two child gains (taken from the paper)
Definition at line 125 of file branch_lookahead.c.
◆ LABdebugMessage
| #define LABdebugMessage | ( | scip, | |
| lvl, | |||
| ... | |||
| ) |
Definition at line 164 of file branch_lookahead.c.
Referenced by executeBranchingRecursive(), isUsePreviousResult(), SCIP_DECL_BRANCHEXITSOL(), SCIP_DECL_BRANCHINIT(), selectVarRecursive(), selectVarStart(), and sortFirstCandidatesByScore().
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 184 of file branch_lookahead.c.
References WARMSTARTINFO::lpistate, NULL, and warmStartInfoFree().
◆ warmStartInfoIsReadable()
|
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 204 of file branch_lookahead.c.
References NULL, SCIP_CALL, SCIPblkmem(), and SCIPgetLPI().
◆ 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 214 of file branch_lookahead.c.
References candidateCreate(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfreeBlockMemory, SCIPlpiFreeNorms(), and SCIPlpiFreeState().
Referenced by candidateFree(), and warmStartInfoCreate().
◆ candidateCreate()
|
static |
Allocates the candidate on the buffer and initializes it with default values.
- Parameters
-
scip SCIP data structure candidate the candidate to allocate and initialize storelpi should the candidate be able to store its lpi information?
Definition at line 257 of file branch_lookahead.c.
Referenced by candidateListCreateWithCandidates(), and warmStartInfoFree().
◆ candidateFree()
|
static |
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 286 of file branch_lookahead.c.
References SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfreeBlockMemory, and warmStartInfoFree().
Referenced by candidateListFree(), and candidateListKeep().
◆ branchingDecisionCreate()
|
static |
Allocates a branching decision in the buffer and initiates it with default values.
- Parameters
-
scip SCIP data structure decision pointer to the decision to allocate and initiate
Definition at line 331 of file branch_lookahead.c.
Referenced by executeBranchingRecursive().
◆ branchingDecisionCopy()
|
static |
copies the data from the source branching decision storage to the target storage; this is used to store the most important information (i.e., the dual bounds obtained) so that it can be used in a subsequent call in case the LP solution did not change because we only added bound changes that did not forbid the current LP solution; however, we do not want to store all the domain changes for the two potential child nodes for this rare case, they will be identified when processing the child nodes anyway
- Parameters
-
sourcedecision the source branching decision targetdecision the target branching decision
Definition at line 364 of file branch_lookahead.c.
References branchingDecisionEnsureBoundArraysSize(), BRANCHINGDECISION::cand, and NULL.
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 382 of file branch_lookahead.c.
References BRANCHINGDECISION::boundssize, BRANCHINGDECISION::downlowerbounds, BRANCHINGDECISION::downupperbounds, NULL, SCIP_CALL, SCIPallocBlockMemoryArray, and BRANCHINGDECISION::uplowerbounds.
Referenced by selectVarStart().
◆ branchingDecisionEnsureBoundArraysSize()
|
static |
- Parameters
-
scip SCIP data structure decision branching decision nvars number of problem variables
Definition at line 394 of file branch_lookahead.c.
Referenced by branchingDecisionCopy(), and 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 417 of file branch_lookahead.c.
Referenced by executeBranchingRecursive().
◆ branchingResultDataCreate()
|
static |
Allocates a branching result in the buffer.
- Parameters
-
scip SCIP data structure resultdata pointer to the result to be allocated
Definition at line 460 of file branch_lookahead.c.
References BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::dualbound, BRANCHINGRESULTDATA::dualboundvalid, FALSE, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::niterations, NULL, BRANCHINGRESULTDATA::objval, and SCIPinfinity().
Referenced by selectVarRecursive().
◆ branchingResultDataInit()
|
static |
Initiates the branching result with default values.
- Parameters
-
scip SCIP data structure resultdata pointer to the result to be initialized
Definition at line 475 of file branch_lookahead.c.
References BRANCHINGRESULTDATA::cutoff, BRANCHINGRESULTDATA::dualbound, BRANCHINGRESULTDATA::dualboundvalid, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::niterations, NULL, and BRANCHINGRESULTDATA::objval.
Referenced by selectVarRecursive().
◆ branchingResultDataCopy()
|
static |
Copies the data from the source to the target.
- Parameters
-
sourcedata the source branching result targetdata the target branching result
Definition at line 496 of file branch_lookahead.c.
References NULL, and SCIPfreeBuffer.
◆ 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 517 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ configurationCreate()
|
static |
allocates a configuration in the buffer
- Parameters
-
scip SCIP data structure config pointer to the configuration to allocate in initialize
Definition at line 589 of file branch_lookahead.c.
References CONFIGURATION::addbinconsrow, CONFIGURATION::addnonviocons, CONFIGURATION::forcebranching, CONFIGURATION::maxnviolatedbincons, CONFIGURATION::maxnviolatedcons, CONFIGURATION::maxnviolateddomreds, and NULL.
◆ configurationCopy()
|
static |
copies the fields from configuration copysource to config
- Parameters
-
config pointer to the configuration to allocate in initialize copysource copy the settings from this config
Definition at line 604 of file branch_lookahead.c.
References NULL, and SCIPfreeBuffer.
◆ configurationFree()
|
static |
frees the allocated buffer memory of the branching result
- Parameters
-
scip SCIP data structure config pointer to the configuration to free
Definition at line 638 of file branch_lookahead.c.
References constraintListCreate(), NULL, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CONSADDED, SCIP_CONSCHANGED, SCIP_CUTOFF, SCIP_DELAYED, SCIP_DELAYNODE, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_FOUNDSOL, SCIP_INFEASIBLE, SCIP_Longint, SCIP_LONGINT_FORMAT, SCIP_NEWROUND, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_SEPARATED, SCIP_SOLVELP, SCIP_SUCCESS, SCIP_SUSPENDED, SCIP_UNBOUNDED, SCIPallocBuffer, SCIPallocBufferArray, SCIPerrorMessage, SCIPfreeBuffer, SCIPfreeBufferArray, and SCIPinfoMessage().
◆ 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 1026 of file branch_lookahead.c.
References NULL.
Referenced by configurationFree().
◆ 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 1051 of file branch_lookahead.c.
References constraintListFree(), CONSTRAINTLIST::consvars, CONSTRAINTLIST::memorysize, CONSTRAINTLIST::nconsvars, CONSTRAINTLIST::nelements, NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPduplicateBlockMemoryArray, SCIPfreeBlockMemoryArray, SCIPreallocBufferArray, and CONSTRAINTLIST::violated.
◆ constraintListFree()
|
static |
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 1086 of file branch_lookahead.c.
Referenced by constraintListAppend().
◆ binaryVarListCreate()
|
static |
Allocates and initializes the BINARYVARLIST struct.
- Parameters
-
scip SCIP data structure list Pointer to the list to be allocated and initialized. startsize The number of entries the list initially can hold.
Definition at line 1123 of file branch_lookahead.c.
References BINARYVARLIST::binaryvars, BINARYVARLIST::memorysize, BINARYVARLIST::nbinaryvars, NULL, and SCIPvarIsBinary().
◆ binaryVarListAppend()
|
static |
Appends a binary variable to the list, reallocating the list if necessary.
- Parameters
-
scip SCIP data structure list The list to add the var to. vartoadd The binary var to add to the list.
Definition at line 1145 of file branch_lookahead.c.
References BINARYVARLIST::binaryvars, BINARYVARLIST::nbinaryvars, and NULL.
Referenced by executeBranchingRecursive().
◆ binaryVarListDrop()
|
static |
Remove the last element from the list.
- Parameters
-
list The list to remove the last element from.
Definition at line 1166 of file branch_lookahead.c.
References NULL, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by executeBranchingRecursive().
◆ binaryVarListFree()
|
static |
Frees all resources allocated by a BINARYVARLIST in opposite order of allocation.
- Parameters
-
scip SCIP data structure list Pointer to the list to free
Definition at line 1180 of file branch_lookahead.c.
References binConsDataCreate().
◆ binConsDataCreate()
|
static |
Allocate and initialize the BINCONSDATA struct.
- Parameters
-
scip SCIP data structure consdata Pointer to the struct to be allocated and initialized. maxdepth The depth of the recursion as an upper bound of branch vars to hold. nstartcons The start size of the array containing the constraints.
Definition at line 1201 of file branch_lookahead.c.
Referenced by binaryVarListFree(), and 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 1222 of file branch_lookahead.c.
References candidateListCreate().
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 1246 of file branch_lookahead.c.
Referenced by binConsDataFree().
◆ candidateListCreateWithCandidates()
|
static |
- Parameters
-
scip SCIP data structure candidatelist the candidate list to allocate ncandidates the number of candidates the list must hold storewarmstartinfo should the candidates be able to store warm start information?
Definition at line 1272 of file branch_lookahead.c.
References candidateCreate(), candidateListGetAllFractionalCandidates(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, and SCIP_Real.
◆ candidateListGetAllFractionalCandidates()
|
static |
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 storewarmstartinfo should warm start info of the LP be stored in the candidates?
Definition at line 1297 of file branch_lookahead.c.
Referenced by candidateListCreateWithCandidates(), and executeBranchingRecursive().
◆ candidateListFree()
|
static |
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 1336 of file branch_lookahead.c.
References candidateFree(), candidateListKeep(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by executeBranchingRecursive().
◆ candidateListKeep()
|
static |
Keeps only the first candidates and frees the remaining ones
- Parameters
-
scip SCIP data structure candidatelist the list to allocate and fill nindices the number of candidates to keep (starting from 0)
Definition at line 1367 of file branch_lookahead.c.
References candidateFree(), CANDIDATELIST::candidates, CANDIDATELIST::ncandidates, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, and SCIP_Real.
Referenced by candidateListFree().
◆ domainReductionsCreate()
|
static |
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 1413 of file branch_lookahead.c.
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 1454 of file branch_lookahead.c.
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 1488 of file branch_lookahead.c.
References NULL, SCIP_Real, and SCIPfreeBuffer.
Referenced by executeBranchingRecursive().
◆ statusFree()
frees the allocated buffer memory of the status
- Parameters
-
scip SCIP data structure status the status to be freed
Definition at line 1512 of file branch_lookahead.c.
References NULL.
Referenced by executeBranchingRecursive().
◆ scoreContainterResetBestSortedIndices()
|
static |
resets the array containing the sorted indices w.r.t. their score.
- Parameters
-
scorecontainer the score container to reset
Definition at line 1532 of file branch_lookahead.c.
References NULL.
◆ 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 1543 of file branch_lookahead.c.
◆ findInsertionPoint()
|
static |
Finds the insertion index for the given score in the candidate list. The score of each candidate is taken from the scorecontainer. The first elements of the candidate list have to be sorted, as this method uses binary search to find the correct insertion point
- Parameters
-
scip SCIP data structure scorecontainer container with all the scores for each candidate scoretoinsert score to find the insertion index for candidates candidate list where the first nsorted elements are sorted (w.r.t. their score) ncandidates number of elements in candidates to consider, starting from 0
Definition at line 1579 of file branch_lookahead.c.
Referenced by sortFirstCandidatesByScore().
◆ scoreContainerUpdateSortOrder()
|
static |
Inserts the given probindex into the sorted array in the container, moving all indices after it to the right. Then returns the element that does not fit into the array any longer.
- Parameters
-
scorecontainer container to insert the index into candidate the probindex of a variable to store insertpoint point to store the index at
Definition at line 1624 of file branch_lookahead.c.
References SCORECONTAINER::bestsortedcands, NULL, SCIP_Real, and 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
Definition at line 1649 of file branch_lookahead.c.
Referenced by scoreContainerUpdateSortOrder(), 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 1693 of file branch_lookahead.c.
◆ selectVarRecursive()
|
static |
branches recursively on all given candidates
- Parameters
-
scip SCIP data structure status current status persistent container to store data over multiple calls to the branching rule; or NULL config the configuration of the branching rule baselpsol base lp solution domainreductions container collecting all domain reductions found binconsdata container collecting all binary constraints candidatelist list of candidates to branch on decision struct to store the final decision scorecontainer container to retrieve already calculated scores storewarmstartinfo should LP information be stored? recursiondepth remaining recursion depth lpobjval base LP objective value 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
Definition at line 3978 of file branch_lookahead.c.
References CONFIGURATION::abbreviated, addLowerBoundProofNode(), addUpperBound(), addUpperBoundProofNode(), applyDeeperDomainReductions(), applySingleDeeperDomainReductions(), areBoundsChanged(), BMScopyMemoryArray, BRANCHINGDECISION::boundsvalid, branchingDecisionEnsureBoundArraysSize(), branchingResultDataCreate(), branchingResultDataFree(), branchingResultDataInit(), CANDIDATE::branchval, CANDIDATE::branchvar, calculateScore(), calculateWeightedGain(), BRANCHINGDECISION::cand, CANDIDATELIST::candidates, BINCONSDATA::conslist, BRANCHINGRESULTDATA::cutoff, STATUS::cutoff, domainReductionsCreate(), domainReductionsFree(), STATUS::domred, BRANCHINGDECISION::downdb, BRANCHINGDECISION::downdbvalid, BRANCHINGDECISION::downlowerbounds, BRANCHINGDECISION::downupperbounds, BRANCHINGRESULTDATA::dualbound, BRANCHINGRESULTDATA::dualboundvalid, executeBranchingRecursive(), FALSE, getOldBranching(), isBranchFurtherLoopDecrement(), isStoreDecision(), isUseOldBranching(), LABdebugMessage, STATUS::limitreached, DOMAINREDUCTIONS::lowerbounds, STATUS::lperror, MAX, STATUS::maxnconsreached, CONFIGURATION::maxnviolatedbincons, CONFIGURATION::maxnviolatedcons, CONFIGURATION::maxnviolateddomreds, MIN, CANDIDATELIST::ncandidates, DOMAINREDUCTIONS::nchangedvars, BRANCHINGRESULTDATA::ndeepestcutoffs, CONSTRAINTLIST::nelements, BRANCHINGRESULTDATA::niterations, NULL, CONSTRAINTLIST::nviolatedcons, DOMAINREDUCTIONS::nviolatedvars, BRANCHINGRESULTDATA::objval, BRANCHINGDECISION::proveddb, PERSISTENTDATA::restartindex, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIP_VERBLEVEL_NORMAL, SCIPallColsInLP(), SCIPgetCutoffbound(), SCIPgetLPI(), SCIPgetNVars(), SCIPgetProbingDepth(), SCIPinfinity(), SCIPisEQ(), SCIPisGE(), SCIPisStopped(), SCIPisStrongbranchDownFirst(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), scoreContainerSetScore(), TRUE, updateOldBranching(), BRANCHINGDECISION::updb, BRANCHINGDECISION::updbvalid, BRANCHINGDECISION::uplowerbounds, DOMAINREDUCTIONS::upperbounds, BRANCHINGDECISION::upupperbounds, CONFIGURATION::usebincons, and CONFIGURATION::usedomainreduction.
Referenced by executeBranchingRecursive(), and selectVarStart().
◆ selectVarStart()
|
static |
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 status current status decision struct to store the final decision scorecontainer container to retrieve already calculated scores storewarmstartinfo should lp information be stored? candidatelist list of candidates to branch on
Definition at line 4494 of file branch_lookahead.c.
References CONFIGURATION::abbreviated, STATUS::addedbinconss, applyBinaryConstraints(), applyDomainReductions(), BINCONSDATA::binaryvars, binConsDataCreate(), binConsDataFree(), branchingDecisionCopy(), branchingDecisionIsValid(), CANDIDATE::branchvar, BRANCHINGDECISION::cand, CANDIDATELIST::candidates, BINCONSDATA::conslist, copyCurrentSolution(), STATUS::cutoff, STATUS::depthtoosmall, domainReductionsCreate(), domainReductionsFree(), STATUS::domred, STATUS::domredcutoff, BRANCHINGDECISION::downdb, BRANCHINGDECISION::downdbvalid, FALSE, filterCandidates(), CONFIGURATION::forcebranching, isBranchFurther(), isStoreDecision(), isUsePreviousResult(), LABdebugMessage, BINARYVARLIST::nbinaryvars, CANDIDATELIST::ncandidates, NULL, PERSISTENTDATA::prevbinsolution, PERSISTENTDATA::prevdecision, BRANCHINGDECISION::proveddb, CONFIGURATION::recursiondepth, SCIP_Bool, SCIP_CALL, SCIP_MAXTREEDEPTH, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPABORT, SCIPareSolsEqual(), SCIPceil(), SCIPenableVarHistory(), SCIPendStrongbranch(), SCIPfreeSol(), SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetLPObjval(), SCIPgetProbingDepth(), SCIPinProbing(), SCIPlinkLPSol(), SCIPstartStrongbranch(), SCIPunlinkSol(), SCIPvarGetName(), selectVarRecursive(), TRUE, BRANCHINGDECISION::updb, BRANCHINGDECISION::updbvalid, CONFIGURATION::usebincons, and CONFIGURATION::usedomainreduction.
◆ addLowerBoundProofNode()
|
static |
Adds the given lower bound to the container 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. domainreductions The struct the domain reduction should be added to.
Definition at line 1759 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ addLowerBound()
|
static |
Add a lower bound to the DOMAINREDUCTIONS struct. This is used as a wrapper to the 'addLowerBoundProofNode' method.
- 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. domainreductions The struct the domain reduction should be added to.
Definition at line 1819 of file branch_lookahead.c.
◆ addUpperBoundProofNode()
|
static |
Adds the given upper bound to the container 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. domainreductions The struct the domain reduction should be added to.
Definition at line 1840 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ addUpperBound()
|
static |
Add a lower bound to the DOMAINREDUCTIONS struct. This is used as a wrapper to the 'addUpperBoundProofNode' method.
- 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. domainreductions The struct the domain reduction should be added to.
Definition at line 1902 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ applySingleDeeperDomainReductions()
|
static |
apply the domain reductions from a single struct to another one; this may be used in case one of the two child problems of a variable is infeasible
- Parameters
-
scip SCIP data structure baselpsol The LP solution of the base problem. Used to check whether the domain reduction is violated by it. targetdomreds The target that should be filled with the merged data. domreds source domain reductions
Definition at line 1925 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ applyDeeperDomainReductions()
|
static |
merges the domain reduction data from the two given branching children data into the target parent data
- Parameters
-
scip SCIP data structure baselpsol The LP solution of the base problem. Used to check whether the domain reduction is violated by it. 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 1968 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ applyDomainReductions()
|
static |
Applies the domain reductions to the current node.
- Parameters
-
scip SCIP data structure 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 2039 of file branch_lookahead.c.
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 2208 of file branch_lookahead.c.
References CANDIDATE::branchvar, BRANCHINGDECISION::cand, NULL, and SCIP_Real.
Referenced by selectVarStart().
◆ branchOnVar()
|
static |
Executes the branching on a given variable with a given value.
- Parameters
-
scip SCIP data structure decision the decision with all the needed data
Definition at line 2227 of file branch_lookahead.c.
Referenced by isUsePreviousResult().
◆ storeWarmStartInfo()
|
static |
Store the current lp solution in the warm start info for further usage.
- Parameters
-
scip SCIP data structure warmstartinfo the warm start info in which the data should be stored
Definition at line 2355 of file branch_lookahead.c.
Referenced by executeBranchingRecursive().
◆ restoreFromWarmStartInfo()
|
static |
Sets the lp state and norms of the current node to the values stored in the warm start info.
- Parameters
-
scip SCIP data structure warmstartinfo the warm start info containing the stored data
Definition at line 2386 of file branch_lookahead.c.
◆ getNIterationsLastLP()
|
static |
Get the number of iterations the last LP needed
- Parameters
-
scip SCIP data structure iterations pointer to store the number of iterations
Definition at line 2411 of file branch_lookahead.c.
◆ executeBranching()
|
static |
Creates a new probing node with a new bound for the given candidate and solves the corresponding LP.
- Parameters
-
scip SCIP data structure config configuration to control the behavior downbranching the branching direction candidate the candidate to branch on resultdata pointer to the result data which gets filled with the status baselpsol the base lp solution domreds struct to store the domain reduction found during propagation status status will contain updated lperror and limit fields
Definition at line 2435 of file branch_lookahead.c.
Referenced by executeBranchingRecursive().
◆ createBinaryConstraint()
|
static |
Creates a logic or constraint based on the given 'consvars'. This array has to consist of the negated versions of the variables present on a cutoff "path" (path means all variables from the root directly to the cutoff node). Let x_1, ..., x_n be the variables on a path to a cutoff with the branchings x_i <= 1 for all i. Summed up the constraints would look like x_1 + ... x_n <= n-1. Let y_i = 1 - x_i. Then we have y_1 + ... + y_n >= 1 which is a logic or constraint.
- Parameters
-
scip SCIP data structure config configuration containing flags changing the behavior constraint pointer to store the created constraint in constraintname name of the new constraint consvars array containing the negated binary vars nconsvars the number of elements in 'consvars'
Definition at line 2639 of file branch_lookahead.c.
◆ createBinaryConstraintName()
|
static |
Create a name for the binary constraint.
- Parameters
-
binaryvars the variables contained in the constraint nbinaryvars the number of elements in 'binaryvars' constraintname the char pointer to store the name in
Definition at line 2682 of file branch_lookahead.c.
References addBinaryConstraint(), NULL, SCIP_MAXSTRLEN, and SCIPvarGetName().
◆ addBinaryConstraint()
|
static |
Add the constraints found during the lookahead branching. The implied binary bounds were found when two or more consecutive branchings of binary variables were cutoff. Then these branching constraints can be combined into a single 'binary constraint'.
- Parameters
-
scip SCIP data structure config the configuration of the branching rule binconsdata collected binary constraints baselpsol the original lp solution, used to check the violation of the constraint
Definition at line 2715 of file branch_lookahead.c.
Referenced by createBinaryConstraintName(), and executeBranchingRecursive().
◆ applyBinaryConstraints()
|
static |
applies the binary constraints to the original problem.
- Parameters
-
scip SCIP data structure basenode original branching node conslist list of constraints to be added config the configuration of the branching rule consadded pointer to store whether at least one constraint was added cutoff pointer to store whether the original problem was made infeasible boundchange pointer to store whether a bound change has been applied by adding the constraint as a clique
Definition at line 2785 of file branch_lookahead.c.
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 2914 of file branch_lookahead.c.
References STATUS::cutoff, STATUS::domred, STATUS::limitreached, STATUS::lperror, STATUS::maxnconsreached, and NULL.
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 2934 of file branch_lookahead.c.
References FALSE, NULL, and SCIP_Bool.
Referenced by executeBranchingRecursive(), 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 2948 of file branch_lookahead.c.
References NULL, CONFIGURATION::reevalage, SCIPgetNNodes(), SCIPgetVarStrongbranchLPAge(), and SCIPgetVarStrongbranchNode().
Referenced by selectVarRecursive().
◆ isUseOldBranching()
|
static |
Determines whether previous branching results of a variable can be reused
- Parameters
-
scip SCIP data structure config the configuration of the branching rule branchvar variable to check
Definition at line 2968 of file branch_lookahead.c.
References NULL.
Referenced by selectVarRecursive().
◆ getOldBranching()
|
static |
Retrieves previous branching results for the given variable
- Parameters
-
scip SCIP data structure persistent data storage over multiple calls to the rulel 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 2985 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ updateOldBranching()
|
static |
Stores the data for use in a later call to the branching rule
- Parameters
-
scip SCIP data structure persistent data storage over multiple calls to the 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 3036 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ getFSBResult()
|
static |
calculates the FSB scores for the given candidates
- Parameters
-
scip SCIP data structure parentconfig main configuration candidatelist the candidates to get the scores for status status getting updated by the FSB routine scorecontainer container for the scores and lpi information
Definition at line 3073 of file branch_lookahead.c.
◆ 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 3186 of file branch_lookahead.c.
◆ calculateWeightedGain()
|
static |
calculates the combined gain, weighted with parameters given by the user configuration
- Parameters
-
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 3227 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ 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 3266 of file branch_lookahead.c.
◆ calculateScore()
|
static |
scoring method that selects an actual scoring method based on the user configuration
- Parameters
-
scip SCIP data structure config LAB configuration branchvar variable to get the score for downbranchingresult branching result of the down branch upbranchingresult branching result of the up branch lpobjval objective value to get difference to as gain
Definition at line 3295 of file branch_lookahead.c.
Referenced by selectVarRecursive().
◆ calculateScoreFromPseudocosts()
calculates the score based on the pseudocosts of the given variable
- Parameters
-
scip SCIP data structure lpcand candidate to get the score for
Definition at line 3330 of file branch_lookahead.c.
◆ 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 3379 of file branch_lookahead.c.
References CANDIDATE::branchvar, CANDIDATELIST::candidates, findInsertionPoint(), isCandidateReliable(), LABdebugMessage, MIN, CANDIDATELIST::ncandidates, NULL, SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPgetVarPseudocostCountCurrentRun(), SCIPvarGetProbindex(), and SCORECONTAINER::scores.
◆ isCandidateReliable()
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 3444 of file branch_lookahead.c.
Referenced by sortFirstCandidatesByScore().
◆ isCurrentNodeCutoff()
checks whether the current problem is feasible or cutoff
- Parameters
-
scip SCIP data structure
Definition at line 3466 of file branch_lookahead.c.
◆ ensureScoresPresent()
|
static |
Ensures that the scores are present in the scorecontainer for each of the candidates to consider
- Parameters
-
scip SCIP data structure config main configuration status current status allcandidates list containing all candidates to consider scorecontainer container to store the scores for later usage
Definition at line 3477 of file branch_lookahead.c.
◆ filterBestCandidates()
|
static |
Gets the best candidates w.r.t. the scores stored in the scorecontainer and stores them in the given list
- Parameters
-
scip SCIP data structure config the configuration of the branching rule scorecontainer container to store the scores for later usage candidatelist list containing all candidates to consider
Definition at line 3594 of file branch_lookahead.c.
◆ getBestCandidates()
|
static |
Gets the best candidates, according the FSB score of each candidate
- Parameters
-
scip SCIP data structure config the configuration of the branching rule status current status candidatelist list containing all candidates to consider scorecontainer container to store the scores for later usage
Definition at line 3636 of file branch_lookahead.c.
◆ 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 config the configuration of the branching rule status current status scorecontainer container to store the scores for later usage; or NULL if not running the abbreviated version of lookahead branching candidatelist list with the candidates
Definition at line 3697 of file branch_lookahead.c.
Referenced by executeBranchingRecursive(), and selectVarStart().
◆ executeBranchingRecursive()
|
static |
Executes the general branching on a node 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 recursiondepth remaining recursion depth domainreductions container collecting all domain reductions found binconsdata container collecting all binary constraints branchingresult container to store the result of the branching in scorecontainer container to retrieve already calculated scores; or NULL storewarmstartinfo should lp information be stored? downbranching should we branch up or down in here?
Definition at line 3736 of file branch_lookahead.c.
References CONFIGURATION::abbreviated, addBinaryConstraint(), BRANCHINGRESULTDATA::bestgain, binaryVarListAppend(), binaryVarListDrop(), BINCONSDATA::binaryvars, branchingDecisionCreate(), branchingDecisionFree(), CANDIDATE::branchval, CANDIDATE::branchvar, candidateListFree(), candidateListGetAllFractionalCandidates(), BRANCHINGRESULTDATA::cutoff, STATUS::cutoff, CANDIDATE::downwarmstartinfo, BRANCHINGRESULTDATA::dualbound, BRANCHINGRESULTDATA::dualboundvalid, executeBranching(), FALSE, filterCandidates(), CANDIDATE::fracval, isBranchFurther(), LABdebugMessage, STATUS::limitreached, STATUS::lperror, MAX, BINARYVARLIST::nbinaryvars, CANDIDATELIST::ncandidates, BRANCHINGRESULTDATA::ndeepestcutoffs, BRANCHINGRESULTDATA::niterations, BRANCHINGRESULTDATA::ntotalgains, NULL, BRANCHINGRESULTDATA::objval, BRANCHINGDECISION::proveddb, CONFIGURATION::reusebasis, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIPallColsInLP(), SCIPbacktrackProbing(), SCIPgetNegatedVar(), SCIPgetProbingDepth(), SCIPisGE(), SCIPupdateVarPseudocost(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), selectVarRecursive(), statusCreate(), statusFree(), storeWarmStartInfo(), BRANCHINGRESULTDATA::totalgains, TRUE, CANDIDATE::upwarmstartinfo, and CONFIGURATION::usebincons.
Referenced by selectVarRecursive().
◆ isStoreDecision()
|
static |
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 4474 of file branch_lookahead.c.
Referenced by selectVarRecursive(), and selectVarStart().
◆ 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 currentsol the current base lp solution persistent container to store data over multiple calls to the branching rule
Definition at line 4756 of file branch_lookahead.c.
References branchOnVar(), LABdebugMessage, NULL, SCIP_CALL, and SCIP_VERBLEVEL_FULL.
Referenced by selectVarStart().
◆ usePreviousResult()
|
static |
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 decision decision to branch on result the pointer to the branching result
Definition at line 4780 of file branch_lookahead.c.
◆ freePersistent()
|
static |
free persistent data structure
- Parameters
-
scip SCIP data structure branchruledata branching rule data
Definition at line 4807 of file branch_lookahead.c.
References FALSE, isInitBranchruleData(), PERSISTENTDATA::lastbranchdownres, PERSISTENTDATA::lastbranchid, PERSISTENTDATA::lastbranchlpobjval, PERSISTENTDATA::lastbranchnlps, PERSISTENTDATA::lastbranchupres, NULL, PERSISTENTDATA::prevbinsolution, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeSol(), SCIPgetNBinVars(), and SCIPgetNIntVars().
Referenced by SCIP_DECL_BRANCHINIT().
◆ isInitBranchruleData()
|
static |
checks whether the branchruledata struct has to be (re-)initialized
- Parameters
-
scip SCIP data structure branchruledata branch rule data that may get initialized
Definition at line 4856 of file branch_lookahead.c.
References NULL.
Referenced by freePersistent().
◆ initBranchruleData()
|
static |
initializes the branchruledata and the contained structs
- Parameters
-
scip SCIP data structure branchruledata the branch rule data to initialize
Definition at line 4871 of file branch_lookahead.c.
◆ SCIP_DECL_BRANCHCOPY()
|
static |
copy method for branchrule plugins (called when SCIP copies plugins)
Definition at line 4929 of file branch_lookahead.c.
References NULL, SCIPbranchruleGetData(), and SCIPfreeMemory.
◆ SCIP_DECL_BRANCHFREE()
|
static |
destructor of branching rule to free user data (called when SCIP is exiting)
Definition at line 4942 of file branch_lookahead.c.
◆ SCIP_DECL_BRANCHINIT()
|
static |
initialization method of branching rule (called after problem was transformed)
Definition at line 4963 of file branch_lookahead.c.
References freePersistent(), LABdebugMessage, NULL, SCIP_CALL, SCIP_DECL_BRANCHEXIT, SCIP_DECL_BRANCHEXITSOL(), SCIP_OKAY, SCIP_VERBLEVEL_FULL, SCIP_VERBLEVEL_HIGH, SCIPallocMemory, SCIPallocMemoryArray, 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 5047 of file branch_lookahead.c.
References BRANCHRULE_NAME, LABdebugMessage, NULL, SCIP_Bool, SCIP_VERBLEVEL_HIGH, and SCIPbranchruleGetName().
Referenced by SCIP_DECL_BRANCHINIT().
◆ SCIP_DECL_BRANCHEXECLP()
|
static |
branching execution method for fractional LP solutions
Definition at line 5064 of file branch_lookahead.c.
◆ SCIPincludeBranchruleLookahead()
| SCIP_RETCODE SCIPincludeBranchruleLookahead | ( | SCIP * | scip | ) |
creates the lookahead branching rule and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 5266 of file branch_lookahead.c.
Referenced by SCIPincludeDefaultPlugins().