MAiNGO
maingo::bab::BranchAndBound Class Reference

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 &currentNodeInOut)
 Function processing the current node. More...
 
bool _preprocess_node (babBase::BabNode &currentNodeInOut)
 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 &currentNode)
 Function invoking the LBS to solve the lower bounding problem. More...
 
std::tuple< bool, bool, double > _solve_UBP (const babBase::BabNode &currentNode, std::vector< double > &ubpSolutionPoint, const double currentLBD)
 Function invoking the UBS to solve the upper bounding problem. More...
 
bool _postprocess_node (babBase::BabNode &currentNodeInOut, 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 &currentNode)
 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
 

Detailed Description

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).

Member Enumeration Documentation

◆ _TERMINATION_TYPE

Enum for representing different termination types in B&B.

Enumerator
_TERMINATED 

termination condition has been reached and no worker is processing any nodes

_TERMINATED_WORKERS_ACTIVE 

termination condition has been reached, but there are still nodes being processed by workers

_NOT_TERMINATED 

termination condition has not been reached yet

Constructor & Destructor Documentation

◆ BranchAndBound()

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.

Parameters
[in]variablesis a vector containing the initial optimization variables defined in problem.h
[in]LBSInis a pointer to the LowerBoundingSolver object
[in]UBSInis a pointer to the UpperBoundingSolver object
[in]settingsInis a pointer to an object containing the settings for the Branch-and-Bound solvers
[in]loggerInis a pointer to the MAiNGO logger object
[in]nvarWOauxis the number of optimization variables without the additional auxiliary variables added by the LBP_addAuxiliaryVars option

◆ ~BranchAndBound()

maingo::bab::BranchAndBound::~BranchAndBound ( )
inline

Destructor.

Member Function Documentation

◆ _check_if_more_scaling_needed()

void BranchAndBound::_check_if_more_scaling_needed ( )
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.

◆ _check_termination()

BranchAndBound::_TERMINATION_TYPE BranchAndBound::_check_termination ( )
private

Function for checking if the B&B algorithm terminated.

◆ _display_and_log_progress()

void BranchAndBound::_display_and_log_progress ( const double  currentNodeLBD,
const babBase::BabNode currentNode 
)
private

Function for printing the current progress on the screen and appending it to the internal log to be written to file later.

Parameters
[in]currentNodeLBDis the lower bound for the current node
[in]currentNodeis the current node

◆ _postprocess_node()

bool BranchAndBound::_postprocess_node ( babBase::BabNode currentNodeInOut,
const std::vector< double > &  lbpSolutionPoint,
const lbp::LbpDualInfo dualInfo 
)
private

Function for post-processing the current node. Includes bound DBBT and probing.

Parameters
[in,out]currentNodeInOutThe node to be processed
[in]lbpSolutionPointSolution point of the lower bounding problem
[in]dualInfois a struct containing information from the LP solved during LBP
Returns
Flag indicating whether the node has converged

◆ _preprocess_node()

bool BranchAndBound::_preprocess_node ( babBase::BabNode currentNodeInOut)
private

Function for pre-processing the current node. Includes bound tightening and OBBT.

Parameters
[in,out]currentNodeInOutThe node to be processed
Returns
Flag indicating whether the node was proven to be infeasible

◆ _print_one_node() [1/4]

void BranchAndBound::_print_one_node ( const double  theLBD,
const int  ID,
const std::vector< double >  lowerVarBounds,
const std::vector< double >  upperVarBounds 
)
private

Function printing one node.

Parameters
[in]theLBDis the lower bound of the node
[in]IDis the id of the node
[in]lowerVarBoundsare the variables lower bounds
[in]upperVarBoundsare the variables upper bounds

◆ _print_one_node() [2/4]

void BranchAndBound::_print_one_node ( const double  theLBD,
const int  ID,
const std::vector< double >  lowerVarBounds,
const std::vector< double >  upperVarBounds,
std::ostream &  outstream 
)
private

Function printing one node.

Parameters
[in]theLBDis the lower bound of the node
[in]IDis the id of the node
[in]lowerVarBoundsare the variables lower bounds
[in]upperVarBoundsare the variables upper bounds
[in]outstreamis the stream to be written to, e.g., an error message

◆ _print_one_node() [3/4]

void maingo::bab::BranchAndBound::_print_one_node ( const double  theLBD,
const babBase::BabNode theNode 
)
inlineprivate

Function printing one node.

Parameters
[in]theLBDis the lower bound of the node
[in]theNodeis the node to be printed

◆ _print_one_node() [4/4]

