FarmBranchAndBound.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*----------------------- File FarmBranchAndBound.h ------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_FarmBranchAndBound
 #define __PBeFS_FarmBranchAndBound
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <atomic>
 
#include <memory>
 
#include <stdexcept>
 
#include <vector>
 
#include "PBeFS/bnb/ParallelBranchAndBound.h"
 
#include "ADS/parallel/Farm.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*------------------------ CLASS FarmBranchAndBound ------------------------*/
/*--------------------------------------------------------------------------*/

 
template< BranchAndBound P , ADS::WorkerExecutor Executor = ADS::ThreadPool >
class FarmBranchAndBound {
 
/*------------------------ 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 FarmBranchAndBound( 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;
 
 SolutionT run( std::optional< std::vector< Leaf > > seeds ) const
 {
  const Value inf = BBValueTraits< Value >::infinity();
  Stopwatch clock;
  const Value start = f_options.incumbent ?
                      detail::bb_signed< P >( *f_options.incumbent ) : inf;
  Shared sh( start , clock );
  Master master( *this , sh , detail::bb_starts( f_p , std::move( seeds ) ) );
  const unsigned n = f_options.threads;
  std::vector< std::unique_ptr< Worker > > w( n );
  for( unsigned i = 0 ; i < n ; ++i )
   w[ i ] = std::make_unique< Worker >( *this , sh , i );
  const auto begin = [ & ]( auto && emit , std::size_t ) {
   if( ! ADS::isRunCaller() )
    pin_worker( 0 );
   master.start( emit );
   };
  const auto back = [ & ]( Task * t , auto && emit ) {
   return( master.back( t , emit ) );
   };
  const auto work = [ & ]( Task * t , std::size_t i ) {
   return( w[ i ]->process( t ) );
   };
  if( f_ex )
   ADS::feedbackFarm< Task * , Task * >( *f_ex , n , begin , back , work );
  else {
   Executor ex( n + 1 );
   ADS::feedbackFarm< Task * , Task * >( ex , n , begin , back , work );
   }
 
  SolutionT sol;
  // left open by a limit
  detail::BBFrontier< Node , Value > & fr = master.f_fr;
  fr.add( master.f_q , BBLeafKind::open );
  for( auto & x : w ) {
   sol.stats.add( x->f_st );
   fr.merge( std::move( x->f_fr ) );
   }
  sol.stats.pruned_extracted += master.f_st.pruned_extracted;
  sol.stats.max_open = master.f_st.max_open;
  sol.stats.messages = master.f_st.messages;
  detail::bb_finish< P >( sol , sh.inc , fr , sh.limit.load() ,
                          sh.time.load() );
  sol.stats.seconds = clock.seconds();
  return( sol );
  }
 
 // a task: the nodes to evaluate, and then the children that survive
 struct Task {
  std::vector< Item > nodes;                    // the nodes
  std::vector< Item > kids;                     // their children
  Value best = Value( 0 );                      // the best open bound
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the data shared by the master and the workers
 
 struct Shared {
 
  Shared( Value z , const Stopwatch & c ) : inc( z ) , clock( c ) {}
 
  BBIncumbent< Node , Value > inc;              // the incumbent
  const Stopwatch & clock;                      // the clock of the search
  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
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the master: the queue of the open nodes
 
 struct Master {
 
  Master( const FarmBranchAndBound & a , Shared & s ,
          std::vector< Leaf > && starts )
   : f_a( a ) , f_sh( s ) , f_q( a.f_options.selection ) ,
     f_fr( a.f_options.keep_frontier ) , v_starts( std::move( starts ) ) {}
 
  Master( const Master & ) = delete;
  Master & operator=( const Master & ) = delete;
 
  ~Master() {
   for( Task * t : v_free )
    delete t;
   }
 
  // the start: the first nodes, and the first tasks
  template< class E >
  void start( E && emit ) {
   for( auto & l : v_starts )
    enqueue( Item{ std::move( l.node ) , l.bound , l.depth } );
   v_starts.clear();
   check_limits();
   dispatch( emit );
   }
 
  // a task back, with the children of its nodes; false once nothing is
  // out at the workers and nothing is left to send
  template< class E >
  bool back( Task * t , E && emit ) {
   --f_out;
   for( Item & it : t->kids )
    enqueue( std::move( it ) );
   t->kids.clear();
   v_free.push_back( t );
   check_limits();
   dispatch( emit );
   return( ( f_out > 0 ) || ( ! f_sh.limit.load() && ! f_q.empty() ) );
   }
 
  // pushes a node in the queue
  void enqueue( 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() );
   }
 
  // stops the dispatch if a limit is reached
  void check_limits( void ) {
   ( void ) detail::bb_limit( f_a.f_options , f_sh.evaluated.load() ,
                              f_sh.clock , f_sh.limit , f_sh.time );
   }
 
  // sends tasks while there are nodes and free workers
  template< class E >
  void dispatch( E && emit ) {
   while( ! f_sh.limit.load() && ( f_out < f_a.f_options.threads ) &&
          ! f_q.empty() ) {
    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;                                    // nothing can improve
     }
    Task * t;
    if( v_free.empty() )
     t = new Task;
    else {
     t = v_free.back();
     v_free.pop_back();
     }
    t->nodes.clear();
    while( ! f_q.empty() && ( t->nodes.size() < f_a.f_options.batch ) )
     t->nodes.push_back( f_q.pop() );
    t->best = std::min( best , f_q.best_bound() );
    ++f_out;
    ++f_st.messages;
    emit( t );
    }
   }
 
  const FarmBranchAndBound & f_a;               // the search
  Shared & f_sh;                                // the shared data
  BBQueue< Node , Value > f_q;                  // the open nodes
  std::vector< Task * > v_free;                 // tasks to reuse
  unsigned f_out = 0;                           // tasks at the workers
  BBStats f_st;                                 // its counters
  detail::BBFrontier< Node , Value > f_fr;      // its leaves
  std::vector< Leaf > v_starts;       // the nodes to start from
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // a worker: evaluates and branches the nodes of a task
 
 struct Worker {
 
  Worker( const FarmBranchAndBound & a , Shared & s , unsigned i )
   : f_a( a ) , f_sh( s ) , f_id( i ) ,
     f_fr( a.f_options.keep_frontier ) {}
 
  // the nodes of t evaluated and branched, the children in t
  Task * process( Task * t ) {
   if( ! f_w ) {                     // the first task, on its own thread
    if( ! ADS::isRunCaller() )
     pin_worker( f_id + 1 );
    f_w.emplace( 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( Item & first : t->nodes ) {
    std::optional< Item > it( std::move( first ) );
    while( it ) {                  // the node, then the child that dives
     v_kids.clear();
     detail::bb_process< P >( it->node , it->bound , it->depth , *f_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 );
     it.reset();
     const std::size_t k = detail::bb_dive( v_kids , t->best , inc() , o );
     for( std::size_t j = 0 ; j < v_kids.size() ; ++j )
      if( j == k )
       it.emplace( std::move( v_kids[ j ] ) );
      else
       t->kids.push_back( std::move( v_kids[ j ] ) );
     if( it && o.node_limit &&
         ( f_sh.evaluated.load() >= o.node_limit ) ) {
      t->kids.push_back( std::move( *it ) );     // the dive stops here
      it.reset();
      }
     }
    }
   t->nodes.clear();
   return( t );
   }
 
  using Evaluator = decltype( detail::bb_worker( std::declval< const P & >() ,
                                                 0u ) );
 
  const FarmBranchAndBound & f_a;               // the search
  Shared & f_sh;                                // the shared data
  unsigned f_id;                                // the index of the worker
  std::optional< Evaluator > f_w;               // its evaluator
  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( FarmBranchAndBound ) )
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_FarmBranchAndBound */
 
/*--------------------------------------------------------------------------*/
/*--------------------- End File FarmBranchAndBound.h ----------------------*/
/*--------------------------------------------------------------------------*/