BranchAndBound.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*------------------------- File BranchAndBound.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_BranchAndBound
 #define __PBeFS_BranchAndBound
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <algorithm>
 
#include <cmath>
 
#include <concepts>
 
#include <cstddef>
 
#include <cstdint>
 
#include <functional>
 
#include <limits>
 
#include <optional>
 
#include <type_traits>
 
#include <utility>
 
#include <vector>
 
#include "PBeFS/core/SearchUtils.h"
 
#include "ADS/priority/IndexedHeapPair.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*--------------------------------- TYPES ----------------------------------*/
/*--------------------------------------------------------------------------*/

enum class Sense {
 minimize ,     
 maximize       
 };

enum class Selection {
 best_first ,     
 depth_first ,    
 breadth_first ,  
 best_estimate ,  
 plunging         
 };

enum class BBStatus {
 optimal ,      
 infeasible ,   
 node_limit ,   
 time_limit     
 };

template< class V = double >
struct BasicEvaluation {
 V bound = V( 0 );                
 bool infeasible = false;         
 std::optional< V > feasible;     
 };

using Evaluation = BasicEvaluation<>;

enum class BBLeafKind {
 open ,         
 pruned ,       
 feasible ,     
 infeasible     
 };


 
template< class Node , class V = double >
struct BBLeaf {
 Node node;                                
 V bound;                                  
 unsigned depth = 0;                       
 BBLeafKind kind = BBLeafKind::open;       
 };
 
/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS BBValueTraits ---------------------------*/
/*--------------------------------------------------------------------------*/

 
template< class V >
struct BBValueTraits {
 
 static_assert( std::is_arithmetic_v< V > && std::is_signed_v< V > ,
                "BBValueTraits: specialize it for a type that is not a "
                "signed arithmetic one" );

 [[nodiscard]] static constexpr V infinity( void ) noexcept {
  if constexpr( std::numeric_limits< V >::has_infinity )
   return( std::numeric_limits< V >::infinity() );
  else
   return( std::numeric_limits< V >::max() );
  }

 [[nodiscard]] static constexpr V none( void ) noexcept {
  if constexpr( std::numeric_limits< V >::has_quiet_NaN )
   return( std::numeric_limits< V >::quiet_NaN() );
  else
   return( infinity() );
  }

 [[nodiscard]] static constexpr bool finite( V v ) noexcept {
  return( ( v > - infinity() ) && ( v < infinity() ) );
  }

 [[nodiscard]] static V tolerance( V z , V a , double r ) noexcept {
  if constexpr( std::is_floating_point_v< V > )
   return( std::max( a , V( r * std::abs( z ) ) ) );
  else {
   using L = long double;
   return( std::max( a , V( std::floor( L( r ) * std::abs( L( z ) ) ) ) ) );
   }
  }

 [[nodiscard]] static bool within( V b , V l , V z , double g ) noexcept {
  if( ! finite( l ) )
   return( false );
  if constexpr( std::is_floating_point_v< V > )
   return( b <= l + g * ( z - l ) );
  else {
   using L = long double;
   return( L( b ) <= L( l ) + L( g ) * ( L( z ) - L( l ) ) );
   }
  }
 
 };  // end( struct( BBValueTraits ) )
 
/*--------------------------------------------------------------------------*/
 
template< class V >
concept BBValue = std::totally_ordered< V > && std::copyable< V > &&
 std::constructible_from< V , int > &&
 requires( const V & a , double r ) {
  { - a } -> std::convertible_to< V >;
  { a - a } -> std::convertible_to< V >;
  { BBValueTraits< V >::infinity() } -> std::convertible_to< V >;
  { BBValueTraits< V >::none() } -> std::convertible_to< V >;
  { BBValueTraits< V >::finite( a ) } -> std::convertible_to< bool >;
  { BBValueTraits< V >::tolerance( a , a , r ) } -> std::convertible_to< V >;
  { BBValueTraits< V >::within( a , a , a , r ) }
   -> std::convertible_to< bool >;
  };
 