void maingo::bab::BranchAndBound::_print_one_node ( const double  theLBD,
const babBase::BabNode theNode,
std::ostream &  outstream 
)
inlineprivate

Function printing one node.

Parameters
[in]theLBDis the lower bound of the node
[in]theNodeis the node to be printed
[in]outstreamis the stream to be written to, e.g., an error message

◆ _print_termination()

void BranchAndBound::_print_termination ( std::string  message)
private

Function printing a termination message.

Parameters
[in]messageis a string holding the message to print

◆ _process_node()

std::tuple< bool, bool, int, int, double, std::vector< double >, bool, double, std::vector< double > > BranchAndBound::_process_node ( babBase::BabNode currentNodeInOut)
private

Function processing the current node.

Parameters
[in,out]currentNodeInOutThe node to be processed

◆ _solve_LBP()

std::tuple< bool, bool, double, std::vector< double >, lbp::LbpDualInfo > BranchAndBound::_solve_LBP ( const babBase::BabNode currentNode)
private

Function invoking the LBS to solve the lower bounding problem.

Parameters
[in]currentNodeThe node to be processed
Returns
Tuple consisting of flags for whether the node is infeasible and whether it is converged, the lower bound, the lower bounding solution point, and dual information for DBBT

◆ _solve_UBP()

std::tuple< bool, bool, double > BranchAndBound::_solve_UBP ( const babBase::BabNode currentNode,
std::vector< double > &  ubpSolutionPoint,
const double  currentLBD 
)
private

Function invoking the UBS to solve the upper bounding problem.

Parameters
[in]currentNodeThe node to be processed
[in,out]ubpSolutionPointOn input: initial point for local search. On output: solution point.
[in]currentLBDLower bound of current Node. Needed for sanity check.
Returns
Tuple consisting of flags indicating whether a new feasible point has been found and whether the node converged, and the optimal objective value of the new point

◆ _update_incumbent_and_fathom()

void BranchAndBound::_update_incumbent_and_fathom ( const double  solval,
const std::vector< double >  sol,
const unsigned int  currentNodeID 
)
private

Function for updating the incumbent and fathoming accordingly.

Parameters
[in]solvalis the value of the processed solution
[in]solis the solution point
[in]currentNodeIDis the ID of the new node holding the incumbent (it is used instead of directly giving the node to match the parallel implementation)

◆ _update_lowest_lbd()

void BranchAndBound::_update_lowest_lbd ( )
private

Function for updating the global lower bound.

◆ get_final_abs_gap()

double maingo::bab::BranchAndBound::get_final_abs_gap ( )
inline

Function returning the final absolute gap.

◆ get_final_LBD()

double maingo::bab::BranchAndBound::get_final_LBD ( )
inline

Function returning the final LBD.

◆ get_final_rel_gap()

double maingo::bab::BranchAndBound::get_final_rel_gap ( )
inline

Function returning the final relative gap.

◆ get_first_found()

double maingo::bab::BranchAndBound::get_first_found ( )
inline

Function returning the ID of the node where the incumbent was first found.

◆ get_iterations()

double maingo::bab::BranchAndBound::get_iterations ( )
inline

Function returning the number of iterations.

◆ get_LBP_count()

double maingo::bab::BranchAndBound::get_LBP_count ( )
inline

Function returning number of LBD problems solved.

◆ get_max_nodes_in_memory()

double maingo::bab::BranchAndBound::get_max_nodes_in_memory ( )
inline

Function returning the maximum number of nodes in memory.

◆ get_nodes_left()

double maingo::bab::BranchAndBound::get_nodes_left ( )
inline

Function returning the number of nodes left after termination of B&B.

◆ get_UBP_count()

double maingo::bab::BranchAndBound::get_UBP_count ( )
inline

Function returning number of UBD problems solved.

◆ solve()

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.

Parameters
[in]rootNodeInRoot node to start Branch&Bound on.
[in,out]solutionValueObjective 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]solutionPointSolution 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]preprocessTimeIs the CPU time spent in pre-processing before invoking this solve routine (needed for correct output of total CPU time during B&B)
[out]timePassedIs the CPU time spent in B&B (especially useful if time is >24h)
Returns
Return code summarizing the solution status.

Member Data Documentation

◆ _bestLbdFathomed

double maingo::bab::BranchAndBound::_bestLbdFathomed
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)

◆ _brancher

std::unique_ptr<babBase::Brancher> maingo::bab::BranchAndBound::_brancher
private

pointer to brancher object that holds and manages the branch-and-bound tree

◆ _daysPassed

unsigned maingo::bab::BranchAndBound::_daysPassed
private

number of full days

◆ _firstFound

