BasicKnapsack

Declared in bnb/Knapsack.h; the same struct on the site of Doxygen.

template<class V = double> struct BasicKnapsack

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().

Public Types

using value_type = V : the type of the values

Public Functions

inline node_type root(void) const

inline long greedy(const node_type &n) const

inline BasicEvaluation<V> evaluate(node_type &n) const

template<class F> inline void branch(const node_type &n, F &&f) const

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

inline V estimate(const node_type &n) const

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

inline node_type deserialize(const char *&in) const

inline long optimum(void) const

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

Public Members

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

Public Static Functions

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

Public Static Attributes

static constexpr Sense sense = Sense::maximize 

struct node_type

Public Members

std::size_t k = 0: the items fixed

long weight = 0: the weight of those taken

long profit = 0: their profit

std::vector<char> x: the items taken