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  **********************************************************************************/
11 
12 #pragma once
13 
14 #include "MAiNGOdebug.h"
15 #include "logger.h"
16 #include "mpiUtilities.h"
17 #ifdef HAVE_MAiNGO_MPI
18 #include "MAiNGOMpiException.h"
19 #endif
20 
21 #include "babBrancher.h"
22 
23 #include <cmath>
24 #include <map>
25 #include <memory>
26 #include <string>
27 #include <vector>
28 
29 
30 namespace maingo {
31 
32 
33 namespace lbp {
35 struct LbpDualInfo;
36 } // namespace lbp
37 namespace ubp {
39 } // namespace ubp
40 
41 
46 namespace bab {
47 
48 
59 
60  public:
71  BranchAndBound(const std::vector<babBase::OptimizationVariable> &variables, std::shared_ptr<lbp::LowerBoundingSolver> LBSIn, std::shared_ptr<ubp::UpperBoundingSolver> UBSIn,
72  std::shared_ptr<Settings> settingsIn, std::shared_ptr<Logger> loggerIn, const unsigned nvarWOaux);
73 
78 
88  babBase::enums::BAB_RETCODE solve(babBase::BabNode &rootNodeIn, double &solutionValue, std::vector<double> &solutionPoint, const double preprocessTime, double &timePassed);
89 
93  double get_iterations() { return _iterations; }
94 
99 
103  double get_UBP_count() { return _ubdcnt; }
104 
108  double get_LBP_count() { return _lbdcnt; }
109 
113  double get_final_LBD() { return _lbd; }
114 
118  double get_final_abs_gap() { return _ubd - _lbd; }
119 
123  double get_final_rel_gap() { return ((_ubd == 0) ? (get_final_abs_gap()) : ((_ubd - _lbd) / std::fabs(_ubd))); }
124 
128  double get_first_found() { return _firstFound; }
129 
133  double get_nodes_left() { return _nNodesLeft; }
134 
135  private:
144  };
145 
151  std::tuple<bool, bool, int, int, double, std::vector<double>, bool, double, std::vector<double>> _process_node(babBase::BabNode &currentNodeInOut);
152 
159  bool _preprocess_node(babBase::BabNode &currentNodeInOut);
160 
167  std::tuple<bool, bool, double, std::vector<double>, lbp::LbpDualInfo> _solve_LBP(const babBase::BabNode &currentNode);
168 
177  std::tuple<bool, bool, double> _solve_UBP(const babBase::BabNode &currentNode, std::vector<double> &ubpSolutionPoint, const double currentLBD);
178 
187  bool _postprocess_node(babBase::BabNode &currentNodeInOut, const std::vector<double> &lbpSolutionPoint, const lbp::LbpDualInfo &dualInfo);
188 
189 
197  void _update_incumbent_and_fathom(const double solval, const std::vector<double> sol, const unsigned int currentNodeID);
198 
202  void _update_lowest_lbd();
203 
208 
213 
220  void _display_and_log_progress(const double currentNodeLBD, const babBase::BabNode &currentNode);
221 
227  void _print_termination(std::string message);
228 
237  void _print_one_node(const double theLBD, const int ID, const std::vector<double> lowerVarBounds, const std::vector<double> upperVarBounds);
238 
248  void _print_one_node(const double theLBD, const int ID, const std::vector<double> lowerVarBounds, const std::vector<double> upperVarBounds, std::ostream &outstream);
249 
256  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()); }
257 
265  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); }
266 
267 #ifdef HAVE_MAiNGO_MPI
268 
277  void _communicate_exception_and_throw(const maingo::MAiNGOMpiException &e);
278 
290  void _recv_solved_problem(babBase::BabNode &node, double &lbd, std::vector<double> &lbdSolutionPoint, unsigned &lbdcnt,
291  unsigned &ubdcnt, const COMMUNICATION_TAG status, const int src);
292 
299  void _send_new_problem(const babBase::BabNode &node, const int dest);
300 
307  void _inform_worker_about_event(const BCAST_TAG eventTag, const bool blocking);
319  void _recv_new_problem(babBase::BabNode &node);
320 
328  void _send_incumbent(const double ubd, const std::vector<double> incumbent, const unsigned incumbentID);
329 
340  void _send_solved_problem(const babBase::BabNode node, const double lbd, const std::vector<double> lbdSolutionPoint,
341  const unsigned lbdcnt, const unsigned ubdcnt, const COMMUNICATION_TAG status);
342 
348  void _sync_with_master(MPI_Request &req);
349 
356  void _sync_with_master(MPI_Request &req, bool &terminate);
358 #endif
359 
360  std::unique_ptr<babBase::Brancher> _brancher;
361  std::shared_ptr<ubp::UpperBoundingSolver> _UBS;
362  std::shared_ptr<lbp::LowerBoundingSolver> _LBS;
364  std::shared_ptr<Settings> _maingoSettings;
370  std::vector<babBase::OptimizationVariable> _originalVariables;
371  const unsigned _nvar;
372  const unsigned _nvarWOaux;
373  std::vector<double> _lowerVarBoundsOrig;
374  std::vector<double> _upperVarBoundsOrig;
381  std::vector<double> _incumbent;
382  std::vector<double> _initialPoint;
383  double _ubd;
384  double _lbd;
386  bool _foundFeas;
387  unsigned _firstFound;
388  unsigned _incumbentNodeId;
396  double _lbdOld;
397  unsigned _lbdNotChanged;
405  unsigned _nNodesTotal;
406  unsigned _nNodesLeft;
408  unsigned _nNodesDeleted;
409  unsigned _nNodesFathomed;
416  unsigned _lbdcnt;
417  unsigned _ubdcnt;
418  double _timePassed;
420  unsigned _daysPassed;
427  unsigned _linesprinted;
428  unsigned _iterations;
429  unsigned _iterationsgap;
432  std::shared_ptr<Logger> _logger;
435 #ifdef HAVE_MAiNGO_MPI
436 
440  int _rank;
441  int _nProcs;
442  BCAST_TAG _bcastTag;
443  MPI_Request _bcastReq;
450  std::vector<bool> _informedWorkerAboutIncumbent;
451  bool _checkForNodeWithIncumbent;
452  bool _confirmedTermination;
453  unsigned _workCount;
454  std::vector<std::pair<bool, double>> _nodesGivenToWorkers;
461  bool _pendingIncumbentUpdate;
462  MPI_Request _incumbentReq;
465 #endif
466 };
467 
468 
469 } // end namespace bab
470 
471 
472 } // end namespace maingo
Wrapper for handling the lower bounding problems as well as optimization-based bounds tightening (OBB...
Definition: lbp.h:65
void _print_termination(std::string message)
Function printing a termination message.
Definition: bab.cpp:1232
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:897
std::vector< double > _lowerVarBoundsOrig
Definition: bab.h:373
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:58
BAB_RETCODE
Enum for representing the return codes returned by the B&B solver.
Definition: babUtils.h:126
bool _foundFeas
Definition: bab.h:386
unsigned _lbdNotChanged
Definition: bab.h:397
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:535
std::unique_ptr< babBase::Brancher > _brancher
Definition: bab.h:360
BranchAndBound(const std::vector< babBase::OptimizationVariable > &variables, std::shared_ptr< lbp::LowerBoundingSolver > LBSIn, std::shared_ptr< ubp::UpperBoundingSolver > UBSIn, std::shared_ptr< Settings > settingsIn, std::shared_ptr< Logger > loggerIn, const unsigned nvarWOaux)
Constructor, stores information on problem and settings.
Definition: bab.cpp:28
double _timePassed
Definition: bab.h:418
unsigned _ubdcnt
Definition: bab.h:417
File containing definition of the Branch-and-Bound brancher class.
unsigned _writeToLogEverySec
Definition: bab.h:431
std::vector< babBase::OptimizationVariable > _originalVariables
Definition: bab.h:370
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:792
double get_iterations()
Function returning the number of iterations.
Definition: bab.h:93
double get_first_found()
Function returning the ID of the node where the incumbent was first found.
Definition: bab.h:128
double get_UBP_count()
Function returning number of UBD problems solved.
Definition: bab.h:103
double _bestLbdFathomed
Definition: bab.h:385
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:658
bool _moreScalingActivated
Definition: bab.h:398
bool _preprocess_node(babBase::BabNode &currentNodeInOut)
Function for pre-processing the current node. Includes bound tightening and OBBT. ...
Definition: bab.cpp:602
babBase::enums::BAB_RETCODE _status
Definition: bab.h:389
_TERMINATION_TYPE _check_termination()
Function for checking if the B&B algorithm terminated.
Definition: bab.cpp:1047
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:374
const unsigned _nvarWOaux
Definition: bab.h:372
double get_final_rel_gap()
Function returning the final relative gap.
Definition: bab.h:123
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:763
unsigned _iterationsgap
Definition: bab.h:429
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:109
double _lbdOld
Definition: bab.h:396
unsigned _nNodesMaxInMemory
Definition: bab.h:407
Base class for wrappers for handling the upper bounding problems.
Definition: ubp.h:44
unsigned _linesprinted
Definition: bab.h:427
unsigned _nNodesFathomed
Definition: bab.h:409
void _print_one_node(const double theLBD, const babBase::BabNode &theNode, std::ostream &outstream)
Function printing one node.
Definition: bab.h:265
double _ubd
Definition: bab.h:383
namespace holding all essentials of MAiNGO
Definition: aleModel.h:25
unsigned _nNodesTotal
Definition: bab.h:405
void _update_lowest_lbd()
Function for updating the global lower bound.
Definition: bab.cpp:835
double get_final_abs_gap()
Function returning the final absolute gap.
Definition: bab.h:118
unsigned _iterations
Definition: bab.h:428
std::vector< double > _incumbent
Definition: bab.h:381
std::shared_ptr< lbp::LowerBoundingSolver > _LBS
Definition: bab.h:362
std::shared_ptr< Logger > _logger
Definition: bab.h:432
unsigned _lbdcnt
Definition: bab.h:416
double get_nodes_left()
Function returning the number of nodes left after termination of B&B.
Definition: bab.h:133
bool _printNewIncumbent
Definition: bab.h:430
double _lbd
Definition: bab.h:384
unsigned _firstFound
Definition: bab.h:387
void _print_one_node(const double theLBD, const babBase::BabNode &theNode)
Function printing one node.
Definition: bab.h:256
unsigned _nNodesDeleted
Definition: bab.h:408
double get_final_LBD()
Function returning the final LBD.
Definition: bab.h:113
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:1019
double _timePreprocess
Definition: bab.h:419
std::shared_ptr< ubp::UpperBoundingSolver > _UBS
Definition: bab.h:361
unsigned _daysPassed
Definition: bab.h:420
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. This is a heuristic approach, which does not affect any deterministic optimization assumptions.
Definition: bab.cpp:867
std::vector< double > _initialPoint
Definition: bab.h:382
Container for information from the LBP that is needed in DBBT and probing, used for communicating the...
Definition: lbp.h:52
const unsigned _nvar
Definition: bab.h:371
unsigned _nNodesLeft
Definition: bab.h:406
_TERMINATION_TYPE
Enum for representing different termination types in B&B.
Definition: bab.h:140
std::shared_ptr< Settings > _maingoSettings
Definition: bab.h:364
double get_max_nodes_in_memory()
Function returning the maximum number of nodes in memory.
Definition: bab.h:98
unsigned _incumbentNodeId
Definition: bab.h:388
double get_LBP_count()
Function returning number of LBD problems solved.
Definition: bab.h:108
~BranchAndBound()
Destructor.
Definition: bab.h:77
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:703