MAiNGO
bab.h
Go to the documentation of this file.
1 /**********************************************************************************
2  * Copyright (c) 2019 Process Systems Engineering (AVT.SVT), RWTH Aachen University
3  *
4  * This program and the accompanying materials are made available under the
5  * terms of the Eclipse Public License 2.0 which is available at
6  * http://www.eclipse.org/legal/epl-2.0.
7  *
8  * SPDX-License-Identifier: EPL-2.0
9  *
10  * @file bab.h
11  *
12  * @brief File declaring the BranchAndBound solver class which manages the tree
13  * and the respective sub-solvers.
14  *
15  **********************************************************************************/
16 
17 #pragma once
18 
19 #include "MAiNGOdebug.h"
20 #include "logger.h"
21 #include "mpiUtilities.h"
22 #ifdef HAVE_MAiNGO_MPI
23 #include "exceptions.h"
24 #endif
25 
26 #include "babBrancher.h"
27 
28 #include <cmath>
29 #include <map>
30 #include <memory>
31 #include <string>
32 #include <vector>
33 
34 
35 namespace maingo {
36 
37 
38 namespace lbp {
40 struct LbpDualInfo;
41 } // namespace lbp
42 namespace ubp {
44 } // namespace ubp
45 
46 
51 namespace bab {
52 
53 
64 
65  public:
76  BranchAndBound(const std::vector<babBase::OptimizationVariable> &variables, std::shared_ptr<lbp::LowerBoundingSolver> LBSIn, std::shared_ptr<ubp::UpperBoundingSolver> UBSIn,
77  Settings *settingsIn, Logger *loggerIn, const unsigned nvarWOaux);
78 
83 
93  babBase::enums::BAB_RETCODE solve(babBase::BabNode &rootNodeIn, double &solutionValue, std::vector<double> &solutionPoint, const double preprocessTime, double &timePassed);
94 
98  double get_iterations() { return _iterations; }
99 
104 
108  double get_UBP_count() { return _ubdcnt; }
109 
113  double get_LBP_count() { return _lbdcnt; }
114 
118  double get_final_LBD() { return _lbd; }
119 
123  double get_final_abs_gap() { return _ubd - _lbd; }
124 
128  double get_final_rel_gap() { return ((_ubd == 0) ? (get_final_abs_gap()) : ((_ubd - _lbd) / std::fabs(_ubd))); }
129 
133  double get_first_found() { return _firstFound; }
134 
138  double get_nodes_left() { return _nNodesLeft; }
139 
140  private:
149  };
150 
156  std::tuple<bool, bool, int, int, double, std::vector<double>, bool, double, std::vector<double>> _process_node(babBase::BabNode &currentNodeInOut);
157 
164  bool _preprocess_node(babBase::BabNode &currentNodeInOut);
165 
172  std::tuple<bool, bool, double, std::vector<double>, lbp::LbpDualInfo> _solve_LBP(const babBase::BabNode &currentNode);
173 
182  std::tuple<bool, bool, double> _solve_UBP(const babBase::BabNode &currentNode, std::vector<double> &ubpSolutionPoint, const double currentLBD);
183 
192  bool _postprocess_node(babBase::BabNode &currentNodeInOut, const std::vector<double> &lbpSolutionPoint, const lbp::LbpDualInfo &dualInfo);
193 
194 
202  void _update_incumbent_and_fathom(const double solval, const std::vector<double> sol, const unsigned int currentNodeID);
203 
207  void _update_lowest_lbd();
208 
213 
218 
225  void _display_and_log_progress(const double currentNodeLBD, const babBase::BabNode &currentNode);
226 
232  void _print_termination(std::string message);
233 
242  void _print_one_node(const double theLBD, const int ID, const std::vector<double> lowerVarBounds, const std::vector<double> upperVarBounds);
243 
253  void _print_one_node(const double theLBD, const int ID, const std::vector<double> lowerVarBounds, const std::vector<double> upperVarBounds, std::ostream &outstream);
254 
261  void _print_one_node(const double theLBD, const babBase::BabNode &theNode) { _print_one_node(theLBD, theNode.get_ID(), theNode.get_lower_bounds(), theNode.get_upper_bounds()); }
262 
270  void _print_one_node(const double theLBD, const babBase::BabNode &theNode, std::ostream &outstream) { _print_one_node(theLBD, theNode.get_ID(), theNode.get_lower_bounds(), theNode.get_upper_bounds(), outstream); }
271 
272 #ifdef HAVE_MAiNGO_MPI
273 
282  void _handle_exception(maingo::MAiNGOMpiException &e);
283 
295  void _recv_solved_problem(babBase::BabNode &node, double &lbd, std::vector<double> &lbdSolutionPoint, unsigned &lbdcnt,
296  unsigned &ubdcnt, const COMMUNICATION_TAG status, const int src);
297 
304  void _send_new_problem(const babBase::BabNode &node, const int dest);
305 
312  void _inform_worker_about_event(const BCAST_TAG eventTag, const bool blocking);
324  void _recv_new_problem(babBase::BabNode &node);
325 
333  void _send_incumbent(const double ubd, const std::vector<double> incumbent, const unsigned incumbentID);
334 
345  void _send_solved_problem(const babBase::BabNode node, const double lbd, const std::vector<double> lbdSolutionPoint,
346  const unsigned lbdcnt, const unsigned ubdcnt, const COMMUNICATION_TAG status);
347 
353  void _sync_with_master(MPI_Request &req);
354 
361  void _sync_with_master(MPI_Request &req, bool &terminate);
363 #endif
364 
365  std::unique_ptr<babBase::Brancher> _brancher;
366  std::shared_ptr<ubp::UpperBoundingSolver> _UBS;
367  std::shared_ptr<lbp::LowerBoundingSolver> _LBS;
375  std::vector<babBase::OptimizationVariable> _originalVariables;
376  const unsigned _nvar;
377  const unsigned _nvarWOaux;
378  std::vector<double> _lowerVarBoundsOrig;
379  std::vector<double> _upperVarBoundsOrig;
386  std::vector<double> _incumbent;
387  std::vector<double> _initialPoint;
388  double _ubd;
389  double _lbd;
391  bool _foundFeas;
392  unsigned _firstFound;
393  unsigned _incumbentNodeId;
401  double _lbdOld;
402  unsigned _lbdNotChanged;
410  unsigned _nNodesTotal;
411  unsigned _nNodesLeft;
413  unsigned _nNodesDeleted;
414  unsigned _nNodesFathomed;
421  unsigned _lbdcnt;
422  unsigned _ubdcnt;
423  double _timePassed;
425  unsigned _daysPassed;
432  unsigned _linesprinted;
433  unsigned _iterations;
434  unsigned _iterationsgap;
440 #ifdef HAVE_MAiNGO_MPI
441 
445  int _rank;
446  int _nProcs;
447  BCAST_TAG _bcastTag;
448  MPI_Request _bcastReq;
455  std::vector<bool> _informedWorkerAboutIncumbent;
456  bool _checkForNodeWithIncumbent;
457  bool _confirmedTermination;
458  unsigned _workCount;
459  std::vector<std::pair<bool, double>> _nodesGivenToWorkers;
466  bool _pendingIncumbentUpdate;
467  MPI_Request _incumbentReq;
470 #endif
471 };
472 
473 
474 } // end namespace bab
475 
476 
477 } // end namespace maingo
Wrapper for handling the lower bounding problems as well as optimization-based bounds tightening (OBB...
Definition: lbp.h:60
void _print_termination(std::string message)
Function printing a termination message.
Definition: bab.cpp:1247
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 w...
Definition: bab.cpp:907
std::vector< double > _lowerVarBoundsOrig
Definition: bab.h:378
Settings * _maingoSettings
Definition: bab.h:369
int get_ID() const
Function for querying the node ID.
Definition: babNode.h:100
This class contains the main algorithm, including handling of pre-processing routines and managing th...
Definition: bab.h:63
BAB_RETCODE
Enum for representing the return codes returned by the B&B solver.
Definition: babUtils.h:126
bool _foundFeas
Definition: bab.h:391
unsigned _lbdNotChanged
Definition: bab.h:402
Class representing a node in the Branch-and-Bound tree.
Definition: babNode.h:35
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.
Definition: bab.cpp:549
std::unique_ptr< babBase::Brancher > _brancher
Definition: bab.h:365
double _timePassed
Definition: bab.h:423
unsigned _ubdcnt
Definition: bab.h:422
File containing definition of the Branch-and-Bound brancher class.
Struct for storing settings for MAiNGO.
Definition: settings.h:143
unsigned _writeToLogEverySec
Definition: bab.h:436
std::vector< babBase::OptimizationVariable > _originalVariables
Definition: bab.h:375
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.
Definition: bab.cpp:803
double get_iterations()
Function returning the number of iterations.
Definition: bab.h:98
double get_first_found()
Function returning the ID of the node where the incumbent was first found.
Definition: bab.h:133
double get_UBP_count()
Function returning number of UBD problems solved.
Definition: bab.h:108
double _bestLbdFathomed
Definition: bab.h:390
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.
Definition: bab.cpp:672
bool _moreScalingActivated
Definition: bab.h:403
This class contains all logging and output information.
Definition: logger.h:100
bool _preprocess_node(babBase::BabNode &currentNodeInOut)
Function for pre-processing the current node. Includes bound tightening and OBBT.
Definition: bab.cpp:616
babBase::enums::BAB_RETCODE _status
Definition: bab.h:394
_TERMINATION_TYPE _check_termination()
Function for checking if the B&B algorithm terminated.
Definition: bab.cpp:1059
std::vector< double > get_lower_bounds() const
Function for querying the lower bounds on the optimization variables within this node.
Definition: babNode.h:90
std::vector< double > _upperVarBoundsOrig
Definition: bab.h:379
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.
Definition: bab.cpp:34
const unsigned _nvarWOaux
Definition: bab.h:377
double get_final_rel_gap()
Function returning the final relative gap.
Definition: bab.h:128
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.
Definition: bab.cpp:777
unsigned _iterationsgap
Definition: bab.h:434
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.
Definition: bab.cpp:115
Logger * _logger
Definition: bab.h:437
double _lbdOld
Definition: bab.h:401
unsigned _nNodesMaxInMemory
Definition: bab.h:412
Base class for wrappers for handling the upper bounding problems.
Definition: ubp.h:49
unsigned _linesprinted
Definition: bab.h:432
unsigned _nNodesFathomed
Definition: bab.h:414
void _print_one_node(const double theLBD, const babBase::BabNode &theNode, std::ostream &outstream)
Function printing one node.
Definition: bab.h:270
double _ubd
Definition: bab.h:388
namespace holding all essentials of MAiNGO
Definition: aleModel.h:31
unsigned _nNodesTotal
Definition: bab.h:410
void _update_lowest_lbd()
Function for updating the global lower bound.
Definition: bab.cpp:845
double get_final_abs_gap()
Function returning the final absolute gap.
Definition: bab.h:123
unsigned _iterations
Definition: bab.h:433
std::vector< double > _incumbent
Definition: bab.h:386
std::shared_ptr< lbp::LowerBoundingSolver > _LBS
Definition: bab.h:367
unsigned _lbdcnt
Definition: bab.h:421
double get_nodes_left()
Function returning the number of nodes left after termination of B&B.
Definition: bab.h:138
bool _printNewIncumbent
Definition: bab.h:435
double _lbd
Definition: bab.h:389
unsigned _firstFound
Definition: bab.h:392
void _print_one_node(const double theLBD, const babBase::BabNode &theNode)
Function printing one node.
Definition: bab.h:261
unsigned _nNodesDeleted
Definition: bab.h:413
double get_final_LBD()
Function returning the final LBD.
Definition: bab.h:118
void _print_one_node(const double theLBD, const int ID, const std::vector< double > lowerVarBounds, const std::vector< double > upperVarBounds)
Function printing one node.
Definition: bab.cpp:1031
double _timePreprocess
Definition: bab.h:424
std::shared_ptr< ubp::UpperBoundingSolver > _UBS
Definition: bab.h:366
unsigned _daysPassed
Definition: bab.h:425
std::vector< double > get_upper_bounds() const
Function for querying the upper bounds on the optimization variables within this node.
Definition: babNode.h:95
void _check_if_more_scaling_needed()
Function which checks whether it is necessary to activate scaling within the LBD solver....
Definition: bab.cpp:877
std::vector< double > _initialPoint
Definition: bab.h:387
Container for information from the LBP that is needed in DBBT and probing, used for communicating the...
Definition: lbp.h:47
const unsigned _nvar
Definition: bab.h:376
unsigned _nNodesLeft
Definition: bab.h:411
_TERMINATION_TYPE
Enum for representing different termination types in B&B.
Definition: bab.h:145
double get_max_nodes_in_memory()
Function returning the maximum number of nodes in memory.
Definition: bab.h:103
unsigned _incumbentNodeId
Definition: bab.h:393
double get_LBP_count()
Function returning number of LBD problems solved.
Definition: bab.h:113
~BranchAndBound()
Destructor.
Definition: bab.h:82
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.
Definition: bab.cpp:717