ParallelBranchAndBound.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*--------------------- File ParallelBranchAndBound.h ----------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_ParallelBranchAndBound
 #define __PBeFS_ParallelBranchAndBound
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <atomic>
 
#include <memory>
 
#include <mutex>
 
#include <random>
 
#include <type_traits>
 
#include "PBeFS/bnb/BranchAndBound.h"
 
#include "ADS/parallel/Channels.h"
 
#include "ADS/parallel/Mailbox.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*------------------------ CLASS ParallelBBOptions -------------------------*/
/*--------------------------------------------------------------------------*/

 
template< class V = double >
struct BasicParallelBBOptions : public BasicBBOptions< V > ,
                                public ParallelParams {
 
 BasicParallelBBOptions( void ) {
  batch = 16;
  flush_period = 1;
  }

 std::size_t round = 0;

 std::size_t split = 0;

 bool split_dive = true;

 bool split_shared = false;
 
 };  // end( struct( BasicParallelBBOptions ) )

using ParallelBBOptions = BasicParallelBBOptions<>;
 
namespace detail {

template< class V , bool = std::is_trivially_copyable_v< V > >
struct bb_lock_free : std::false_type {};
 
template< class V >
struct bb_lock_free< V , true >
 : std::bool_constant< std::atomic< V >::is_always_lock_free > {};
 
}  // end( namespace detail )
 
/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS BBIncumbent ----------------------------*/
/*--------------------------------------------------------------------------*/

 
template< class Node , class V = double >
class BBIncumbent {
 
