operations_research::KnapsackPropagator Class Reference

#include <knapsack_solver.h>

Inheritance diagram for operations_research::KnapsackPropagator:

Public Member Functions
	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)
virtual void	ComputeProfitBounds ()=0
virtual int	GetNextItemId () const =0
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
virtual void	InitPropagator ()=0
virtual bool	UpdatePropagator (bool revert, const KnapsackAssignment &assignment)=0
virtual void	CopyCurrentStateToSolutionPropagator (std::vector< bool > *solution) const =0
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

--— KnapsackPropagator --— KnapsackPropagator is the base class for modeling and propagating a constraint given an assignment.

When some work has to be done both by the base and the derived class, a protected pure virtual method ending by 'Propagator' is defined. For instance, 'Init' creates a vector of items, and then calls 'InitPropagator' to let the derived class perform its own initialization.

Definition at line 468 of file knapsack_solver.h.

Constructor & Destructor Documentation

KnapsackPropagator() [1/2]

operations_research::KnapsackPropagator::KnapsackPropagator ( const KnapsackState & state )

explicit

--— KnapsackPropagator --—

Definition at line 171 of file knapsack_solver.cc.

KnapsackPropagator() [2/2]

operations_research::KnapsackPropagator::KnapsackPropagator ( const KnapsackPropagator & )

delete

This type is neither copyable nor movable.

~KnapsackPropagator()

operations_research::KnapsackPropagator::~KnapsackPropagator ( )

virtual

Definition at line 178 of file knapsack_solver.cc.

Member Function Documentation

ComputeProfitBounds()

virtual void operations_research::KnapsackPropagator::ComputeProfitBounds ( )

pure virtual

ComputeProfitBounds should set 'profit_lower_bound_' and 'profit_upper_bound_' which are constraint specific.

Implemented in operations_research::KnapsackCapacityPropagator.

CopyCurrentStateToSolution()

void operations_research::KnapsackPropagator::CopyCurrentStateToSolution	(	bool	has_one_propagator,
		std::vector< bool > *	solution ) const

Copies the current state into 'solution'. All unbound items are set to false (i.e. not in the knapsack). When 'has_one_propagator' is true, CopyCurrentSolutionPropagator is called to have a better solution. When there is only one propagator there is no need to check the solution with other propagators, so the partial solution can be smartly completed.

Definition at line 205 of file knapsack_solver.cc.

CopyCurrentStateToSolutionPropagator()

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

protectedpure virtual

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.

Implemented in operations_research::KnapsackCapacityPropagator.

current_profit()

int64_t operations_research::KnapsackPropagator::current_profit ( ) const

inline

Definition at line 494 of file knapsack_solver.h.

GetNextItemId()

virtual int operations_research::KnapsackPropagator::GetNextItemId ( ) const

pure virtual

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

Implemented in operations_research::KnapsackCapacityPropagator.

Init()

void operations_research::KnapsackPropagator::Init	(	const std::vector< int64_t > &	profits,
		const std::vector< int64_t > &	weights )

Initializes data structure and then calls InitPropagator.

Definition at line 180 of file knapsack_solver.cc.

InitPropagator()

virtual void operations_research::KnapsackPropagator::InitPropagator ( )

protectedpure virtual

Initializes data structure. This method is called after initialization of KnapsackPropagator data structure.

Implemented in operations_research::KnapsackCapacityPropagator.

items()

const std::vector< KnapsackItemPtr > & operations_research::KnapsackPropagator::items ( ) const

inlineprotected

Definition at line 526 of file knapsack_solver.h.

operator=()

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

delete

profit_lower_bound()

int64_t operations_research::KnapsackPropagator::profit_lower_bound ( ) const

inline

Definition at line 495 of file knapsack_solver.h.

profit_upper_bound()

int64_t operations_research::KnapsackPropagator::profit_upper_bound ( ) const

inline

Definition at line 496 of file knapsack_solver.h.

set_profit_lower_bound()

void operations_research::KnapsackPropagator::set_profit_lower_bound ( int64_t profit )

inlineprotected

Definition at line 528 of file knapsack_solver.h.

set_profit_upper_bound()

void operations_research::KnapsackPropagator::set_profit_upper_bound ( int64_t profit )

inlineprotected

Definition at line 529 of file knapsack_solver.h.

state()

const KnapsackState & operations_research::KnapsackPropagator::state ( ) const

inlineprotected

Definition at line 525 of file knapsack_solver.h.

Update()

bool operations_research::KnapsackPropagator::Update	(	bool	revert,
		const KnapsackAssignment &	assignment )

Updates data structure and then calls UpdatePropagator. Returns false when failure.

Definition at line 193 of file knapsack_solver.cc.

UpdatePropagator()

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

protectedpure virtual

Updates internal data structure incrementally. This method is called after update of KnapsackPropagator data structure.

Implemented in operations_research::KnapsackCapacityPropagator.

---

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

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