BasicBBOptions< V > Struct Template Reference

the options of a B&B with values of type V More...

#include <PBeFS/bnb/BranchAndBound.h>

Public Attributes
Selection	selection = Selection::best_first
	the order of the nodes
V	abs_gap = V( 0 )
	the absolute tolerance on the gap
double	rel_gap = 0
	the relative tolerance on the gap
double	plunge_gap = 0.5
	how far from the best bound a dive goes
std::optional< V >	incumbent
	a known feasible value, if any
std::function< V(void) >	shared_incumbent
	a value that the search reads at each extraction and prunes by when it is better than its incumbent, e.g., the incumbent of other searches running at the same time; the Solution has only the feasible values that the search itself finds (or incumbent), so that it is infeasible when none of them is better than the values read, and its bound is still that of the subtrees searched
std::size_t	node_limit = 0
	evaluated nodes (0 = no limit)
double	time_limit = 0
	seconds (0 = no limit)
bool	keep_frontier = false
	keep the leaves of the tree explored
std::function< void(V) >	on_incumbent
	called with every new incumbent value (in a parallel search, by the worker that finds it, under a lock)

Detailed Description

template<class V = double>
struct PBeFS_di_unipi_it::BasicBBOptions< V >

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

A node is pruned when its bound cannot improve the incumbent \( z \) by more than the tolerance \( \max \{ \tau_a , \tau_r |z| \} \), \( \tau_a \) being abs_gap and \( \tau_r \) rel_gap, and the search ends when no open node can. With Selection::plunging, the best child of the node just branched is extracted next (a dive) if its bound is at most \( \underline{\beta} + \gamma ( z - \underline{\beta} ) \), \( \gamma \) being plunge_gap and \( \underline{\beta} \) the least open bound, and always while there is no incumbent. With keep_frontier, the Solution holds the leaves of the tree explored [see BBSolution], from which a later search can start again [see BranchAndBoundSearch::solve()].

Member Data Documentation

abs_gap

template<class V = double>

V abs_gap = V( 0 )

the absolute tolerance on the gap

incumbent

template<class V = double>

std::optional< V > incumbent

a known feasible value, if any

keep_frontier

template<class V = double>

bool keep_frontier = false

keep the leaves of the tree explored

node_limit

template<class V = double>

std::size_t node_limit = 0

evaluated nodes (0 = no limit)

on_incumbent

template<class V = double>

std::function< void( V ) > on_incumbent

called with every new incumbent value (in a parallel search, by the worker that finds it, under a lock)

plunge_gap

template<class V = double>

double plunge_gap = 0.5

how far from the best bound a dive goes

rel_gap

template<class V = double>

double rel_gap = 0

the relative tolerance on the gap

selection

template<class V = double>

Selection selection = Selection::best_first

the order of the nodes

shared_incumbent

template<class V = double>

std::function< V( void ) > shared_incumbent

a value that the search reads at each extraction and prunes by when it is better than its incumbent, e.g., the incumbent of other searches running at the same time; the Solution has only the feasible values that the search itself finds (or incumbent), so that it is infeasible when none of them is better than the values read, and its bound is still that of the subtrees searched

time_limit

template<class V = double>

double time_limit = 0

seconds (0 = no limit)

---

The documentation for this struct was generated from the following file:

• PBeFS/bnb/BranchAndBound.h