DeterministicBranchAndBound.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*------------------- File DeterministicBranchAndBound.h -------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_DeterministicBranchAndBound
 #define __PBeFS_DeterministicBranchAndBound
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <algorithm>
 
#include <barrier>
 
#include <exception>
 
#include <mutex>
 
#include <optional>
 
#include <utility>
 
#include <vector>
 
#include "PBeFS/bnb/ParallelBranchAndBound.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*------------------- CLASS DeterministicBranchAndBound --------------------*/
/*--------------------------------------------------------------------------*/

 
template< BranchAndBound P , ADS::WorkerExecutor Executor = ADS::ThreadPool >
class DeterministicBranchAndBound {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
/*------------------------------ PUBLIC TYPES ------------------------------*/
 
 using Node = typename P::node_type;            
 using Value = bb_value_t< P >;                 
 using Options = BasicParallelBBOptions< Value >; 
 using Leaf = BBLeaf< Node , Value >;           
 using SolutionT = BBSolution< Node , Value >;  
 
/*------------------------------ CONSTRUCTOR -------------------------------*/

 
 explicit DeterministicBranchAndBound( const P & problem ,
                                       const Options & options = {} )
  : f_p( problem ) , f_options( options ) {
  f_options.normalize();
  }
 
/*------------------------- OTHER INITIALIZATIONS --------------------------*/
 
 void set_executor( Executor & ex ) noexcept { f_ex = &ex; }
 
/*-------------------------------- SOLVING ---------------------------------*/
 
