![]() |
MAiNGO
|
This class contains the main algorithm, including handling of pre-processing routines and managing the B&B tree as well as the respective sub-solvers. More...
#include <bab.h>
Public Member Functions | |
BranchAndBound (const std::vector< babBase::OptimizationVariable > &variables, std::shared_ptr< lbp::LowerBoundingSolver > LBSIn, std::shared_ptr< ubp::UpperBoundingSolver > UBSIn, Settings *settingsIn, Logger *loggerIn, const unsigned nvarWOaux) | |
Constructor, stores information on problem and settings. More... | |
~BranchAndBound () | |
Destructor. More... | |
babBase::enums::BAB_RETCODE | solve (babBase::BabNode &rootNodeIn, double &solutionValue, std::vector< double > &solutionPoint, const double preprocessTime, double &timePassed) |
Main function to solve the optimization problem. More... | |
double | get_iterations () |
Function returning the number of iterations. More... | |
double | get_max_nodes_in_memory () |
Function returning the maximum number of nodes in memory. More... | |
double | get_UBP_count () |
Function returning number of UBD problems solved. More... | |
double | get_LBP_count () |
Function returning number of LBD problems solved. More... | |
double | get_final_LBD () |
Function returning the final LBD. More... | |
double | get_final_abs_gap () |
Function returning the final absolute gap. More... | |
double | get_final_rel_gap () |
Function returning the final relative gap. More... | |
double | get_first_found () |
Function returning the ID of the node where the incumbent was first found. More... | |
double | get_nodes_left () |
Function returning the number of nodes left after termination of B&B. More... | |
Private Types | |
enum | _TERMINATION_TYPE { _TERMINATED = 0, _TERMINATED_WORKERS_ACTIVE, _NOT_TERMINATED } |
Enum for representing different termination types in B&B. More... | |
Private Member Functions | |
std::tuple< bool, bool, int, int, double, std::vector< double >, bool, double, std::vector< double > > | _process_node (babBase::BabNode ¤tNodeInOut) |
Function processing the current node. More... | |
bool | _preprocess_node (babBase::BabNode ¤tNodeInOut) |
Function for pre-processing the current node. Includes bound tightening and OBBT. More... | |
std::tuple< bool, bool, double, std::vector< double >, lbp::LbpDualInfo > | _solve_LBP (const babBase::BabNode ¤tNode) |
Function invoking the LBS to solve the lower bounding problem. More... | |
std::tuple< bool, bool, double > | _solve_UBP (const babBase::BabNode ¤tNode, std::vector< double > &ubpSolutionPoint, const double currentLBD) |
Function invoking the UBS to solve the upper bounding problem. More... | |
bool | _postprocess_node (babBase::BabNode ¤tNodeInOut, const std::vector< double > &lbpSolutionPoint, const lbp::LbpDualInfo &dualInfo) |
Function for post-processing the current node. Includes bound DBBT and probing. More... | |
void | _update_incumbent_and_fathom (const double solval, const std::vector< double > sol, const unsigned int currentNodeID) |
Function for updating the incumbent and fathoming accordingly. More... | |
void | _update_lowest_lbd () |
Function for updating the global lower bound. More... | |
void | _check_if_more_scaling_needed () |
Function which checks whether it is necessary to activate scaling within the LBD solver. This is a heuristic approach, which does not affect any deterministic optimization assumptions. More... | |
_TERMINATION_TYPE | _check_termination () |
Function for checking if the B&B algorithm terminated. More... | |
void | _display_and_log_progress (const double currentNodeLBD, const babBase::BabNode ¤tNode) |
Function for printing the current progress on the screen and appending it to the internal log to be written to file later. More... | |
void | _print_termination (std::string message) |
Function printing a termination message. More... | |
void | _print_one_node (const double theLBD, const int ID, const std::vector< double > lowerVarBounds, const std::vector< double > upperVarBounds) |
Function printing one node. More... | |
void | _print_one_node (const double theLBD, const int ID, const std::vector< double > lowerVarBounds, const std::vector< double > upperVarBounds, std::ostream &outstream) |
Function printing one node. More... | |
void | _print_one_node (const double theLBD, const babBase::BabNode &theNode) |
Function printing one node. More... | |
void | _print_one_node (const double theLBD, const babBase::BabNode &theNode, std::ostream &outstream) |
Function printing one node. More... | |
Private Attributes | |
std::unique_ptr< babBase::Brancher > | _brancher |
std::shared_ptr< ubp::UpperBoundingSolver > | _UBS |
std::shared_ptr< lbp::LowerBoundingSolver > | _LBS |
Settings * | _maingoSettings |
Internal variables for storing problem parameters | |
std::vector< babBase::OptimizationVariable > | _originalVariables |
const unsigned | _nvar |
const unsigned | _nvarWOaux |
std::vector< double > | _lowerVarBoundsOrig |
std::vector< double > | _upperVarBoundsOrig |
Internal variables for storing solution information | |
std::vector< double > | _incumbent |
std::vector< double > | _initialPoint |
double | _ubd |
double | _lbd |
double | _bestLbdFathomed |
bool | _foundFeas |
unsigned | _firstFound |
unsigned | _incumbentNodeId |
babBase::enums::BAB_RETCODE | _status |
Internal variables for heuristic approaches | |
double | _lbdOld |
unsigned | _lbdNotChanged |
bool | _moreScalingActivated |
Internal variables to store statistics | |
unsigned | _nNodesTotal |
unsigned | _nNodesLeft |
unsigned | _nNodesMaxInMemory |
unsigned | _nNodesDeleted |
unsigned | _nNodesFathomed |
Counters | |
unsigned | _lbdcnt |
unsigned | _ubdcnt |
double | _timePassed |
double | _timePreprocess |
unsigned | _daysPassed |
Internal variables used for printing | |
unsigned | _linesprinted |
unsigned | _iterations |
unsigned | _iterationsgap |
bool | _printNewIncumbent |
unsigned | _writeToLogEverySec |
Logger * | _logger |
This class contains the main algorithm, including handling of pre-processing routines and managing the B&B tree as well as the respective sub-solvers.
The class BranchAndBound implements a basic branch-and-bound (BaB) solver with some simple features for range reduction. These include optimization-based range reduction (OBBT; cf., e.g., Gleixner et al., J. Glob. Optim. 67 (2017) 731), which can be conducted multiple times at the root node, and also once at every node of the BAB tree, as well as duality-based bounds tightening (DBBT) and probing (cf. Ryoo&Sahinidis, Comput. Chem. Eng. 19 (1995) 551). It also contains a multi-start local search from randomly generated initial points at the root node. Lower and upper bounding are conducted by the respective lower and upper bounding solvers (LBS / UBS).
|
private |
Enum for representing different termination types in B&B.
BranchAndBound::BranchAndBound | ( | const std::vector< babBase::OptimizationVariable > & | variables, |
std::shared_ptr< lbp::LowerBoundingSolver > | LBSIn, | ||
std::shared_ptr< ubp::UpperBoundingSolver > | UBSIn, | ||
Settings * | settingsIn, | ||
Logger * | loggerIn, | ||
const unsigned | nvarWOaux | ||
) |
Constructor, stores information on problem and settings.
[in] | variables | is a vector containing the initial optimization variables defined in problem.h |
[in] | LBSIn | is a pointer to the LowerBoundingSolver object |
[in] | UBSIn | is a pointer to the UpperBoundingSolver object |
[in] | settingsIn | is a pointer to an object containing the settings for the Branch-and-Bound solvers |
[in] | loggerIn | is a pointer to the MAiNGO logger object |
[in] | nvarWOaux | is the number of optimization variables without the additional auxiliary variables added by the LBP_addAuxiliaryVars option |
|
inline |
Destructor.
|
private |
Function which checks whether it is necessary to activate scaling within the LBD solver. This is a heuristic approach, which does not affect any deterministic optimization assumptions.
|
private |
Function for checking if the B&B algorithm terminated.
|
private |
Function for printing the current progress on the screen and appending it to the internal log to be written to file later.
[in] | currentNodeLBD | is the lower bound for the current node |
[in] | currentNode | is the current node |
|
private |
Function for post-processing the current node. Includes bound DBBT and probing.
[in,out] | currentNodeInOut | The node to be processed |
[in] | lbpSolutionPoint | Solution point of the lower bounding problem |
[in] | dualInfo | is a struct containing information from the LP solved during LBP |
|
private |
Function for pre-processing the current node. Includes bound tightening and OBBT.
[in,out] | currentNodeInOut | The node to be processed |
|
private |
Function printing one node.
[in] | theLBD | is the lower bound of the node |
[in] | ID | is the id of the node |
[in] | lowerVarBounds | are the variables lower bounds |
[in] | upperVarBounds | are the variables upper bounds |
|
private |
Function printing one node.
[in] | theLBD | is the lower bound of the node |
[in] | ID | is the id of the node |
[in] | lowerVarBounds | are the variables lower bounds |
[in] | upperVarBounds | are the variables upper bounds |
[in] | outstream | is the stream to be written to, e.g., an error message |
|
inlineprivate |
Function printing one node.
[in] | theLBD | is the lower bound of the node |
[in] | theNode | is the node to be printed |
|
inlineprivate |
Function printing one node.
[in] | theLBD | is the lower bound of the node |
[in] | theNode | is the node to be printed |
[in] | outstream | is the stream to be written to, e.g., an error message |
|
private |
Function printing a termination message.
[in] | message | is a string holding the message to print |
|
private |
Function processing the current node.
[in,out] | currentNodeInOut | The node to be processed |
|
private |
Function invoking the LBS to solve the lower bounding problem.
[in] | currentNode | The node to be processed |
|
private |
Function invoking the UBS to solve the upper bounding problem.
[in] | currentNode | The node to be processed |
[in,out] | ubpSolutionPoint | On input: initial point for local search. On output: solution point. |
[in] | currentLBD | Lower bound of current Node. Needed for sanity check. |
|
private |
Function for updating the incumbent and fathoming accordingly.
[in] | solval | is the value of the processed solution |
[in] | sol | is the solution point |
[in] | currentNodeID | is the ID of the new node holding the incumbent (it is used instead of directly giving the node to match the parallel implementation) |
|
private |
Function for updating the global lower bound.
|
inline |
Function returning the final absolute gap.
|
inline |
Function returning the final LBD.
|
inline |
Function returning the final relative gap.
|
inline |
Function returning the ID of the node where the incumbent was first found.
|
inline |
Function returning the number of iterations.
|
inline |
Function returning number of LBD problems solved.
|
inline |
Function returning the maximum number of nodes in memory.
|
inline |
Function returning the number of nodes left after termination of B&B.
|
inline |
Function returning number of UBD problems solved.
babBase::enums::BAB_RETCODE BranchAndBound::solve | ( | babBase::BabNode & | rootNodeIn, |
double & | solutionValue, | ||
std::vector< double > & | solutionPoint, | ||
const double | preprocessTime, | ||
double & | timePassed | ||
) |
Main function to solve the optimization problem.
[in] | rootNodeIn | Root node to start Branch&Bound on. |
[in,out] | solutionValue | Objective value of best feasible point found (empty if no feasible point was found); Also used for communicating objective value of initial feasible point. |
[in,out] | solutionPoint | Solution point, i.e., (one of) the point(s) at which the best objective value was found (empty if no feasible point was found); Also used for communicating initial feasible point. |
[in] | preprocessTime | Is the CPU time spent in pre-processing before invoking this solve routine (needed for correct output of total CPU time during B&B) |
[out] | timePassed | Is the CPU time spent in B&B (especially useful if time is >24h) |
|
private |
this is the lowest lower bound of a node that has been fathomed by value dominance so far (needed to compute the final optimality gap correctly)
|
private |
pointer to brancher object that holds and manages the branch-and-bound tree
|
private |
number of full days
|
private |
first node to find incumbent
|
private |
if a feasible point has been found
|
private |
vector storing solution (p^*)
|
private |
node currently containing the incumbent (may already have been fathomed)
|
private |
vector storing initial point
|
private |
number of iterations
|
private |
number defining the gap between two outputs
|
private |
lowest lower bound
|
private |
total number of LBPs solved
|
private |
counter on iterations where the lowest lbd did not change
|
private |
lowest lower bound before update in _update_lowest_lbd()
|
private |
pointer to lower bounding solver
|
private |
number of lines printed
|
private |
vector storing original lower bounds
|
private |
pointer to object storing settings
|
private |
bool telling whether more scaling has already been activated in the LBS
|
private |
nodes deleted in Iset
|
private |
nodes fathomed in Iset
|
private |
nodes left in Iset
|
private |
maximum number of nodes held in memory so far
|
private |
total nodes created in Iset
|
private |
stores number of optimization parameters
|
private |
stores number of optimization variables without additional auxiliary variables
|
private |
vector holding the optimization variables
|
private |
auxiliary variable to make sure a line is printed whenever a new incumbent, which is better than the old one for more than the tolerances, is found
|
private |
status of the B&B
|
private |
total CPU time in seconds
|
private |
CPU time in seconds used for preprocessing
|
private |
incumbent upper bound
|
private |
total number of UBPs solved
|
private |
pointer to upper bounding solver
|
private |
vector storing upper bounds
|
private |
auxiliary variable to make sure we print to log every writeToLogSec seconds