bnb/BranchAndBound.h

Header of the layer bnb, in the group Searches; the same header on the site of Doxygen, its source on GitHub.

Classes

Class	Description
BasicEvaluation	The outcome of the evaluation of a node, with values of type V
BBLeaf	A leaf of the tree explored, or a node to start a search from
BBValueTraits	What the B&B needs to know of the type V of its values
BasicBBOptions	The options of a B&B with values of type V
BBStats	The counters of a B&B
BBSolution	The outcome of a B&B
BBQueue	The open nodes of a B&B, ordered by a key
BranchAndBoundSearch	The sequential best-first search with an incumbent

Concepts

template<class V>
concept BBValue

#include <PBeFS/bnb/BranchAndBound.h>

a type of values of a B&B: signed, totally ordered, made from an int, and with its BBValueTraits

template<class W, class N, class V = double>
concept BBEvaluator

#include <PBeFS/bnb/BranchAndBound.h>

what evaluates and branches the nodes of a B&B

evaluate( n ) returns the Evaluation of the node n, possibly storing in n what the branching needs, and branch( n , sink ) calls sink( c , e ) for every child c of the evaluated node n, e being a bound of c that is cheap to compute (typically the bound of n).

Optionally, the evaluator may give cutoff( z ), which the searches call before each evaluate( n ) and branch( n , sink ) with the incumbent value z (in the sense of the problem, infinite when there is none), e.g., to stop the relaxation of a node as soon as it is proven not to improve z, the node being then found infeasible. A worker should take z from here rather than from a value it shares with the others: in the deterministic search z is the incumbent of the start of the round [see DeterministicBranchAndBound], so that the evaluation does not depend on what the other workers find meanwhile.

template<class P>
concept BranchAndBound

#include <PBeFS/bnb/BranchAndBound.h>

a B&B problem

A type P is a BranchAndBound problem if it provides the copyable type node_type, the constant sense, the method root() giving the node of the whole set, optionally the type value_type of its values [see BBValue], double if it gives none, and either the methods evaluate( n ) and branch( n , sink ) of a BBEvaluator, which have to be safe to call concurrently in a parallel search, or make_worker( i ), which returns the BBEvaluator of the worker i (e.g., one with its own copy of a model and of a solver).

Optionally, P may give hash( n ), which the distributed search uses to send n to its owner, and estimate( n ), the estimate of the best feasible value under n that orders the nodes with Selection::best_estimate.

template<class P>
concept HashedBranchAndBound

#include <PBeFS/bnb/BranchAndBound.h>

a B&B problem that gives a hash of its nodes

template<class P>
concept EstimatingBranchAndBound

#include <PBeFS/bnb/BranchAndBound.h>

a B&B problem that estimates the best feasible value under a node

Functions

template<BranchAndBound P>
BBSolution<typename P::node_type, bb_value_t<P>> PBeFS_di_unipi_it::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>> PBeFS_di_unipi_it::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

Types

using PBeFS_di_unipi_it::Evaluation = BasicEvaluation<>

the outcome of the evaluation of a node, with values of type double

template<class P>
using PBeFS_di_unipi_it::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 PBeFS_di_unipi_it::BBOptions = BasicBBOptions<>

the options of a B&B with values of type double

Enumerations

enum class PBeFS_di_unipi_it::Sense

the sense of the optimization

Values:

enumerator minimize

the least value is sought

enumerator maximize

the largest value is sought

enum class PBeFS_di_unipi_it::Selection

the order in which the open nodes are extracted

Values:

enumerator best_first

the least bound first

enumerator depth_first

the deepest node first

enumerator breadth_first

the shallowest node first, the oldest among those

enumerator best_estimate

the least estimate( n ) of the problem first

enumerator plunging

a dive into the children, then best-first

enum class PBeFS_di_unipi_it::BBStatus

how a B&B ended

Values:

enumerator optimal

the incumbent is optimal within the tolerance

enumerator infeasible

no feasible solution exists (nor was given)

enumerator node_limit

the limit on the evaluated nodes was reached first

enumerator time_limit

the time limit was reached first

enum class PBeFS_di_unipi_it::BBLeafKind

why a node is a leaf of the tree explored

Values:

enumerator open

left open by a limit

enumerator pruned

its bound cannot improve the incumbent

enumerator feasible

evaluated with a feasible value, and not branched

enumerator infeasible

found infeasible

Description of the header

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:

 1  procedure B&B(R)          ▷ the nodes to start from, {root} by default
 2     z ← the given incumbent, or ∞;  Q ← R;  d ← nil  ▷ d: the dive
 3     while Q ≠ ∅ or d ≠ nil do
 4        if the node or the time limit is reached then break
 5        βmin ← the least bound of Q and of d
 6        if PRUNABLE(βmin) then the nodes of Q and d are leaves;  break
 7        n ← d if d ≠ nil, else the first node of Q, removed;  d ← nil
 8        K ← PROCESS(n)
 9        if the selection is plunging and K ≠ ∅ then
10           k ← the node of K of least bound
11           βmin ← min(the least bound of Q, β(k))
12           if z = ∞ or β(k) ≤ βmin + γ (z − βmin) then d ← k, taken from K
13        push the nodes of K in Q
14     the nodes left in Q and d are leaves             ▷ open by a limit
15     return z, its node, and the bound min(z, least bound of the leaves)
16  procedure PROCESS(n)
17     if PRUNABLE(β(n)) then n is a leaf (pruned);  return ∅
18     cutoff(z);  (β', infeasible, v) ← evaluate(n)
19     if infeasible then n is a leaf (infeasible);  return ∅
20     β(n) ← max(β(n), β')
21     if v is given and v < z then z ← v;  n is the node of z
22     if PRUNABLE(β(n)) then n is a leaf (pruned or feasible);  return ∅
23     K ← ∅;  cutoff(z)
24     for each child m of n, with its estimate e, given by branch(n) do
25        β(m) ← max(β(n), e)
26        if PRUNABLE(β(m)) then m is a leaf (pruned)
27        else K ← K ∪ {m}
28     if n has no child then n is a leaf
29     return K
30  procedure PRUNABLE(β)
31     if z = ∞ then return β = ∞
32     return β ≥ z − max(τ_a, τ_r |z|)

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.

Author

Donato Meoli

Dipartimento di Informatica

Università di Pisa

Copyright

© by Donato Meoli