operations_research::KnapsackGenericSolver Class Reference

KnapsackGenericSolver KnapsackGenericSolver is the multi-dimensional knapsack solver class. More...

#include <knapsack_solver.h>

Inheritance diagram for operations_research::KnapsackGenericSolver:

List of all members.

Public Member Functions
	KnapsackGenericSolver (const string &solver_name)
	KnapsackGenericSolver.
virtual	~KnapsackGenericSolver ()
virtual void	Init (const std::vector< int64 > &profits, const std::vector< std::vector< int64 > > &weights, const std::vector< int64 > &capacities)
	Initializes the solver and enters the problem to be solved.
int	GetNumberOfItems () const
void	GetLowerAndUpperBoundWhenItem (int item_id, bool is_item_in, int64 *lower_bound, int64 *upper_bound)
	Gets the lower and upper bound when the item is in or out of the knapsack.
void	set_master_propagator_id (int master_propagator_id)
	Sets which propagator should be used to guide the search.
virtual int64	Solve ()
	Solves the problem and returns the profit of the optimal solution.
virtual bool	best_solution (int item_id) const
	Returns true if the item 'item_id' is packed in the optimal knapsack.

---

Detailed Description

KnapsackGenericSolver KnapsackGenericSolver is the multi-dimensional knapsack solver class.

In the current implementation, the next item to assign is given by the master propagator. Using SetMasterPropagator allows to change the default (propagator of the first dimension), and select another dimension when more constrained.

Todo:

TODO(user): In case of multi-dimensional knapsack problem, implement an aggregated propagator to combine all dimensions and give a better guide to select next item (see for instance Dobson's aggregated efficiency).

Definition at line 509 of file knapsack_solver.h.

---

Constructor & Destructor Documentation

operations_research::KnapsackGenericSolver::KnapsackGenericSolver

(

const string &

solver_name

)

[explicit]

KnapsackGenericSolver.

Definition at line 355 of file knapsack_solver.cc.

operations_research::KnapsackGenericSolver::~KnapsackGenericSolver

(

)

[virtual]

Definition at line 365 of file knapsack_solver.cc.

---

Member Function Documentation

void operations_research::KnapsackGenericSolver::Init	(	const std::vector< int64 > &	profits,
		const std::vector< std::vector< int64 > > &	weights,
		const std::vector< int64 > &	capacities
	)			[virtual]

Initializes the solver and enters the problem to be solved.

Implements operations_research::BaseKnapsackSolver.

Definition at line 369 of file knapsack_solver.cc.

int operations_research::KnapsackGenericSolver::GetNumberOfItems

(

)

const [inline]

Definition at line 518 of file knapsack_solver.h.

void operations_research::KnapsackGenericSolver::GetLowerAndUpperBoundWhenItem	(	int	item_id,
		bool	is_item_in,
		int64 *	lower_bound,
		int64 *	upper_bound
	)			[virtual]

Gets the lower and upper bound when the item is in or out of the knapsack.

BaseKnapsackSolver.

To ensure objects are correctly initialized, this method should not be called before Init.

Reimplemented from operations_research::BaseKnapsackSolver.

Definition at line 390 of file knapsack_solver.cc.

void operations_research::KnapsackGenericSolver::set_master_propagator_id

(

int

master_propagator_id

)

[inline]

Sets which propagator should be used to guide the search.

'master_propagator_id' should be in 0..p-1 with p the number of propagators.

Definition at line 527 of file knapsack_solver.h.

int64 operations_research::KnapsackGenericSolver::Solve

(

)

[virtual]

Solves the problem and returns the profit of the optimal solution.

Implements operations_research::BaseKnapsackSolver.

Definition at line 414 of file knapsack_solver.cc.

virtual bool operations_research::KnapsackGenericSolver::best_solution

(

int

item_id

)

const [inline, virtual]

Returns true if the item 'item_id' is packed in the optimal knapsack.

Implements operations_research::BaseKnapsackSolver.

Definition at line 534 of file knapsack_solver.h.

---

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

• or-tools/src/algorithms/knapsack_solver.h
• or-tools/src/algorithms/knapsack_solver.cc