SelfSplitBranchAndBound.h

Go to the documentation of this file.

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

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*--------------------- CLASS SelfSplitBranchAndBound ----------------------*/
/*--------------------------------------------------------------------------*/

 
template< BranchAndBound P , ADS::WorkerExecutor Executor = ADS::ThreadPool >
class SelfSplitBranchAndBound {
 
/*------------------------ 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 SelfSplitBranchAndBound( const P & problem ,
                                   const Options & options = {} )
  : f_p( problem ) , f_options( options ) {
  f_options.normalize();
  if( f_options.split == 0 )
   f_options.split = 4;
  }
 
/*------------------------- 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
 {
  using Tr = BBValueTraits< Value >;
  const Value inf = Tr::infinity();
  const Options & o = f_options;
  const unsigned p = o.threads;
  const bool sample = p > 1;        // one worker has nothing to split
  Stopwatch clock;
 
  // the sampling, by the evaluator of the worker 0
  SolutionT sol;
  BBStats & st = sol.stats;
  const Selection sel = o.selection == Selection::plunging ?
                        Selection::best_first : o.selection;
  BBQueue< Node , Value > q( sel );
  const auto push = [ & ]( Item && it ) {
   const Value key = detail::bb_key( f_p , it.node , it.bound , it.depth ,
                                      sel );
   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 } );
 
  Value inc = o.incumbent ? detail::bb_signed< P >( *o.incumbent ) : inf;
  std::optional< Node > inc_node;
  detail::BBFrontier< Node , Value > fr( o.keep_frontier );
  bool limit = false , late = false;
  {
   auto w = detail::bb_worker( f_p , 0u );
   const auto improve = [ & ]( Value v , const Node & n ) {
    if( v >= inc )
     return( false );
    inc = v;
    inc_node = n;
    if( o.on_incumbent )
     o.on_incumbent( detail::bb_signed< P >( v ) );
    return( true );
    };
   std::vector< Item > kids;
   while( sample && ! q.empty() && ( q.size() < o.split * p ) ) {
    if( o.node_limit && ( st.evaluated >= o.node_limit ) ) {
     limit = true;
     break;
     }
    if( ( o.time_limit > 0 ) && ( clock.seconds() >= o.time_limit ) ) {
     limit = late = true;
     break;
     }
    if( detail::bb_prunable( q.best_bound() , inc , o ) ) {
     st.pruned_extracted += fr.add( q , BBLeafKind::pruned );
     break;                            // nothing can improve
     }
    Item it = q.pop();
    kids.clear();
    detail::bb_process< P >( it.node , it.bound , it.depth , w ,
                             [ & ] { return( inc ); } , improve ,
                             [ & ]( Node && c , Value b , unsigned d ) {
                              kids.push_back( Item{ std::move( c ) , b ,
                                                    d } );
                              } , o , st , fr );
    for( Item & k : kids )
     push( std::move( k ) );
    }
 
   // the dive, from a copy of the first open node: its leaves are not
   // leaves of the search, whose open nodes still cover them
   if( sample && o.split_dive && ! limit && ! q.empty() &&
       ! detail::bb_prunable( q.best_bound() , inc , o ) ) {
    detail::BBFrontier< Node , Value > none( false );
    const Item & top = q.top();
    Item d{ Node( top.node ) , top.bound , top.depth };
    for( ;; ) {
     if( o.node_limit && ( st.evaluated >= o.node_limit ) )
      break;
     if( ( o.time_limit > 0 ) && ( clock.seconds() >= o.time_limit ) )
      break;
     kids.clear();
     detail::bb_process< P >( d.node , d.bound , d.depth , w ,
                              [ & ] { return( inc ); } , improve ,
                              [ & ]( Node && c , Value b , unsigned dp ) {
                               kids.push_back( Item{ std::move( c ) , b ,
                                                     dp } );
                               } , o , st , none );
     if( kids.empty() )
      break;
     std::size_t c = 0;
     Value best = inf;
     for( std::size_t j = 0 ; j < kids.size() ; ++j ) {
      const Value e = detail::bb_key( f_p , kids[ j ].node , kids[ j ].bound ,
                                      kids[ j ].depth ,
                                      Selection::best_estimate );
      if( ( j == 0 ) || ( e < best ) ) {
       c = j;
       best = e;
       }
      }
     d = std::move( kids[ c ] );
     }
    }
  }
 
  // the split: the k-th open node, in the order of the selection, to the
  // worker k mod p, unless a limit or the incumbent ends the search here
  std::vector< std::vector< Leaf > > part( p );
  if( ! limit && ! q.empty() &&
      detail::bb_prunable( q.best_bound() , inc , o ) )
   st.pruned_extracted += fr.add( q , BBLeafKind::pruned );
  std::uint64_t rest = 0;                       // the evaluations left
  double time = 0;                              // the time left
  if( o.node_limit && ! limit )
   rest = o.node_limit - st.evaluated;
  if( ( o.time_limit > 0 ) && ! limit ) {
   time = o.time_limit - clock.seconds();
   if( time <= 0 )
    limit = late = true;
   }
  if( ! limit )
   for( std::size_t k = 0 ; ! q.empty() ; ++k ) {
    Item it = q.pop();
    const unsigned i = unsigned( k % p );
    if( o.node_limit && ( share( rest , p , i ) == 0 ) ) {
     limit = true;                      // a node left open by the limit
     fr.add( std::move( it.node ) , it.bound , it.depth , BBLeafKind::open );
     }
    else
     part[ i ].push_back( Leaf{ std::move( it.node ) ,
                                detail::bb_signed< P >( it.bound ) ,
                                it.depth , BBLeafKind::open } );
    }
  fr.add( q , BBLeafKind::open );        // left open by a limit
  st.evaluated_by.assign( p , 0 );
  st.evaluated_by[ 0 ] = st.evaluated;
 
  // the workers, each with its share of the limits and an incumbent that
  // calls on_incumbent only when it improves on all of them, and that with
  // split_shared prunes the nodes of all of them
  std::vector< std::optional< SolutionT > > out( p );
  std::mutex m;
  BBIncumbent< std::monostate , Value > best( inc );   // the best value
  std::exception_ptr error;
  run_workers( f_ex , p , [ & ]( unsigned i ) {
   if( part[ i ].empty() )
    return;
   try {
    BasicBBOptions< Value > wo = o;
    if( Tr::finite( inc ) )
     wo.incumbent = detail::bb_signed< P >( inc );
    wo.node_limit = o.node_limit ? share( rest , p , i ) : 0;
    wo.time_limit = time;
    wo.on_incumbent = [ & ]( Value v ) {
     ( void ) best.template improve< P >( detail::bb_signed< P >( v ) ,
                                          std::monostate() , o );
     };
    if( o.split_shared )
     wo.shared_incumbent = [ & ] {
      return( detail::bb_signed< P >( best.value() ) );
      };
    out[ i ] = BranchAndBoundSearch< P >( f_p , wo , i ).solve(
                                                  std::move( part[ i ] ) );
    }
   catch( ... ) {
    std::lock_guard< std::mutex > guard( m );
    if( ! error )
     error = std::current_exception();
    }
   } );
  if( error )
   std::rethrow_exception( error );
 
  // the merge, in the order of the workers
  Value low = std::min( inc , fr.low );
  fr.template take< P >( sol.frontier );
  for( unsigned i = 0 ; i < p ; ++i ) {
   if( ! out[ i ] )
    continue;
   SolutionT & s = *out[ i ];
   if( s.node && ( detail::bb_signed< P >( s.value ) < inc ) ) {
    inc = detail::bb_signed< P >( s.value );
    inc_node = std::move( s.node );
    }
   low = std::min( low , detail::bb_signed< P >( s.bound ) );
   if( s.status == BBStatus::time_limit )
    limit = late = true;
   else
    if( s.status == BBStatus::node_limit )
     limit = true;
   st.add( s.stats );                    // which appends its evaluations
   st.evaluated_by.pop_back();
   st.evaluated_by[ i ] += s.stats.evaluated;
   sol.frontier.insert( sol.frontier.end() ,
                        std::make_move_iterator( s.frontier.begin() ) ,
                        std::make_move_iterator( s.frontier.end() ) );
   }
 
  if( limit )
   sol.status = late ? BBStatus::time_limit : BBStatus::node_limit;
  else
   sol.status = Tr::finite( inc ) ? BBStatus::optimal
                                  : BBStatus::infeasible;
  sol.node = std::move( inc_node );
  if( Tr::finite( inc ) )
   sol.value = detail::bb_signed< P >( inc );
  low = std::min( low , inc );
  sol.bound = detail::bb_signed< P >( low );
  sol.gap = Tr::finite( inc ) && Tr::finite( low ) ? Value( inc - low )
                                                   : inf;
  st.seconds = clock.seconds();
  return( sol );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the evaluations of the worker i of p out of the rest of the node limit
 
 static std::uint64_t share( std::uint64_t rest , unsigned p , unsigned i )
  noexcept {
  return( rest / p + ( i < rest % p ? 1 : 0 ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 const P & f_p;                                       
 Options f_options;                           
 Executor * f_ex = nullptr;                   
 
 };  // end( class( SelfSplitBranchAndBound ) )
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_SelfSplitBranchAndBound */
 
/*--------------------------------------------------------------------------*/
/*------------------- End File SelfSplitBranchAndBound.h -------------------*/
/*--------------------------------------------------------------------------*/