StealingBranchAndBound.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*--------------------- File StealingBranchAndBound.h ----------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_StealingBranchAndBound
 #define __PBeFS_StealingBranchAndBound
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <atomic>
 
#include <cstdint>
 
#include <memory>
 
#include <optional>
 
#include <utility>
 
#include <vector>
 
#include "PBeFS/bnb/ParallelBranchAndBound.h"
 
#include "ADS/concurrent/StealablePriorityQueue.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*---------------------- CLASS StealingBranchAndBound ----------------------*/
/*--------------------------------------------------------------------------*/

 
template< BranchAndBound P , ADS::WorkerExecutor Executor = ADS::ThreadPool >
class StealingBranchAndBound {
 
/*------------------------ 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 StealingBranchAndBound( 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:
 
 // a node in a queue: the node and its depth, its bound being the bound of
 // the pair
 struct Held {
  Node node;          // the node
  unsigned depth;     // its depth in the tree
  };
 
 // the order of the selection: the key, then the push, reversed (the last
 // pushed first) unless first in, first out
 using Order = std::pair< Value , std::uint64_t >;
 
 using Frontier = ADS::StealingFrontier< Order , Held , std::less<> , Value >;
 using Item = typename BBQueue< Node , Value >::Item;
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 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.seed );
 
  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 );
  std::size_t n = 0;
  for( auto & l : detail::bb_starts( f_p , std::move( seeds ) ) )
   w[ n++ % p ]->push( Item{ std::move( l.node ) , l.bound , l.depth } );
 
  const auto body = [ & ]( std::size_t i ) {
   if( ! ADS::isRunCaller() )
    pin_worker( unsigned( i ) );
   w[ i ]->run();
   };
  if( f_ex )
   sh.frontier.run( *f_ex , body );
  else {
   Executor ex( p );
   sh.frontier.run( ex , body );
   }
 
  // the nodes left open by a limit bound the optimum too
  SolutionT sol;
  detail::BBFrontier< Node , Value > fr( f_options.keep_frontier );
  for( auto & x : w ) {
   sol.stats.add( x->f_st );
   fr.merge( std::move( x->f_fr ) );
   if( x->f_dive )
    fr.add( std::move( x->f_dive->node ) , x->f_dive->bound ,
            x->f_dive->depth , BBLeafKind::open );
   }
  sh.frontier.leftovers( [ & ]( auto && e ) {
   fr.add( std::move( e.item.node ) , e.bound , e.item.depth ,
           BBLeafKind::open );
   } );
  sol.stats.sent = sh.frontier.steals();
  detail::bb_finish< P >( sol , sh.inc , fr , sh.limit.load() ,
                          sh.time.load() );
  sol.stats.seconds = clock.seconds();
  return( sol );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the data shared by the workers
 
 struct Shared {
 
  Shared( unsigned np , Value z , std::uint64_t seed )
   : frontier( np , seed ) , inc( z ) {}
 
  Frontier frontier;                            // the queues
  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 counters, its dive and its leaves; its queue is in the
 // frontier
 
 struct alignas( cache_line ) Worker {
 
  Worker( const StealingBranchAndBound & a , Shared & s , unsigned i ,
          const Stopwatch & c )
   : f_a( a ) , f_sh( s ) , f_id( i ) , f_clock( c ) ,
     f_fifo( a.f_options.selection == Selection::breadth_first ) ,
     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( ;; ) {
    std::optional< Item > it = next();
    if( ! it )
     return;
    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 , 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
      push( std::move( v_kids[ j ] ) );
    }
   }
 
  // pushes a node in the queue of the worker
  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 );
   const std::uint64_t seq = ++f_seq;
   f_sh.frontier.push( f_id , Order( key , f_fifo ? seq : ~seq ) , it.bound ,
                       Held{ std::move( it.node ) , it.depth } );
   f_st.max_open = std::max( f_st.max_open ,
                             f_sh.frontier.queue( f_id ).size() );
   }
 
  // the least bound of the nodes of the queue of the worker, +infinity if
  // there is none
  [[nodiscard]] Value best_bound( void ) const {
   const auto b = f_sh.frontier.minBound( f_id );
   return( b ? *b : BBValueTraits< Value >::infinity() );
   }
 
  // the next node: the dive, the best of the queue, or the best of what is
  // stolen; none when the search is over, i.e., when no worker holds a
  // node or a limit is reached; the queue is dropped when none of its
  // nodes can improve the incumbent
  std::optional< Item > next( void ) {
   if( f_dive ) {
    std::optional< Item > it( std::move( f_dive ) );
    f_dive.reset();
    return( it );
    }
   if( const auto b = f_sh.frontier.minBound( f_id ) ;
       b && detail::bb_prunable( *b , f_sh.inc.value() , f_a.f_options ) )
    f_st.pruned_extracted += f_sh.frontier.drain( f_id , [ & ]( auto && e ) {
     f_fr.add( std::move( e.item.node ) , e.bound , e.item.depth ,
               BBLeafKind::pruned );
     } );
   auto e = f_sh.frontier.pop( f_id );
   if( ! e )
    return( std::nullopt );
   return( Item{ std::move( e->item.node ) , e->bound , e->item.depth } );
   }
 
  // 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.frontier.stop();
   return( true );
   }
 
  const StealingBranchAndBound & 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
  bool f_fifo;                                  // first in, first out
  std::uint64_t f_seq = 0;                      // the pushes so far
  std::optional< Item > f_dive;                 // the node of its dive
  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( StealingBranchAndBound ) )
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_StealingBranchAndBound */
 
/*--------------------------------------------------------------------------*/
/*------------------- End File StealingBranchAndBound.h --------------------*/
/*--------------------------------------------------------------------------*/