unsigned maingo::bab::BranchAndBound::_firstFound
private

first node to find incumbent

◆ _foundFeas

bool maingo::bab::BranchAndBound::_foundFeas
private

if a feasible point has been found

◆ _incumbent

std::vector<double> maingo::bab::BranchAndBound::_incumbent
private

vector storing solution (p^*)

◆ _incumbentNodeId

unsigned maingo::bab::BranchAndBound::_incumbentNodeId
private

node currently containing the incumbent (may already have been fathomed)

◆ _initialPoint

std::vector<double> maingo::bab::BranchAndBound::_initialPoint
private

vector storing initial point

◆ _iterations

unsigned maingo::bab::BranchAndBound::_iterations
private

number of iterations

◆ _iterationsgap

unsigned maingo::bab::BranchAndBound::_iterationsgap
private

number defining the gap between two outputs

◆ _lbd

double maingo::bab::BranchAndBound::_lbd
private

lowest lower bound

◆ _lbdcnt

unsigned maingo::bab::BranchAndBound::_lbdcnt
private

total number of LBPs solved

◆ _lbdNotChanged

unsigned maingo::bab::BranchAndBound::_lbdNotChanged
private

counter on iterations where the lowest lbd did not change

◆ _lbdOld

double maingo::bab::BranchAndBound::_lbdOld
private

lowest lower bound before update in _update_lowest_lbd()

◆ _LBS

std::shared_ptr<lbp::LowerBoundingSolver> maingo::bab::BranchAndBound::_LBS
private

pointer to lower bounding solver

◆ _linesprinted

unsigned maingo::bab::BranchAndBound::_linesprinted
private

number of lines printed

◆ _logger

Logger* maingo::bab::BranchAndBound::_logger
private

pointer to MAiNGO logger

◆ _lowerVarBoundsOrig

std::vector<double> maingo::bab::BranchAndBound::_lowerVarBoundsOrig
private

vector storing original lower bounds

◆ _maingoSettings

Settings* maingo::bab::BranchAndBound::_maingoSettings
private

pointer to object storing settings

◆ _moreScalingActivated

bool maingo::bab::BranchAndBound::_moreScalingActivated
private

bool telling whether more scaling has already been activated in the LBS

◆ _nNodesDeleted

unsigned maingo::bab::BranchAndBound::_nNodesDeleted
private

nodes deleted in Iset

◆ _nNodesFathomed

unsigned maingo::bab::BranchAndBound::_nNodesFathomed
private

nodes fathomed in Iset

◆ _nNodesLeft

unsigned maingo::bab::BranchAndBound::_nNodesLeft
private

nodes left in Iset

◆ _nNodesMaxInMemory

unsigned maingo::bab::BranchAndBound::_nNodesMaxInMemory
private

maximum number of nodes held in memory so far

◆ _nNodesTotal

unsigned maingo::bab::BranchAndBound::_nNodesTotal
private

total nodes created in Iset

◆ _nvar

const unsigned maingo::bab::BranchAndBound::_nvar
private

stores number of optimization parameters

◆ _nvarWOaux

const unsigned maingo::bab::BranchAndBound::_nvarWOaux
private

stores number of optimization variables without additional auxiliary variables

◆ _originalVariables

std::vector<babBase::OptimizationVariable> maingo::bab::BranchAndBound::_originalVariables
private

vector holding the optimization variables

◆ _printNewIncumbent

bool maingo::bab::BranchAndBound::_printNewIncumbent
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

◆ _status

babBase::enums::BAB_RETCODE maingo::bab::BranchAndBound::_status
private

status of the B&B

◆ _timePassed

double maingo::bab::BranchAndBound::_timePassed
private

total CPU time in seconds

◆ _timePreprocess

double maingo::bab::BranchAndBound::_timePreprocess
private

CPU time in seconds used for preprocessing

◆ _ubd

double maingo::bab::BranchAndBound::_ubd
private

incumbent upper bound

◆ _ubdcnt

unsigned maingo::bab::BranchAndBound::_ubdcnt
private

total number of UBPs solved

◆ _UBS

std::shared_ptr<ubp::UpperBoundingSolver> maingo::bab::BranchAndBound::_UBS
private

pointer to upper bounding solver

◆ _upperVarBoundsOrig

std::vector<double> maingo::bab::BranchAndBound::_upperVarBoundsOrig
private

vector storing upper bounds

◆ _writeToLogEverySec

unsigned maingo::bab::BranchAndBound::_writeToLogEverySec
private

auxiliary variable to make sure we print to log every writeToLogSec seconds


The documentation for this class was generated from the following files: