KnapsackDomain Class Reference

Collaboration diagram for KnapsackDomain:

Classes
struct	Move

Public Types
using	State = KnapsackState
using	Objective = double

Public Member Functions
	KnapsackDomain (const Array< Item > &items, double capacity)
bool	is_complete (const State &s) const noexcept
	True when all items have been decided.
Objective	objective_value (const State &s) const noexcept
	Objective value for a complete assignment.
Objective	bound (const State &s) const noexcept
	Greedy fractional upper bound on the remaining items.
void	apply (State &s, const Move &m) const noexcept
void	undo (State &s, const Move &m) const noexcept
bool	is_feasible (const State &s) const noexcept
template<typename Visitor >
bool	for_each_successor (const State &s, Visitor visit) const

Private Attributes
Array< Item >	items_
double	capacity_

Detailed Description

Definition at line 82 of file branch_and_bound_df_vs_bf_example.cc.

Member Typedef Documentation

Objective

using KnapsackDomain::Objective = double

Definition at line 91 of file branch_and_bound_df_vs_bf_example.cc.

State

using KnapsackDomain::State = KnapsackState

Definition at line 90 of file branch_and_bound_df_vs_bf_example.cc.

Constructor & Destructor Documentation

KnapsackDomain()

KnapsackDomain::KnapsackDomain ( const Array< Item > &  items, double  capacity  )

inlineexplicit

Definition at line 93 of file branch_and_bound_df_vs_bf_example.cc.

References Aleph::divide_and_conquer_partition_dp(), items_, and Aleph::Array< T >::size().

Member Function Documentation

apply()

void KnapsackDomain::apply ( State &  s, const Move &  m  ) const

inlinenoexcept

Definition at line 150 of file branch_and_bound_df_vs_bf_example.cc.

References items_, m, Item::value, and Item::weight.

bound()

Objective KnapsackDomain::bound ( const State &  s ) const

inlinenoexcept

Greedy fractional upper bound on the remaining items.

Takes remaining items in value-density order and fills the remaining capacity fractionally. This is an admissible upper bound for B&B.

Definition at line 126 of file branch_and_bound_df_vs_bf_example.cc.

References Aleph::and, capacity_, Aleph::divide_and_conquer_partition_dp(), items_, Aleph::Array< T >::size(), Item::value, and Item::weight.

for_each_successor()

template<typename Visitor >

bool KnapsackDomain::for_each_successor ( const State &  s, Visitor  visit  ) const

inline

Definition at line 178 of file branch_and_bound_df_vs_bf_example.cc.

References capacity_, Aleph::divide_and_conquer_partition_dp(), items_, KnapsackState::next_item, Aleph::Array< T >::size(), Item::weight, and KnapsackState::weight_so_far.

is_complete()

bool KnapsackDomain::is_complete ( const State &  s ) const

inlinenoexcept

True when all items have been decided.

Definition at line 110 of file branch_and_bound_df_vs_bf_example.cc.

References items_, and Aleph::Array< T >::size().

is_feasible()

bool KnapsackDomain::is_feasible ( const State &  s ) const

inlinenoexcept

Definition at line 172 of file branch_and_bound_df_vs_bf_example.cc.

References capacity_.

objective_value()

Objective KnapsackDomain::objective_value ( const State &  s ) const

inlinenoexcept

Objective value for a complete assignment.

Definition at line 116 of file branch_and_bound_df_vs_bf_example.cc.

undo()

void KnapsackDomain::undo ( State &  s, const Move &  m  ) const

inlinenoexcept

Definition at line 161 of file branch_and_bound_df_vs_bf_example.cc.

References items_, m, Item::value, and Item::weight.

Member Data Documentation

capacity_

double KnapsackDomain::capacity_

private

Definition at line 196 of file branch_and_bound_df_vs_bf_example.cc.

Referenced by bound(), for_each_successor(), and is_feasible().

items_

Array<Item> KnapsackDomain::items_

private

Definition at line 195 of file branch_and_bound_df_vs_bf_example.cc.

Referenced by KnapsackDomain(), apply(), bound(), for_each_successor(), is_complete(), and undo().

---

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

• Examples/branch_and_bound_df_vs_bf_example.cc