BranchAndBoundScheme.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*---------------------- File BranchAndBoundScheme.h -----------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_BranchAndBoundScheme
 #define __PBeFS_BranchAndBoundScheme
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <array>
 
#include <optional>
 
#include <stdexcept>
 
#include <string>
 
#include <string_view>
 
#include <utility>
 
#include <vector>
 
#include "PBeFS/bnb/DeterministicBranchAndBound.h"
 
#include "PBeFS/bnb/MultiQueueBranchAndBound.h"
 
#include "PBeFS/bnb/ParallelBranchAndBound.h"
 
#include "PBeFS/bnb/SelfSplitBranchAndBound.h"
 
#include "PBeFS/bnb/StealingBranchAndBound.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*----------------------------- ENUM BBScheme ------------------------------*/
/*--------------------------------------------------------------------------*/

 
enum class BBScheme {
 sequential ,      
 shared ,          
 distributed ,     
 deterministic ,   
 selfsplit ,       
 stealing ,        
 multiqueue        
 };
 
/*--------------------------------------------------------------------------*/
/*------------------------------- FUNCTIONS --------------------------------*/
/*--------------------------------------------------------------------------*/
 
namespace detail {
 inline constexpr std::array< std::string_view , 7 > bb_scheme_names = {
  "sequential" , "shared" , "distributed" , "deterministic" , "selfsplit" ,
  "stealing" , "multiqueue" };
 }  // end( namespace detail )
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
[[nodiscard]] inline std::string_view bb_scheme_name( BBScheme s ) {
 return( detail::bb_scheme_names.at( std::size_t( s ) ) );
 }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
[[nodiscard]] inline BBScheme bb_scheme( std::string_view name ) {
 for( std::size_t i = 0 ; i < detail::bb_scheme_names.size() ; ++i )
  if( detail::bb_scheme_names[ i ] == name )
   return( BBScheme( i ) );
 throw( std::invalid_argument( "bb_scheme: unknown scheme " +
                               std::string( name ) ) );
 }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
template< BranchAndBound P , ADS::WorkerExecutor Executor = ADS::ThreadPool >
[[nodiscard]] BBSolution< typename P::node_type , bb_value_t< P > >
 parallel_branch_and_bound( const P & problem , BBScheme s ,
                            const BasicParallelBBOptions< bb_value_t< P > > &
                             o = {} ,
                            std::optional< std::vector< BBLeaf<
                             typename P::node_type , bb_value_t< P > > > >
                             seeds = std::nullopt )
{
 const auto solve = [ & ]( const auto & b ) {
  return( seeds ? b.solve( std::move( *seeds ) ) : b.solve() );
  };
 switch( s ) {
  case( BBScheme::sequential ):
   return( solve( BranchAndBoundSearch< P >( problem , o ) ) );
  case( BBScheme::shared ):
   return( solve( SharedBranchAndBound< P , Executor >( problem , o ) ) );
  case( BBScheme::distributed ):
   return( solve( DistributedBranchAndBound< P , Executor >( problem ,
                                                             o ) ) );
  case( BBScheme::deterministic ):
   return( solve( DeterministicBranchAndBound< P , Executor >( problem ,
                                                               o ) ) );
  case( BBScheme::selfsplit ):
   return( solve( SelfSplitBranchAndBound< P , Executor >( problem , o ) ) );
  case( BBScheme::multiqueue ):
   if constexpr( MultiQueueValue< bb_value_t< P > > )
    return( solve( MultiQueueBranchAndBound< P , Executor >( problem ,
                                                             o ) ) );
   else
    throw( std::invalid_argument( "parallel_branch_and_bound: the scheme "
                                  "multiqueue needs values atomic with no "
                                  "lock" ) );
  default:
   return( solve( StealingBranchAndBound< P , Executor >( problem , o ) ) );
  }
 }
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_BranchAndBoundScheme */
 
/*--------------------------------------------------------------------------*/
/*-------------------- End File BranchAndBoundScheme.h ---------------------*/
/*--------------------------------------------------------------------------*/