namespace detail {
 template< class N , class V >
 struct bb_sink {
  void operator()( const N & , V ) const noexcept {}
  };

 template< class P >
 struct bb_value { using type = double; };
 
 template< class P > requires requires { typename P::value_type; }
 struct bb_value< P > { using type = typename P::value_type; };
 }  // end( namespace detail )

template< class P >
using bb_value_t = typename detail::bb_value< P >::type;
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- CONCEPTS --------------------------------*/
/*--------------------------------------------------------------------------*/

 
template< class W , class N , class V = double >
concept BBEvaluator = requires( W & w , N & n , const N & cn ) {
 { w.evaluate( n ) } -> std::convertible_to< BasicEvaluation< V > >;
 w.branch( cn , detail::bb_sink< N , V >{} );
 };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
template< class P >
concept BranchAndBound = requires( const P & p , unsigned i ) {
 typename P::node_type;
 requires std::copyable< typename P::node_type >;
 requires BBValue< bb_value_t< P > >;
 { P::sense } -> std::convertible_to< Sense >;
 { p.root() } -> std::convertible_to< typename P::node_type >;
 } && ( BBEvaluator< const P , typename P::node_type , bb_value_t< P > > ||
        requires( const P & p , unsigned i ) {
         { p.make_worker( i ) }
          -> BBEvaluator< typename P::node_type , bb_value_t< P > >;
         } );
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
template< class P >
concept HashedBranchAndBound = BranchAndBound< P > &&
 requires( const P & p , const typename P::node_type & n ) {
  { p.hash( n ) } -> std::convertible_to< std::uint64_t >;
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
template< class P >
concept EstimatingBranchAndBound = BranchAndBound< P > &&
 requires( const P & p , const typename P::node_type & n ) {
  { p.estimate( n ) } -> std::convertible_to< bb_value_t< P > >;
  };
 
/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS BBOptions -----------------------------*/
/*--------------------------------------------------------------------------*/

 
template< class V = double >
struct BasicBBOptions {
 
 Selection selection = Selection::best_first;   
 V abs_gap = V( 0 );           
 double rel_gap = 0;           
 double plunge_gap = 0.5;      
 std::optional< V > incumbent;  
 std::function< V( void ) > shared_incumbent;
 std::size_t node_limit = 0;   
 double time_limit = 0;        
 bool keep_frontier = false;   
 std::function< void( V ) > on_incumbent;
 
 };  // end( struct( BasicBBOptions ) )

using BBOptions = BasicBBOptions<>;
 
/*--------------------------------------------------------------------------*/
/*----------------------------- CLASS BBStats ------------------------------*/
/*--------------------------------------------------------------------------*/

 
struct BBStats {
 
 std::uint64_t evaluated = 0;         
 std::uint64_t branched = 0;          
 std::uint64_t generated = 0;         
 std::uint64_t infeasible = 0;        
 std::uint64_t pruned_generated = 0;  
 std::uint64_t pruned_extracted = 0;  
 std::uint64_t pruned_evaluated = 0;  
 std::uint64_t incumbents = 0;        
 std::uint64_t sent = 0;              
 std::uint64_t messages = 0;          
 std::size_t max_open = 0;            
 double seconds = 0;                  
 std::vector< std::uint64_t > evaluated_by;  
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 void add( const BBStats & o ) {
  evaluated += o.evaluated;
  branched += o.branched;
  generated += o.generated;
  infeasible += o.infeasible;
  pruned_generated += o.pruned_generated;
  pruned_extracted += o.pruned_extracted;
  pruned_evaluated += o.pruned_evaluated;
  incumbents += o.incumbents;
  sent += o.sent;
  messages += o.messages;
  max_open = std::max( max_open , o.max_open );
  evaluated_by.push_back( o.evaluated );
  }
 
 };  // end( struct( BBStats ) )
 
/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS BBSolution ----------------------------*/
/*--------------------------------------------------------------------------*/

 
template< class Node , class V = double >
struct BBSolution {
 
 BBStatus status = BBStatus::infeasible;   
 std::optional< Node > node;               
 V value = BBValueTraits< V >::none();     
 V bound = BBValueTraits< V >::none();     
 V gap = BBValueTraits< V >::infinity();   
 BBStats stats;                            
 std::vector< BBLeaf< Node , V > > frontier;  

 [[nodiscard]] bool feasible( void ) const noexcept {
  return( BBValueTraits< V >::finite( value ) );
  }
 
 };  // end( struct( BBSolution ) )
 
/*--------------------------------------------------------------------------*/
/*----------------------------- CLASS BBQueue ------------------------------*/
/*--------------------------------------------------------------------------*/

 
template< class Node , class V = double >
class BBQueue {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:

 struct Item {
  Node node;          
  V bound;            
  unsigned depth;     
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 explicit BBQueue( Selection s = Selection::best_first )
  : f_fifo( s == Selection::breadth_first ) {}
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 void push( Node && n , V bound , unsigned depth , V key ) {
  std::size_t i;
  if( v_free.empty() ) {
   i = v_slot.size();
   v_slot.emplace_back();
   if( i >= std::size_t( f_q.ids() ) )
    grow( 2 * i + 16 );
   }
  else {
   i = v_free.back();
   v_free.pop_back();
   }
  const std::uint64_t seq = ++f_seq;
  v_slot[ i ].emplace( Item{ std::move( n ) , bound , depth } );
  f_q.push( int( i ) , Order( key , f_fifo ? seq : ~seq ) , bound );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] const Item & top( void ) const {
  return( *v_slot[ std::size_t( f_q.top() ) ] );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 Item pop( void ) {
  const auto i = std::size_t( f_q.pop() );
  Item it = std::move( *v_slot[ i ] );
  v_slot[ i ].reset();
  v_free.push_back( i );
  return( it );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] V best_bound( void ) const {
  return( f_q.empty() ? BBValueTraits< V >::infinity() : f_q.minBound() );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 std::size_t clear( void ) {
  const std::size_t n = f_q.size();
  v_slot.clear();
  v_free.clear();
  f_q.clear();
  return( n );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 template< class F >
 std::size_t drain( F && f ) {
  for( auto & x : v_slot )
   if( x )
    f( std::move( *x ) );
  return( clear() );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] bool empty( void ) const noexcept { return( f_q.empty() ); }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] std::size_t size( void ) const noexcept {
  return( f_q.size() );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:

 using Order = std::pair< V , std::uint64_t >;

 using Queue = ADS::IndexedHeapPair< Order , V >;
 
 // the heaps on n slots, with the nodes they hold
 void grow( std::size_t n ) {
  Queue q{ int( n ) };
  for( std::size_t j = 0 ; j < v_slot.size() ; ++j )
   if( v_slot[ j ] && f_q.contains( int( j ) ) )
    q.push( int( j ) , f_q.key( int( j ) ) , f_q.bound( int( j ) ) );
  f_q = std::move( q );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 bool f_fifo;                          
 std::uint64_t f_seq = 0;              
 std::vector< std::optional< Item > > v_slot;   
 std::vector< std::size_t > v_free;    
 Queue f_q;                            
 
 };  // end( class( BBQueue ) )
 
/*--------------------------------------------------------------------------*/
/*------------------------------- FUNCTIONS --------------------------------*/
/*--------------------------------------------------------------------------*/
 
namespace detail {

 
template< class P >
struct BBSelf {
 const P & p;
 BasicEvaluation< bb_value_t< P > > evaluate( typename P::node_type & n ) {
  return( p.evaluate( n ) );
  }
 template< class F >
 void branch( const typename P::node_type & n , F && f ) {
  p.branch( n , std::forward< F >( f ) );
  }
 };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
template< BranchAndBound P >
auto bb_worker( const P & p , unsigned i ) {
 if constexpr( requires { p.make_worker( i ); } )
  return( p.make_worker( i ) );
 else {
  ( void ) i;
  return( BBSelf< P >{ p } );
  }
 }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
template< BranchAndBound P , class V >
constexpr V bb_signed( const V & v ) {
 if( P::sense == Sense::minimize )
  return( v );
 return( - v );
 }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
template< class V >
bool bb_prunable( const V & bound , const V & inc ,
                  const BasicBBOptions< V > & o )
{
 using Tr = BBValueTraits< V >;
 if( ! Tr::finite( inc ) )
  return( bound == Tr::infinity() );
 return( bound >= inc - Tr::tolerance( inc , o.abs_gap , o.rel_gap ) );
 }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
template< class Node , class V = double >
struct BBFrontier {
 
 explicit BBFrontier( bool k = false ) : keep( k ) {}

 void add( Node && n , V b , unsigned depth , BBLeafKind kind ,
           bool lower = true ) {
  if( lower )
   low = std::min( low , b );
  if( keep )
   leaves.push_back( BBLeaf< Node , V >{ std::move( n ) , b , depth ,
                                         kind } );
  }

 std::size_t add( BBQueue< Node , V > & q , BBLeafKind kind ) {
  low = std::min( low , q.best_bound() );
  if( ! keep )
   return( q.clear() );
  return( q.drain( [ & ]( auto && it ) {
   leaves.push_back( BBLeaf< Node , V >{ std::move( it.node ) , it.bound ,
                                     it.depth , kind } );
   } ) );
  }

 void merge( BBFrontier && o ) {
  low = std::min( low , o.low );
  leaves.insert( leaves.end() , std::make_move_iterator( o.leaves.begin() ) ,
                 std::make_move_iterator( o.leaves.end() ) );
  o.leaves.clear();
  }

 template< class P >
 void take( std::vector< BBLeaf< Node , V > > & v ) {
  for( auto & l : leaves )
   l.bound = bb_signed< P >( l.bound );
  v = std::move( leaves );
  leaves.clear();
  }
 
 bool keep;                                     
 V low = BBValueTraits< V >::infinity();        
 std::vector< BBLeaf< Node , V > > leaves;      
 
 };  // end( struct( BBFrontier ) )
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
template< BranchAndBound P , class Seeds >
std::vector< BBLeaf< typename P::node_type , bb_value_t< P > > > bb_starts(
                                                   const P & p ,
                                                          Seeds && seeds )
{
 using Node = typename P::node_type;
 using V = bb_value_t< P >;
 std::vector< BBLeaf< Node , V > > v;
 if( ! seeds )
  v.push_back( BBLeaf< Node , V >{ p.root() ,
                                   - BBValueTraits< V >::infinity() ,
                               0 , BBLeafKind::open } );
 else {
  v = std::move( *seeds );
  for( auto & l : v )
   l.bound = bb_signed< P >( l.bound );
  }
 return( v );
 }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
template< BranchAndBound P >
bb_value_t< P > bb_key( const P & p , const typename P::node_type & n ,
                       const bb_value_t< P > & bound ,
               unsigned depth , Selection s )
{
 switch( s ) {
  case( Selection::depth_first ):
   return( - bb_value_t< P >( int( depth ) ) );
  case( Selection::breadth_first ):
   return( bb_value_t< P >( int( depth ) ) );
  case( Selection::best_estimate ):
   if constexpr( EstimatingBranchAndBound< P > )
    return( bb_signed< P >( bb_value_t< P >( p.estimate( n ) ) ) );
   else
    return( bound );
  default:
   return( bound );
  }
 }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
template< BranchAndBound P , class W , class Inc , class Improve ,
          class Push >
void bb_process( typename P::node_type & n , bb_value_t< P > bound ,
                 unsigned depth ,
                 W & w , Inc && inc , Improve && improve , Push && push ,
                 const BasicBBOptions< bb_value_t< P > > & o , BBStats & st ,
                 BBFrontier< typename P::node_type , bb_value_t< P > > & fr )
{
 using Node = typename P::node_type;
 using V = bb_value_t< P >;
 const V inf = BBValueTraits< V >::infinity();
 if( bb_prunable( bound , inc() , o ) ) {
  ++st.pruned_extracted;
  fr.add( std::move( n ) , bound , depth , BBLeafKind::pruned );
  return;
  }
 const auto cutoff = [ & ]( void ) {
  if constexpr( requires { w.cutoff( inc() ); } )
   w.cutoff( bb_signed< P >( inc() ) );
  };
 cutoff();
 const BasicEvaluation< V > e = w.evaluate( n );
 ++st.evaluated;
 if( e.infeasible ) {
  ++st.infeasible;
  fr.add( std::move( n ) , inf , depth , BBLeafKind::infeasible , false );
  return;
  }
 const V b = std::max( bound , bb_signed< P >( e.bound ) );
 if( e.feasible && improve( bb_signed< P >( *e.feasible ) , n ) )
  ++st.incumbents;
 const BBLeafKind kind = e.feasible ? BBLeafKind::feasible
                                    : BBLeafKind::pruned;
 if( bb_prunable( b , inc() , o ) ) {
  ++st.pruned_evaluated;
  fr.add( std::move( n ) , b , depth , kind );
  return;
  }
 ++st.branched;
 const std::uint64_t g = st.generated;
 cutoff();
 w.branch( std::as_const( n ) , [ & ]( auto && c , V est ) {
  ++st.generated;
  const V cb = std::max( b , bb_signed< P >( est ) );
  if( bb_prunable( cb , inc() , o ) ) {
   ++st.pruned_generated;
   if( fr.keep )
    fr.add( Node( std::forward< decltype( c ) >( c ) ) , cb , depth + 1 ,
            BBLeafKind::pruned );
   else
    fr.low = std::min( fr.low , cb );
   return;
   }
  push( Node( std::forward< decltype( c ) >( c ) ) , cb , depth + 1 );
  } );
 if( st.generated == g )                // no children: its subtree is n
  fr.add( std::move( n ) , b , depth , kind , false );
 }
 
}  // end( namespace detail )
 
/*--------------------------------------------------------------------------*/
/*----------------------- CLASS BranchAndBoundSearch -----------------------*/
/*--------------------------------------------------------------------------*/

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

 
 explicit BranchAndBoundSearch( const P & problem ,
                                const Options & options = {} ,
                                unsigned worker = 0 )
  : f_p( problem ) , f_options( options ) , f_worker( worker ) {}
 
/*-------------------------------- 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
 {
  using Tr = BBValueTraits< Value >;
  const Value inf = Tr::infinity();
  const Options & o = f_options;
  const Selection sel = o.selection;
  Stopwatch clock;
  SolutionT sol;
  BBStats & st = sol.stats;
  auto w = detail::bb_worker( f_p , f_worker );
 
  Value inc = o.incumbent ? detail::bb_signed< P >( *o.incumbent ) : inf;
  Value cut = inc;          // what prunes: inc, or shared_incumbent if less
  std::optional< Node > inc_node;
  const auto improve = [ & ]( Value v , const Node & n ) {
   if( v >= cut )
    return( false );
   inc = cut = v;
   inc_node = n;
   if( o.on_incumbent )
    o.on_incumbent( detail::bb_signed< P >( v ) );
   return( true );
   };
 
  using Item = typename BBQueue< Node , Value >::Item;
  BBQueue< Node , Value > q( sel );
  std::optional< Item > dive;              // the node of the dive, if any
  std::vector< Item > kids;                // the children of a node
  detail::BBFrontier< Node , Value > fr( o.keep_frontier );  // the leaves
 
  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 } );
  sol.status = BBStatus::optimal;
 
  for( ;; ) {
   if( o.shared_incumbent )
    cut = std::min( cut , detail::bb_signed< P >( o.shared_incumbent() ) );
   if( o.node_limit && ( st.evaluated >= o.node_limit ) ) {
    sol.status = BBStatus::node_limit;
    break;
    }
   if( ( o.time_limit > 0 ) && ( clock.seconds() >= o.time_limit ) ) {
    sol.status = BBStatus::time_limit;
    break;
    }
   const Value best = std::min( q.best_bound() ,
                                 dive ? dive->bound : inf );
   if( q.empty() && ! dive )
    break;
   if( detail::bb_prunable( best , cut , o ) ) {   // nothing can improve
    st.pruned_extracted += fr.add( q , BBLeafKind::pruned );
    if( dive ) {
     ++st.pruned_extracted;
     fr.add( std::move( dive->node ) , dive->bound , dive->depth ,
             BBLeafKind::pruned );
     dive.reset();
     }
    break;
    }
 
   Item it = dive ? std::move( *dive ) : q.pop();
   dive.reset();
   kids.clear();
   detail::bb_process< P >( it.node , it.bound , it.depth , w ,
                            [ & ] { return( cut ); } , improve ,
                            [ & ]( Node && c , Value b , unsigned d ) {
                             kids.push_back( Item{ std::move( c ) , b , d } );
                             } , o , st , fr );
   if( kids.empty() )
    continue;
 
   // with plunging, the best child dives if it is close to the best bound
   std::size_t k = kids.size();
   if( sel == Selection::plunging ) {
    std::size_t c = 0;
    for( std::size_t j = 1 ; j < kids.size() ; ++j )
     if( kids[ j ].bound <= kids[ c ].bound )
      c = j;
    const Value b0 = std::min( q.best_bound() , kids[ c ].bound );
    if( ! Tr::finite( cut ) ||
        Tr::within( kids[ c ].bound , b0 , cut , o.plunge_gap ) )
     k = c;
    }
   for( std::size_t j = 0 ; j < kids.size() ; ++j )
    if( j == k )
     dive.emplace( std::move( kids[ j ] ) );
    else
     push( std::move( kids[ j ] ) );
   }
 
  // the open nodes left by a limit bound the optimum too
  fr.add( q , BBLeafKind::open );
  if( dive )
   fr.add( std::move( dive->node ) , dive->bound , dive->depth ,
           BBLeafKind::open );
  if( ( sol.status == BBStatus::optimal ) && ! Tr::finite( inc ) )
   sol.status = BBStatus::infeasible;
  sol.node = std::move( inc_node );
  if( Tr::finite( inc ) )
   sol.value = detail::bb_signed< P >( inc );
  const Value lb = std::min( inc , fr.low );
  sol.bound = detail::bb_signed< P >( lb );
  sol.gap = Tr::finite( inc ) && Tr::finite( lb ) ? Value( inc - lb ) : inf;
  fr.template take< P >( sol.frontier );
  st.evaluated_by = { st.evaluated };
  st.seconds = clock.seconds();
  return( sol );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 const P & f_p;                                      
 Options f_options;                                   
 unsigned f_worker;                                   
 
 };  // end( class( BranchAndBoundSearch ) )
 
/*--------------------------------------------------------------------------*/
/*------------------------------- FUNCTIONS --------------------------------*/
/*--------------------------------------------------------------------------*/
 
template< BranchAndBound P >
[[nodiscard]] BBSolution< typename P::node_type , bb_value_t< P > >
 branch_and_bound( const P & problem ,
                   const BasicBBOptions< bb_value_t< P > > & o = {} )
{
 return( BranchAndBoundSearch< P >( problem , o ).solve() );
 }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
template< BranchAndBound P >
[[nodiscard]] BBSolution< typename P::node_type , bb_value_t< P > >
 branch_and_bound( const P & problem ,
                   std::vector< BBLeaf< typename P::node_type ,
                                        bb_value_t< P > > > seeds ,
                   const BasicBBOptions< bb_value_t< P > > & o = {} )
{
 return( BranchAndBoundSearch< P >( problem , o ).solve(
                                                       std::move( seeds ) ) );
 }
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_BranchAndBound */
 
/*--------------------------------------------------------------------------*/
/*----------------------- End File BranchAndBound.h ------------------------*/
/*--------------------------------------------------------------------------*/