BasicKnapsack< V > Struct Template Reference

a 0-1 knapsack, its items sorted by decreasing ratio of profit to weight More...

#include <PBeFS/bnb/Knapsack.h>

Classes
struct	node_type

Public Types
using	value_type = V
	the type of the values

Public Member Functions
node_type	root (void) const
long	greedy (const node_type &n) const
BasicEvaluation< V >	evaluate (node_type &n) const
template<class F>
void	branch (const node_type &n, F &&f) const
std::uint64_t	hash (const node_type &n) const
V	estimate (const node_type &n) const
void	serialize (const node_type &n, std::vector< char > &out) const
node_type	deserialize (const char *&in) const
long	optimum (void) const
bool	check (const node_type &n, V v) const

Static Public Member Functions
static BasicKnapsack	random (int cls, std::size_t n, long r, std::uint64_t seed)

Public Attributes
std::vector< long >	p
	the profits
std::vector< long >	w
	the weights
long	cap = 0
	the capacity
bool	explicit_children = false
	own bounds, infeasible children

Static Public Attributes
static constexpr Sense	sense = Sense::maximize

Detailed Description

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

a 0-1 knapsack, its items sorted by decreasing ratio of profit to weight

A node fixes the first \( k \) items, its bound is the one of the fractional relaxation of Dantzig, the greedy completion of the node is its feasible value, and it is branched on the item \( k \); a node over the capacity is infeasible. The children get the bound of their parent, and the item is taken only if it fits; with explicit_children, they get their own bound, and the item is taken anyway, giving a child that is found infeasible when it is evaluated if it does not fit. With an integer type V the bound is rounded down, which is still a bound since the profits are integer, so that a node whose bound rounds down to the incumbent is pruned. The nodes travel between the processes of MPI by serialize() and deserialize().

Member Typedef Documentation

value_type

template<class V = double>

using value_type = V

the type of the values

Member Function Documentation

branch()

template<class V = double>

template<class F>

void branch ( const node_type & n, F && f ) const

inline

check()

template<class V = double>

bool check ( const node_type & n, V v ) const

inline

deserialize()

template<class V = double>

node_type deserialize ( const char *& in ) const

inline

estimate()

template<class V = double>

V estimate ( const node_type & n ) const

inline

evaluate()

template<class V = double>

BasicEvaluation< V > evaluate ( node_type & n ) const

inline

greedy()

template<class V = double>

long greedy ( const node_type & n ) const

inline

hash()

template<class V = double>

std::uint64_t hash ( const node_type & n ) const

inline

optimum()

template<class V = double>

long optimum ( void ) const

inline

random()

template<class V = double>

BasicKnapsack random ( int cls, std::size_t n, long r, std::uint64_t seed )

inlinestatic

root()

template<class V = double>

node_type root ( void ) const

inline

serialize()

template<class V = double>

void serialize ( const node_type & n, std::vector< char > & out ) const

inline

Member Data Documentation

cap

template<class V = double>

long cap = 0

the capacity

explicit_children

template<class V = double>

bool explicit_children = false

own bounds, infeasible children

p

template<class V = double>

std::vector< long > p

the profits

sense

template<class V = double>

Sense sense = Sense::maximize

staticconstexpr

w

template<class V = double>

std::vector< long > w

the weights

---

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

• PBeFS/bnb/Knapsack.h