BBQueue

Declared in bnb/BranchAndBound.h; the same class on the site of Doxygen.

template<class Node, class V = double>
class BBQueue

the open nodes of a B&B, ordered by a key

The nodes are kept in slots with a free list, since a node is destroyed when it is branched, and the indexed heap pair of ADS on the slots gives the next one, the least key first and, among equal keys, the last pushed (the first pushed with Selection::breadth_first), and the least bound of the open nodes, which the termination test needs when the key of the selection is not the bound. The heaps grow by doubling with the slots.

Public Functions

inline explicit BBQueue(Selection s = Selection::best_first)

constructor, taking the selection the keys are made by

inline void push(Node &&n, V bound, unsigned depth, V key)

adds a node with its bound, its depth and its key

inline const Item &top(void) const

the next node, which stays in the queue (there must be one)

inline Item pop(void)

removes and returns the next node

inline V best_bound(void) const

the least bound of the open nodes ( \( +\infty \) if there is none)

inline std::size_t clear(void)

removes all the nodes, returning how many there were

template<class F>
inline std::size_t drain(F &&f)

removes all the nodes, giving each to f( item ), and returns how many there were

inline bool empty(void) const noexcept

true if there is no open node

inline std::size_t size(void) const noexcept

the number of open nodes

struct Item

an open node

Public Members

Node node

the node

V bound

its bound, in the minimization

unsigned depth

its depth in the tree