- Generated by
1.15.0
|
PBeFS
Parallel Best-First Search
|
Header file for the best-first search with an incumbent, i.e., for Branch-and-Bound (B&B): the concept BranchAndBound of a problem, its options and its Solution, the queue of the open nodes, and the sequential search BranchAndBoundSearch. More...
#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"Go to the source code of this file.
Classes | |
| struct | BasicEvaluation< V > |
| the outcome of the evaluation of a node, with values of type V More... | |
| struct | BBLeaf< Node, V > |
| a leaf of the tree explored, or a node to start a search from More... | |
| struct | BBValueTraits< V > |
| what the B&B needs to know of the type V of its values More... | |
| struct | BasicBBOptions< V > |
| the options of a B&B with values of type V More... | |
| struct | BBStats |
| the counters of a B&B More... | |
| struct | BBSolution< Node, V > |
| the outcome of a B&B More... | |
| class | BBQueue< Node, V > |
| the open nodes of a B&B, ordered by a key More... | |
| struct | BBQueue< Node, V >::Item |
| an open node More... | |
| class | BranchAndBoundSearch< P > |
| the sequential best-first search with an incumbent More... | |
Namespaces | |
| namespace | PBeFS_di_unipi_it |
| namespace for the Parallel Best-First Search library | |
Concepts | |
| concept | PBeFS_di_unipi_it::BBValue |
| a type of values of a B&B: signed, totally ordered, made from an int, and with its BBValueTraits | |
| concept | PBeFS_di_unipi_it::BBEvaluator |
| what evaluates and branches the nodes of a B&B | |
| concept | PBeFS_di_unipi_it::BranchAndBound |
| a B&B problem | |
| concept | PBeFS_di_unipi_it::HashedBranchAndBound |
| a B&B problem that gives a hash of its nodes | |
| concept | PBeFS_di_unipi_it::EstimatingBranchAndBound |
| a B&B problem that estimates the best feasible value under a node | |
Typedefs | |
| using | Evaluation = BasicEvaluation<> |
| the outcome of the evaluation of a node, with values of type double | |
| template<class P> | |
| using | bb_value_t = typename detail::bb_value< P >::type |
| the type of the values of the B&B problem P: its value_type, or double | |
| using | BBOptions = BasicBBOptions<> |
| the options of a B&B with values of type double | |
Enumerations | |
| enum class | Sense { minimize , maximize } |
| the sense of the optimization More... | |
| enum class | Selection { best_first , depth_first , breadth_first , best_estimate , plunging } |
| the order in which the open nodes are extracted More... | |
| enum class | BBStatus { optimal , infeasible , node_limit , time_limit } |
| how a B&B ended More... | |
| enum class | BBLeafKind { open , pruned , feasible , infeasible } |
| why a node is a leaf of the tree explored More... | |
Functions | |
| template<BranchAndBound P> | |
| BBSolution< typename P::node_type, bb_value_t< P > > | branch_and_bound (const P &problem, const BasicBBOptions< bb_value_t< P > > &o={}) |
| the sequential B&B of a problem, with the given options | |
| template<BranchAndBound P> | |
| 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={}) |
| the sequential B&B of the subtrees of the given nodes [see BranchAndBoundSearch::solve()], with the given options | |
Header file for the best-first search with an incumbent, i.e., for Branch-and-Bound (B&B): the concept BranchAndBound of a problem, its options and its Solution, the queue of the open nodes, and the sequential search BranchAndBoundSearch.
The parallel searches are in ParallelBranchAndBound.h, and the design is discussed in docs/branch-and-bound.md.
The values (bounds, feasible values, incumbent and absolute tolerance) are of the value_type of the problem, double if it gives none: any signed type with a total order for which BBValueTraits says what infinity is and how large the tolerance of a gap is, e.g., a floating point type, an integer one (whose bounds are then integer, which prunes the nodes whose bound equals the incumbent) or a type of exact arithmetic for which the caller specializes BBValueTraits; a maximization problem is solved by negating them internally, so that the code below only minimizes.
The sequential search is the following, with the notation of the page "Branch-and-bound as best-first search" of the documentation and the conventions of the pseudocode of the page "Best-first search and A*": \( \beta( n ) \) is the bound of the node \( n \), inherited from its parent until \( n \) is evaluated, \( z \) the incumbent value, Q the queue of the open nodes, ordered by the key of the selection, \( \gamma \) the fraction plunge_gap of the dive, and the leaves are the nodes that the search does not branch, which give the bound on the optimum:
A node is pruned when it is generated (line 26), when it is extracted (line 17, by an incumbent found after its generation) and after its evaluation (line 22, by its own bound), with the absolute and relative tolerances \( \tau_a \) and \( \tau_r \) (abs_gap and rel_gap); every element of the set below \( z - \max \{ \tau_a , \tau_r |z| \} \) stays in the subset of an open node, and hence the search may stop at line 6 as soon as no open node can improve \( z \) by more than the tolerance. The parallel searches use the same PROCESS, each with the incumbent it sees.
1.15.0