 [[nodiscard]] SolutionT solve( void ) const {
  return( run( std::nullopt ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] SolutionT solve( std::vector< Leaf > seeds ) const {
  return( run( std::move( seeds ) ) );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:
 
 using Item = typename BBQueue< Node , Value >::Item;
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // a node of a round, and what its evaluation gives
 
 struct Slot {
  Item it;                                      // the node
  std::vector< Item > kids;                     // its children
  std::optional< std::pair< Value , Node > > best;  // its best value
  BBStats st;                                   // its counters
  detail::BBFrontier< Node , Value > fr;        // its leaves
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 SolutionT run( std::optional< std::vector< Leaf > > seeds ) const
 {
  const Value inf = BBValueTraits< Value >::infinity();
  const Options & o = f_options;
  const unsigned p = o.threads;
  const std::size_t round = o.round ? o.round : p;
  Stopwatch clock;
 
  BBQueue< Node , Value > q( o.selection );
  SolutionT sol;
  BBStats & st = sol.stats;
  st.evaluated_by.assign( p , 0 );
  const auto push = [ & ]( Item && it ) {
   const Value key = detail::bb_key( f_p , it.node , it.bound , it.depth ,
                                      o.selection );
   q.push( std::move( it.node ) , it.bound , it.depth , key );
   st.max_open = std::max( st.max_open , q.size() );
   };
  for( auto & l : detail::bb_starts( f_p , std::move( seeds ) ) )
   push( Item{ std::move( l.node ) , l.bound , l.depth } );
 
  BBIncumbent< Node , Value > inc( o.incumbent ?
                                   detail::bb_signed< P >( *o.incumbent ) :
                                   inf );
  detail::BBFrontier< Node , Value > fr( o.keep_frontier );
  std::vector< Slot > slots( round );
  std::size_t nslots = 0;               // the nodes of the round
  Value snapshot = inc.value();         // the incumbent of the round
  bool done = false , limit = false , late = false;
  std::exception_ptr error;
  std::mutex error_m;
 
  // merges the outcomes of the round just ended, in the order of its
  // nodes, and extracts the nodes of the next one; it is run by one worker
  // while the others wait
  const auto next_round = [ & ]( void ) noexcept {
   try {
    for( std::size_t j = 0 ; j < nslots ; ++j ) {
     Slot & s = slots[ j ];
     s.st.incumbents = 0;              // counted here, by the merge
     add_counters( st , s.st );
     st.evaluated_by[ j % p ] += s.st.evaluated;
     if( s.best && inc.template improve< P >( s.best->first ,
                                              s.best->second , o ) )
      ++st.incumbents;
     fr.merge( std::move( s.fr ) );
     for( Item & k : s.kids )
      if( detail::bb_prunable( k.bound , inc.value() , o ) ) {
       ++st.pruned_generated;
       fr.add( std::move( k.node ) , k.bound , k.depth ,
               BBLeafKind::pruned );
       }
      else
       push( std::move( k ) );
     }
    nslots = 0;
 
    if( error ) {
     done = true;
     return;
     }
    if( o.node_limit && ( st.evaluated >= o.node_limit ) ) {
     limit = done = true;
     return;
     }
    if( ( o.time_limit > 0 ) && ( clock.seconds() >= o.time_limit ) ) {
     limit = late = done = true;
     return;
     }
    if( q.empty() ) {
     done = true;
     return;
     }
    if( detail::bb_prunable( q.best_bound() , inc.value() , o ) ) {
     st.pruned_extracted += fr.add( q , BBLeafKind::pruned );
     done = true;                      // nothing can improve
     return;
     }
 
    std::size_t r = round;
    if( o.node_limit )
     r = std::min( r , std::size_t( o.node_limit - st.evaluated ) );
    while( ( nslots < r ) && ! q.empty() ) {
     Slot & s = slots[ nslots++ ];
     s.it = q.pop();
     s.kids.clear();
     s.best.reset();
     s.st = BBStats();
     s.fr = detail::BBFrontier< Node , Value >( o.keep_frontier );
     }
    snapshot = inc.value();
    }
   catch( ... ) {
    std::lock_guard< std::mutex > guard( error_m );
    if( ! error )
     error = std::current_exception();
    done = true;
    }
   };
 
  std::barrier sync( std::ptrdiff_t( p ) , next_round );
  run_workers( f_ex , p , [ & ]( unsigned i ) {
   auto w = detail::bb_worker( f_p , i );
   for( ;; ) {
    sync.arrive_and_wait();
    if( done )
     return;
    for( std::size_t j = i ; j < nslots ; j += p ) {
     Slot & s = slots[ j ];
     try {
      detail::bb_process< P >( s.it.node , s.it.bound , s.it.depth , w ,
                               [ & ] { return( snapshot ); } ,
                               [ & ]( Value v , const Node & n ) {
                                if( ( v >= snapshot ) ||
                                    ( s.best && ( v >= s.best->first ) ) )
                                 return( false );
                                s.best.emplace( v , n );
                                return( true );
                                } ,
                               [ & ]( Node && c , Value b , unsigned d ) {
                                s.kids.push_back( Item{ std::move( c ) , b ,
                                                        d } );
                                } , o , s.st , s.fr );
      }
     catch( ... ) {
      std::lock_guard< std::mutex > guard( error_m );
      if( ! error )
       error = std::current_exception();
      }
     }
    }
   } );
  if( error )
   std::rethrow_exception( error );
 
  fr.add( q , BBLeafKind::open );       // left open by a limit
  detail::bb_finish< P >( sol , inc , fr , limit , late );
  st.seconds = clock.seconds();
  return( sol );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // adds the counters of b to those of a, but for evaluated_by
 
 static void add_counters( BBStats & a , const BBStats & b ) {
  a.evaluated += b.evaluated;
  a.branched += b.branched;
  a.generated += b.generated;
  a.infeasible += b.infeasible;
  a.pruned_generated += b.pruned_generated;
  a.pruned_extracted += b.pruned_extracted;
  a.pruned_evaluated += b.pruned_evaluated;
  a.incumbents += b.incumbents;
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 const P & f_p;                                       
 Options f_options;                           
 Executor * f_ex = nullptr;                   
 
 };  // end( class( DeterministicBranchAndBound ) )
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_DeterministicBranchAndBound */
 
/*--------------------------------------------------------------------------*/
/*----------------- End File DeterministicBranchAndBound.h -----------------*/
/*--------------------------------------------------------------------------*/