MAiNGO
babWALL.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 "logger.h"
20 #include "mpiUtilities.h"
21 #ifdef HAVE_MAiNGO_MPI
22 #include "exceptions.h"
23 #endif
24 
25 #include "babBrancher.h"
26 
27 #include <cmath>
28 #include <map>
29 #include <memory>
30 #include <string>
31 #include <vector>
32 
33 
34 namespace maingo {
35 
36 
37 namespace lbp {
38 class LowerBoundingSolver;
39 struct LbpDualInfo;
40 } // namespace lbp
41 namespace ubp {
42 class UpperBoundingSolver;
43 } // namespace ubp
44 
45 
50 namespace bab {
51 
52 
62 class BranchAndBound {
63 
64  public:
75  BranchAndBound(const std::vector<babBase::OptimizationVariable> &variables, std::shared_ptr<lbp::LowerBoundingSolver> LBSIn, std::shared_ptr<ubp::UpperBoundingSolver> UBSIn,
76  Settings *settingsIn, Logger *loggerIn, const unsigned nvarWOaux);
77 
82 
92  babBase::enums::BAB_RETCODE solve(babBase::BabNode &rootNodeIn, double &solutionValue, std::vector<double> &solutionPoint, const double preprocessTime, double &timePassed);
93 
97  double get_iterations() { return _iterations; }
98 
103 
107  double get_UBP_count() { return _ubdcnt; }
108 
112  double get_LBP_count() { return _lbdcnt; }
113 
117  double get_final_LBD() { return _lbd; }
118 
122  double get_final_abs_gap() { return _ubd - _lbd; }
123 
127  double get_final_rel_gap() { return ((_ubd == 0) ? (get_final_abs_gap()) : ((_ubd - _lbd) / std::fabs(_ubd))); }
128 
132  double get_first_found() { return _firstFound; }
133 
137  double get_nodes_left() { return _nNodesLeft; }
138 
139  private:
145  _TERMINATED = 0,
148  };
149 
155  std::tuple<bool, bool, int, int, double, std::vector<double>, bool, double, std::vector<double>> _process_node(babBase::BabNode &currentNodeInOut);
156 
163  bool _preprocess_node(babBase::BabNode &currentNodeInOut);
164 
171  std::tuple<bool, bool, double, std::vector<double>, lbp::LbpDualInfo> _solve_LBP(const babBase::BabNode &currentNode);
172 
181  std::tuple<bool, bool, double> _solve_UBP(const babBase::BabNode &currentNode, std::vector<double> &ubpSolutionPoint, const double currentLBD);
182 
191  bool _postprocess_node(babBase::BabNode &currentNodeInOut, const std::vector<double> &lbpSolutionPoint, const lbp::LbpDualInfo &dualInfo);
192 
193 
201  void _update_incumbent_and_fathom(const double solval, const std::vector<double> sol, const unsigned int currentNodeID);
202 
206  void _update_lowest_lbd();
207 
212 
217 
224  void _display_and_log_progress(const double currentNodeLBD, const babBase::BabNode &currentNode);
225 
231  void _print_termination(std::string message);
232 
241  void _print_one_node(const double theLBD, const int ID, const std::vector<double> lowerVarBounds, const std::vector<double> upperVarBounds);
242 
252  void _print_one_node(const double theLBD, const int ID, const std::vector<double> lowerVarBounds, const std::vector<double> upperVarBounds, std::ostream &outstream);
253 
260  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()); }
261 
269  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); }
270 
271 #ifdef HAVE_MAiNGO_MPI
272 
281  void _handle_exception(maingo::MAiNGOMpiException &e);
282 
294  void _recv_solved_problem(babBase::BabNode &node, double &lbd, std::vector<double> &lbdSolutionPoint, unsigned &lbdcnt,
295  unsigned &ubdcnt, const COMMUNICATION_TAG status, const int src);
296 
303  void _send_new_problem(const babBase::BabNode &node, const int dest);
304 
311  void _inform_worker_about_event(const BCAST_TAG eventTag, const bool blocking);
323  void _recv_new_problem(babBase::BabNode &node);
324 
332  void _send_incumbent(const double ubd, const std::vector<double> incumbent, const unsigned incumbentID);
333 
344  void _send_solved_problem(const babBase::BabNode node, const double lbd, const std::vector<double> lbdSolutionPoint,
345  const unsigned lbdcnt, const unsigned ubdcnt, const COMMUNICATION_TAG status);
346 
352  void _sync_with_master(MPI_Request &req);
353 
360  void _sync_with_master(MPI_Request &req, bool &terminate);
362 #endif
363 
364  std::unique_ptr<babBase::Brancher> _brancher;
365  std::shared_ptr<ubp::UpperBoundingSolver> _UBS;
366  std::shared_ptr<lbp::LowerBoundingSolver> _LBS;
374  std::vector<babBase::OptimizationVariable> _originalVariables;
375  const unsigned _nvar;
376  const unsigned _nvarWOaux;
377  std::vector<double> _lowerVarBoundsOrig;
378  std::vector<double> _upperVarBoundsOrig;
385  std::vector<double> _incumbent;
386  std::vector<double> _initialPoint;
387  double _ubd;
388  double _lbd;
389  double _bestLbdFathomed;
390  bool _foundFeas;
391  unsigned _firstFound;
392  unsigned _incumbentNodeId;
400  double _lbdOld;
401  unsigned _lbdNotChanged;
402  bool _moreScalingActivated;
409  unsigned _nNodesTotal;
410  unsigned _nNodesLeft;
411  unsigned _nNodesMaxInMemory;
412  unsigned _nNodesDeleted;
413  unsigned _nNodesFathomed;
420  unsigned _lbdcnt;
421  unsigned _ubdcnt;
422  double _timePassed;
423  double _wallPassed;
424  double _timePreprocess;
425  unsigned _daysPassed;
432  unsigned _linesprinted;
433  unsigned _iterations;
434  unsigned _iterationsgap;
435  bool _printNewIncumbent;
436  unsigned _writeToLogEverySec;
437  Logger *_logger;
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
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< babBase::OptimizationVariable > _originalVariables
Definition: bab.h:375
int get_ID() const
Function for querying the node ID.
Definition: babNode.h:100
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
double _wallPassed
Definition: babWALL.h:423
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
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
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
std::shared_ptr< ubp::UpperBoundingSolver > _UBS
Definition: bab.h:366
double get_iterations()
Function returning the number of iterations.
Definition: babWALL.h:97
double get_first_found()
Function returning the ID of the node where the incumbent was first found.
Definition: babWALL.h:132
double get_UBP_count()
Function returning number of UBD problems solved.
Definition: babWALL.h:107
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
Logger * _logger
Definition: bab.h:437
This class contains all logging and output information.
Definition: logger.h:101
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
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: babWALL.h:127
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
double _lbdOld
Definition: bab.h:401
unsigned _nNodesMaxInMemory
Definition: bab.h:412
unsigned _linesprinted
Definition: bab.h:432
unsigned _nNodesFathomed
Definition: bab.h:414
std::vector< double > _lowerVarBoundsOrig
Definition: bab.h:378
std::vector< double > _incumbent
Definition: bab.h:386
void _print_one_node(const double theLBD, const babBase::BabNode &theNode, std::ostream &outstream)
Function printing one node.
Definition: babWALL.h:269
double _ubd
Definition: bab.h:388
std::unique_ptr< babBase::Brancher > _brancher
Definition: bab.h:365
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
std::vector< double > _initialPoint
Definition: bab.h:387
std::vector< double > _upperVarBoundsOrig
Definition: bab.h:379
double get_final_abs_gap()
Function returning the final absolute gap.
Definition: babWALL.h:122
unsigned _iterations
Definition: bab.h:433
unsigned _lbdcnt
Definition: bab.h:421
double get_nodes_left()
Function returning the number of nodes left after termination of B&B.
Definition: babWALL.h:137
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: babWALL.h:260
unsigned _nNodesDeleted
Definition: bab.h:413
double get_final_LBD()
Function returning the final LBD.
Definition: babWALL.h:117
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
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
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
std::shared_ptr< lbp::LowerBoundingSolver > _LBS
Definition: bab.h:367
_TERMINATION_TYPE
Enum for representing different termination types in B&B.
Definition: bab.h:145
Settings * _maingoSettings
Definition: bab.h:369
double get_max_nodes_in_memory()
Function returning the maximum number of nodes in memory.
Definition: babWALL.h:102
unsigned _incumbentNodeId
Definition: bab.h:393
double get_LBP_count()
Function returning number of LBD problems solved.
Definition: babWALL.h:112
~BranchAndBound()
Destructor.
Definition: babWALL.h:81
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