 public:

 
 explicit BBIncumbent( V v ) : f_value( v ) {}
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] V value( void ) const {
  if constexpr( c_atomic )
   return( f_value.load( std::memory_order_relaxed ) );
  else {
   std::lock_guard< std::mutex > guard( f_m );
   return( f_value );
   }
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 template< class P >
 bool improve( V v , const Node & n , const BasicBBOptions< V > & o ) {
  if( c_atomic && ( v >= value() ) )
   return( false );
  std::lock_guard< std::mutex > guard( f_m );
  if( v >= stored() )
   return( false );
  if constexpr( c_atomic )
   f_value.store( v , std::memory_order_relaxed );
  else
   f_value = v;
  f_node = n;
  if( o.on_incumbent )
   o.on_incumbent( detail::bb_signed< P >( v ) );
  return( true );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 std::optional< Node > take_node( void ) { return( std::move( f_node ) ); }
 
 private:

 static constexpr bool c_atomic = detail::bb_lock_free< V >::value;
 
 // the value, read under the lock
 [[nodiscard]] V stored( void ) const {
  if constexpr( c_atomic )
   return( f_value.load( std::memory_order_relaxed ) );
  else
   return( f_value );
  }
 
 alignas( cache_line ) std::conditional_t< c_atomic , std::atomic< V > , V >
  f_value;                                      
 mutable std::mutex f_m;                        
 std::optional< Node > f_node;                  
 
 };  // end( class( BBIncumbent ) )
 
/*--------------------------------------------------------------------------*/
/*------------------------------- FUNCTIONS --------------------------------*/
/*--------------------------------------------------------------------------*/
 
namespace detail {

 
template< BranchAndBound P >
void bb_finish( BBSolution< typename P::node_type , bb_value_t< P > > & sol ,
                BBIncumbent< typename P::node_type , bb_value_t< P > > & inc ,
                BBFrontier< typename P::node_type , bb_value_t< P > > & fr ,
                bool limit , bool time )
{
 using V = bb_value_t< P >;
 using Tr = BBValueTraits< V >;
 const V z = inc.value();
 if( limit )
  sol.status = time ? BBStatus::time_limit : BBStatus::node_limit;
 else
  sol.status = Tr::finite( z ) ? BBStatus::optimal : BBStatus::infeasible;
 sol.node = inc.take_node();
 if( Tr::finite( z ) )
  sol.value = bb_signed< P >( z );
 const V lb = std::min( z , fr.low );
 sol.bound = bb_signed< P >( lb );
 sol.gap = Tr::finite( z ) && Tr::finite( lb ) ? V( z - lb )
                                               : Tr::infinity();
 fr.template take< P >( sol.frontier );
 }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
template< class Item , class V >
std::size_t bb_dive( const std::vector< Item > & kids , V best , V inc ,
                     const BasicBBOptions< V > & o )
{
 if( ( o.selection == Selection::depth_first ) && ! kids.empty() )
  return( kids.size() - 1 );
 if( ( o.selection != Selection::plunging ) || kids.empty() )
  return( kids.size() );
 std::size_t c = 0;
 for( std::size_t j = 1 ; j < kids.size() ; ++j )
  if( kids[ j ].bound <= kids[ c ].bound )
   c = j;
 using Tr = BBValueTraits< V >;
 const V b0 = std::min( best , kids[ c ].bound );
 if( ! Tr::finite( inc ) ||
     Tr::within( kids[ c ].bound , b0 , inc , o.plunge_gap ) )
  return( c );
 return( kids.size() );
 }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
template< class V >
bool bb_limit( const BasicBBOptions< V > & o , std::uint64_t evaluated ,
               const Stopwatch & clock , std::atomic< bool > & limit ,
               std::atomic< bool > & time )
{
 const bool nodes = o.node_limit && ( evaluated >= o.node_limit );
 const bool late = ( o.time_limit > 0 ) && ( clock.seconds() >= o.time_limit );
 if( ! ( nodes || late ) )
  return( false );
 if( late )
  time.store( true );
 limit.store( true );
 return( true );
 }
 
}  // end( namespace detail )
 
/*--------------------------------------------------------------------------*/
/*----------------------- CLASS SharedBranchAndBound -----------------------*/
/*--------------------------------------------------------------------------*/

 
template< BranchAndBound P , ADS::WorkerExecutor Executor = ADS::ThreadPool >
class SharedBranchAndBound {
 
/*------------------------ 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 SharedBranchAndBound( 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:
 
 SolutionT run( std::optional< std::vector< Leaf > > seeds ) const
 {
  const Value inf = BBValueTraits< Value >::infinity();
  const unsigned p = f_options.threads;
  const Selection sel = f_options.selection;
  Stopwatch clock;
  const Value start = f_options.incumbent ?
                      detail::bb_signed< P >( *f_options.incumbent ) : inf;
  Shared sh( start , sel );
  for( auto & l : detail::bb_starts( f_p , std::move( seeds ) ) ) {
   const Value key = detail::bb_key( f_p , l.node , l.bound , l.depth ,
                                      sel );
   sh.q.push( std::move( l.node ) , l.bound , l.depth , key );
   }
  sh.open.store( sh.q.size() );
  sh.max_open = sh.q.size();
 
  std::vector< std::unique_ptr< Worker > > w( p );
  for( unsigned i = 0 ; i < p ; ++i )
   w[ i ] = std::make_unique< Worker >( *this , sh , clock );
  run_workers( f_ex , p , [ & ]( unsigned i ) { w[ i ]->run( i ); } );
 
  SolutionT sol;
  detail::BBFrontier< Node , Value > fr( f_options.keep_frontier );
  fr.add( sh.q , BBLeafKind::open );          // left open by a limit
  for( auto & x : w ) {
   sol.stats.add( x->f_st );
   fr.merge( std::move( x->f_fr ) );
   }
  sol.stats.max_open = sh.max_open;
  detail::bb_finish< P >( sol , sh.inc , fr , sh.limit.load() ,
                          sh.time.load() );
  sol.stats.seconds = clock.seconds();
  return( sol );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 using Lock = typename Executor::lock_type;
 using Item = typename BBQueue< Node , Value >::Item;
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the data shared by the workers
 
 struct Shared {
 
  Shared( Value z , Selection s ) : inc( z ) , q( s ) {}
 
  BBIncumbent< Node , Value > inc;             // the incumbent
  alignas( cache_line ) Lock lock;              // protects q and max_open
  BBQueue< Node , Value > q;                   // the open nodes
  std::size_t max_open = 0;                    // the most open nodes
  alignas( cache_line ) std::atomic< std::size_t > open{ 0 };  // q.size()
  alignas( cache_line ) std::atomic< unsigned > busy{ 0 };  // holding a node
  alignas( cache_line ) std::atomic< std::uint64_t > evaluated{ 0 };
  alignas( cache_line ) std::atomic< bool > done{ false };
  std::atomic< bool > limit{ false };          // stopped by a limit
  std::atomic< bool > time{ false };           // ... the time limit
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // a worker
 
 struct alignas( cache_line ) Worker {
 
  Worker( const SharedBranchAndBound & a , Shared & s , const Stopwatch & c )
   : f_a( a ) , f_sh( s ) , f_clock( c ) ,
     f_fr( a.f_options.keep_frontier ) {}
 
  // the main loop
  void run( unsigned i ) {
   auto w = detail::bb_worker( f_a.f_p , i );
   const auto & o = f_a.f_options;
   const Selection sel = o.selection;
   std::optional< Item > dive;               // the node of the dive
   std::vector< Item > kids;                 // the children of a node
   const auto inc = [ & ] { return( f_sh.inc.value() ); };
   const auto improve = [ & ]( Value v , const Node & n ) {
    return( f_sh.inc.template improve< P >( v , n , o ) );
    };
 
   for( ;; ) {
    std::optional< Item > it;
    if( dive ) {
     it.emplace( std::move( *dive ) );
     dive.reset();
     }
    else
     if( ! ( it = next() ) )
      return;
 
    if( stop() ) {                     // the node stays open
     f_fr.add( std::move( it->node ) , it->bound , it->depth ,
               BBLeafKind::open );
     f_sh.busy.fetch_sub( 1 );
     return;
     }
 
    kids.clear();
    detail::bb_process< P >( it->node , it->bound , it->depth , w , inc ,
                             improve , [ & ]( Node && c , Value b ,
                                              unsigned d ) {
                              kids.push_back( Item{ std::move( c ) , b , d } );
                              } , o , f_st , f_fr );
    f_sh.evaluated.fetch_add( 1 );
 
    std::lock_guard< Lock > guard( f_sh.lock );
    const std::size_t k = detail::bb_dive( kids , f_sh.q.best_bound() ,
                                           inc() , o );
    for( std::size_t j = 0 ; j < kids.size() ; ++j )
     if( j == k )
      dive.emplace( std::move( kids[ j ] ) );
     else {
      const Value key = detail::bb_key( f_a.f_p , kids[ j ].node ,
                                         kids[ j ].bound , kids[ j ].depth ,
                                         sel );
      f_sh.q.push( std::move( kids[ j ].node ) , kids[ j ].bound ,
                   kids[ j ].depth , key );
      }
    f_sh.open.store( f_sh.q.size() );
    f_sh.max_open = std::max( f_sh.max_open , f_sh.q.size() );
    if( ! dive )
     f_sh.busy.fetch_sub( 1 );
    }
   }
 
  // the next node of the queue, counting the worker as busy; none when the
  // search is over
  std::optional< Item > next( void ) {
   ADS::Backoff backoff;
   for( ;; ) {
    if( f_sh.done.load( std::memory_order_acquire ) )
     return( std::nullopt );
    if( f_sh.open.load() == 0 ) {      // wait without the lock
     if( f_sh.busy.load() == 0 ) {
      std::lock_guard< Lock > guard( f_sh.lock );
      if( f_sh.q.empty() && ( f_sh.busy.load() == 0 ) )
       f_sh.done.store( true , std::memory_order_release );
      continue;
      }
     backoff.pause();
     continue;
     }
    std::lock_guard< Lock > guard( f_sh.lock );
    if( f_sh.q.empty() )
     continue;
    const Value best = f_sh.q.best_bound();
    if( detail::bb_prunable( best , f_sh.inc.value() , f_a.f_options ) ) {
     f_st.pruned_extracted += f_fr.add( f_sh.q , BBLeafKind::pruned );
     f_sh.open.store( 0 );                       // nothing can improve
     continue;
     }
    f_sh.busy.fetch_add( 1 );
    Item it = f_sh.q.pop();
    f_sh.open.store( f_sh.q.size() );
    return( it );
    }
   }
 
  // true if a limit is reached, which ends the search
  bool stop( void ) {
   if( ! detail::bb_limit( f_a.f_options , f_sh.evaluated.load() , f_clock ,
                           f_sh.limit , f_sh.time ) )
    return( false );
   f_sh.done.store( true , std::memory_order_release );
   return( true );
   }
 
  const SharedBranchAndBound & f_a;             // the search
  Shared & f_sh;                                // the shared data
  const Stopwatch & f_clock;                    // the clock of the search
  BBStats f_st;                                 // its counters
  detail::BBFrontier< Node , Value > f_fr;      // its leaves
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 const P & f_p;                                       
 Options f_options;                           
 Executor * f_ex = nullptr;                   
 
 };  // end( class( SharedBranchAndBound ) )
 
/*--------------------------------------------------------------------------*/
/*-------------------- CLASS DistributedBranchAndBound ---------------------*/
/*--------------------------------------------------------------------------*/

 
template< BranchAndBound P , ADS::WorkerExecutor Executor = ADS::ThreadPool >
class DistributedBranchAndBound {
 
/*------------------------ 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 >;  

 struct Msg {
  Node node;
  Value bound;
  unsigned depth;
  };
 
/*------------------------------ CONSTRUCTOR -------------------------------*/

 
 explicit DistributedBranchAndBound( 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:
 
 SolutionT run( std::optional< std::vector< Leaf > > seeds ) const
 {
  const Value inf = BBValueTraits< Value >::infinity();
  const unsigned p = f_options.threads;
  Stopwatch clock;
  const Value start = f_options.incumbent ?
                      detail::bb_signed< P >( *f_options.incumbent ) : inf;
  Shared sh( p , start , f_options.batch );
  {
   auto & b = sh.seeds;
   std::size_t i = 0;
   for( auto & l : detail::bb_starts( f_p , std::move( seeds ) ) ) {
    unsigned dst;
    if constexpr( HashedBranchAndBound< P > )
     dst = unsigned( std::uint64_t( f_p.hash( l.node ) ) % p );
    else
     dst = unsigned( i % p );
    ++i;
    b[ dst ].push_back( Msg{ std::move( l.node ) , l.bound , l.depth } );
    }
   }
 
  std::vector< std::unique_ptr< Worker > > w( p );
  for( unsigned i = 0 ; i < p ; ++i )
   w[ i ] = std::make_unique< Worker >( *this , sh , i , clock );
  run_workers( f_ex , p , [ & ]( unsigned i ) { w[ i ]->run(); } );
 
  // the nodes left open by a limit bound the optimum too
  SolutionT sol;
  detail::BBFrontier< Node , Value > fr( f_options.keep_frontier );
  const auto open = [ & ]( Msg && m ) {
   fr.add( std::move( m.node ) , m.bound , m.depth , BBLeafKind::open );
   };
  for( unsigned i = 0 ; i < p ; ++i ) {
   Worker & x = *w[ i ];
   x.f_st.messages = sh.mail.batches( i );
   sol.stats.add( x.f_st );
   fr.merge( std::move( x.f_fr ) );
   fr.add( x.f_q , BBLeafKind::open );
   if( x.f_dive )
    fr.add( std::move( x.f_dive->node ) , x.f_dive->bound ,
            x.f_dive->depth , BBLeafKind::open );
   }
  sh.mail.leftovers( open );
  detail::bb_finish< P >( sol , sh.inc , fr , sh.limit.load() ,
                          sh.time.load() );
  sol.stats.seconds = clock.seconds();
  return( sol );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 using Mailbox = ADS::Mailbox< Msg , ADS::DefaultChannels< Msg , Executor > >;
 using Item = typename BBQueue< Node , Value >::Item;
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the data shared by the workers
 
 struct Shared {
 
  Shared( unsigned np , Value z , std::size_t batch )
   : p( np ) , mail( np , batch ) , seeds( np ) , inc( z ) {}
 
  unsigned p;                                   // the number of workers
  Mailbox mail;                                 // the messages
  std::vector< std::vector< Msg > > seeds;      // the first nodes, by owner
  BBIncumbent< Node , Value > inc;              // the incumbent
  alignas( cache_line ) std::atomic< std::uint64_t > evaluated{ 0 };
  std::atomic< bool > limit{ false };           // stopped by a limit
  std::atomic< bool > time{ false };            // ... the time limit
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // a worker: its queue, its outboxes and its counters
 
 struct alignas( cache_line ) Worker {
 
  Worker( const DistributedBranchAndBound & a , Shared & s , unsigned i ,
          const Stopwatch & c )
   : f_a( a ) , f_sh( s ) , f_id( i ) , f_clock( c ) ,
     f_q( a.f_options.selection ) ,
     f_gen( a.f_options.seed + i ) ,
     f_fr( a.f_options.keep_frontier ) {}
 
  // the main loop
  void run( void ) {
   auto w = detail::bb_worker( f_a.f_p , f_id );
   const auto & o = f_a.f_options;
   const auto inc = [ & ] { return( f_sh.inc.value() ); };
   const auto improve = [ & ]( Value v , const Node & n ) {
    return( f_sh.inc.template improve< P >( v , n , o ) );
    };
   for( Msg & m : f_sh.seeds[ f_id ] )
    push( Item{ std::move( m.node ) , m.bound , m.depth } );
   unsigned since_flush = 0;
   ADS::Backoff backoff;
 
   while( ! f_sh.mail.stopped() ) {
    f_sh.mail.poll( f_id , [ & ]( Msg && m ) {
     push( Item{ std::move( m.node ) , m.bound , m.depth } );
     } );
 
    if( std::optional< Item > it = next() ) {
     backoff.reset();
     if( stop() ) {                   // the node stays open
      f_fr.add( std::move( it->node ) , it->bound , it->depth ,
                BBLeafKind::open );
      return;
      }
     v_kids.clear();
     detail::bb_process< P >( it->node , it->bound , it->depth , w , inc ,
                              improve , [ & ]( Node && c , Value b ,
                                               unsigned d ) {
                               v_kids.push_back( Item{ std::move( c ) , b ,
                                                       d } );
                               } , o , f_st , f_fr );
     f_sh.evaluated.fetch_add( 1 );
     const std::size_t k = detail::bb_dive( v_kids , f_q.best_bound() ,
                                            inc() , o );
     for( std::size_t j = 0 ; j < v_kids.size() ; ++j )
      if( j == k )
       f_dive.emplace( std::move( v_kids[ j ] ) );
      else
       send( std::move( v_kids[ j ] ) );
     if( ++since_flush >= f_a.f_options.flush_period ) {
      since_flush = 0;
      f_sh.mail.flush( f_id );
      }
     continue;
     }
 
    // nothing to evaluate: send everything, and end if no worker has work
    // and no message is in transit
    if( f_sh.mail.quiescent( f_id ) )
     return;
    backoff.pause();
    }
   }
 
  // pushes a node in the queue
  void push( Item && it ) {
   const Value key = detail::bb_key( f_a.f_p , it.node , it.bound ,
                                      it.depth , f_a.f_options.selection );
   f_q.push( std::move( it.node ) , it.bound , it.depth , key );
   f_st.max_open = std::max( f_st.max_open , f_q.size() );
   }
 
  // the next node: the dive, or the best of the queue; none if there is
  // none, or if none can improve the incumbent (which empties the queue)
  std::optional< Item > next( void ) {
   if( f_dive ) {
    std::optional< Item > it( std::move( f_dive ) );
    f_dive.reset();
    return( it );
    }
   if( f_q.empty() )
    return( std::nullopt );
   const Value best = f_q.best_bound();
   if( detail::bb_prunable( best , f_sh.inc.value() , f_a.f_options ) ) {
    f_st.pruned_extracted += f_fr.add( f_q , BBLeafKind::pruned );
    return( std::nullopt );
    }
   return( f_q.pop() );
   }
 
  // sends a child to its owner, or keeps it if the worker owns it
  void send( Item && it ) {
   const unsigned p = f_sh.p;
   unsigned dst;
   if constexpr( HashedBranchAndBound< P > )
    dst = unsigned( std::uint64_t( f_a.f_p.hash( it.node ) ) % p );
   else
    dst = unsigned( random_below( f_gen , p ) );
   if( dst == f_id ) {
    push( std::move( it ) );
    return;
    }
   f_sh.mail.send( f_id , dst , Msg{ std::move( it.node ) , it.bound ,
                                      it.depth } );
   ++f_st.sent;
   }
 
  // true if a limit is reached, which ends the search
  bool stop( void ) {
   if( ! detail::bb_limit( f_a.f_options , f_sh.evaluated.load() , f_clock ,
                           f_sh.limit , f_sh.time ) )
    return( false );
   f_sh.mail.stop();
   return( true );
   }
 
  const DistributedBranchAndBound & f_a;        // the search
  Shared & f_sh;                                // the shared data
  unsigned f_id;                                // the index of the worker
  const Stopwatch & f_clock;                    // the clock of the search
  BBQueue< Node , Value > f_q;                  // its open nodes
  std::optional< Item > f_dive;                 // the node of its dive
  std::mt19937_64 f_gen;                        // the random owners
  std::vector< Item > v_kids;                   // the children of a node
  BBStats f_st;                                 // its counters
  detail::BBFrontier< Node , Value > f_fr;      // its leaves
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 const P & f_p;                                       
 Options f_options;                           
 Executor * f_ex = nullptr;                   
 
 };  // end( class( DistributedBranchAndBound ) )
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_ParallelBranchAndBound */
 
/*--------------------------------------------------------------------------*/
/*------------------- End File ParallelBranchAndBound.h --------------------*/
/*--------------------------------------------------------------------------*/