operations_research::KnapsackCapacityPropagator Class Reference

#include <knapsack_solver.h>

Inheritance diagram for operations_research::KnapsackCapacityPropagator:

Public Member Functions
	KnapsackCapacityPropagator (const KnapsackState &state, int64_t capacity)
	--— KnapsackCapacityPropagator --—
	KnapsackCapacityPropagator (const KnapsackCapacityPropagator &)=delete
	This type is neither copyable nor movable.
KnapsackCapacityPropagator &	operator= (const KnapsackCapacityPropagator &)=delete
	~KnapsackCapacityPropagator () override
void	ComputeProfitBounds () override
int	GetNextItemId () const override
Public Member Functions inherited from operations_research::KnapsackPropagator
	KnapsackPropagator (const KnapsackState &state)
	--— KnapsackPropagator --—
	KnapsackPropagator (const KnapsackPropagator &)=delete
	This type is neither copyable nor movable.
KnapsackPropagator &	operator= (const KnapsackPropagator &)=delete
virtual	~KnapsackPropagator ()
void	Init (const std::vector< int64_t > &profits, const std::vector< int64_t > &weights)
	Initializes data structure and then calls InitPropagator.
bool	Update (bool revert, const KnapsackAssignment &assignment)
int64_t	current_profit () const
int64_t	profit_lower_bound () const
int64_t	profit_upper_bound () const
void	CopyCurrentStateToSolution (bool has_one_propagator, std::vector< bool > *solution) const

Protected Member Functions
void	InitPropagator () override
bool	UpdatePropagator (bool revert, const KnapsackAssignment &assignment) override
	Returns false when the propagator fails.
void	CopyCurrentStateToSolutionPropagator (std::vector< bool > *solution) const override
Protected Member Functions inherited from operations_research::KnapsackPropagator
const KnapsackState &	state () const
const std::vector< KnapsackItemPtr > &	items () const
void	set_profit_lower_bound (int64_t profit)
void	set_profit_upper_bound (int64_t profit)

Detailed Description

--— KnapsackCapacityPropagator --— KnapsackCapacityPropagator is a KnapsackPropagator used to enforce a capacity constraint. As a KnapsackPropagator is supposed to compute profit lower and upper bounds, and get the next item to select, it can be seen as a 0-1 Knapsack solver. The most efficient way to compute the upper bound is to iterate on items in profit-per-unit-weight decreasing order. The break item is commonly defined as the first item for which there is not enough remaining capacity. Selecting this break item as the next-item-to-assign usually gives the best results (see Greenberg & Hegerich).

This is exactly what is implemented in this class.

When there is only one propagator, it is possible to compute a better profit lower bound almost for free. During the scan to find the break element all unbound items are added just as if they were part of the current solution. This is used in both ComputeProfitBounds and CopyCurrentSolutionPropagator. For incrementality reasons, the ith item should be accessible in O(1). That's the reason why the item vector has to be duplicated 'sorted_items_'.

Definition at line 559 of file knapsack_solver.h.

Constructor & Destructor Documentation

KnapsackCapacityPropagator() [1/2]

operations_research::KnapsackCapacityPropagator::KnapsackCapacityPropagator	(	const KnapsackState &	state,
		int64_t	capacity )

--— KnapsackCapacityPropagator --—

Definition at line 218 of file knapsack_solver.cc.

KnapsackCapacityPropagator() [2/2]

operations_research::KnapsackCapacityPropagator::KnapsackCapacityPropagator ( const KnapsackCapacityPropagator & )

delete

This type is neither copyable nor movable.

~KnapsackCapacityPropagator()

operations_research::KnapsackCapacityPropagator::~KnapsackCapacityPropagator ( )

overridedefault

Member Function Documentation

ComputeProfitBounds()

void operations_research::KnapsackCapacityPropagator::ComputeProfitBounds ( )

overridevirtual

Todo

(user): Make it more incremental, by saving the break item in a search node for instance.

Implements operations_research::KnapsackPropagator.

Definition at line 231 of file knapsack_solver.cc.

CopyCurrentStateToSolutionPropagator()

void operations_research::KnapsackCapacityPropagator::CopyCurrentStateToSolutionPropagator ( std::vector< bool > * solution ) const

overrideprotectedvirtual

Copies the current state into 'solution'. Only unbound items have to be copied as CopyCurrentSolution was already called with current state. This method is useful when a propagator is able to find a better solution than the blind instantiation to false of unbound items.

Implements operations_research::KnapsackPropagator.

Definition at line 291 of file knapsack_solver.cc.

GetNextItemId()

int operations_research::KnapsackCapacityPropagator::GetNextItemId ( ) const

inlineoverridevirtual

Returns the id of next item to assign. Returns kNoSelection when all items are bound.

Implements operations_research::KnapsackPropagator.

Definition at line 572 of file knapsack_solver.h.

InitPropagator()

void operations_research::KnapsackCapacityPropagator::InitPropagator ( )

overrideprotectedvirtual

Initializes KnapsackCapacityPropagator (e.g., sort items in decreasing order).

Implements operations_research::KnapsackPropagator.

Definition at line 262 of file knapsack_solver.cc.

operator=()

KnapsackCapacityPropagator & operations_research::KnapsackCapacityPropagator::operator= ( const KnapsackCapacityPropagator & )

delete

UpdatePropagator()

bool operations_research::KnapsackCapacityPropagator::UpdatePropagator ( bool revert, const KnapsackAssignment & assignment )

overrideprotectedvirtual

Returns false when the propagator fails.

Updates internal data structure incrementally (i.e., 'consumed_capacity_') to avoid a O(number_of_items) scan.

Implements operations_research::KnapsackPropagator.

Definition at line 276 of file knapsack_solver.cc.

---

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

• ortools/algorithms/knapsack_solver.h
• ortools/algorithms/knapsack_solver.cc