operations_research::KnapsackGenericSolver Class Reference

#include <knapsack_solver.h>

Inheritance diagram for operations_research::KnapsackGenericSolver:

Public Member Functions
	KnapsackGenericSolver (const std::string &solver_name)
	--— KnapsackGenericSolver --—
	KnapsackGenericSolver (const KnapsackGenericSolver &)=delete
	This type is neither copyable nor movable.
KnapsackGenericSolver &	operator= (const KnapsackGenericSolver &)=delete
	~KnapsackGenericSolver () override
void	Init (const std::vector< int64_t > &profits, const std::vector< std::vector< int64_t > > &weights, const std::vector< int64_t > &capacities) override
	Initializes the solver and enters the problem to be solved.
int	GetNumberOfItems () const
void	GetLowerAndUpperBoundWhenItem (int item_id, bool is_item_in, int64_t *lower_bound, int64_t *upper_bound) override
	--— BaseKnapsackSolver --—
void	set_primary_propagator_id (int primary_propagator_id)
int64_t	Solve (TimeLimit *time_limit, double time_limit_in_seconds, bool *is_solution_optimal) override
	Solves the problem and returns the profit of the optimal solution.
bool	best_solution (int item_id) const override
	Returns true if the item 'item_id' is packed in the optimal knapsack.
Public Member Functions inherited from operations_research::BaseKnapsackSolver
	BaseKnapsackSolver (absl::string_view solver_name)
virtual	~BaseKnapsackSolver ()=default
virtual std::string	GetName () const

Detailed Description

--— KnapsackGenericSolver --— KnapsackGenericSolver is the multi-dimensional knapsack solver class. In the current implementation, the next item to assign is given by the primary propagator. Using SetPrimaryPropagator allows changing the default (propagator of the first dimension), and selecting another dimension when more constrained.

Todo

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

Definition at line 646 of file knapsack_solver.h.

Constructor & Destructor Documentation

KnapsackGenericSolver() [1/2]

operations_research::KnapsackGenericSolver::KnapsackGenericSolver ( const std::string & solver_name )

explicit

--— KnapsackGenericSolver --—

Definition at line 346 of file knapsack_solver.cc.

KnapsackGenericSolver() [2/2]

operations_research::KnapsackGenericSolver::KnapsackGenericSolver ( const KnapsackGenericSolver & )

delete

This type is neither copyable nor movable.

~KnapsackGenericSolver()

operations_research::KnapsackGenericSolver::~KnapsackGenericSolver ( )

override

Definition at line 355 of file knapsack_solver.cc.

Member Function Documentation

best_solution()

bool operations_research::KnapsackGenericSolver::best_solution ( int item_id ) const

inlineoverridevirtual

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

Implements operations_research::BaseKnapsackSolver.

Definition at line 678 of file knapsack_solver.h.

GetLowerAndUpperBoundWhenItem()

void operations_research::KnapsackGenericSolver::GetLowerAndUpperBoundWhenItem ( int item_id, bool is_item_in, int64_t * lower_bound, int64_t * upper_bound )

overridevirtual

--— BaseKnapsackSolver --—

Gets the lower and upper bound when the item is in or out of the knapsack. To ensure objects are correctly initialized, this method should not be called before Init.

Reimplemented from operations_research::BaseKnapsackSolver.

Definition at line 379 of file knapsack_solver.cc.

GetNumberOfItems()

int operations_research::KnapsackGenericSolver::GetNumberOfItems ( ) const

inline

Definition at line 662 of file knapsack_solver.h.

Init()

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

overridevirtual

Initializes the solver and enters the problem to be solved.

Implements operations_research::BaseKnapsackSolver.

Definition at line 357 of file knapsack_solver.cc.

operator=()

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

delete

set_primary_propagator_id()

void operations_research::KnapsackGenericSolver::set_primary_propagator_id ( int primary_propagator_id )

inline

Sets which propagator should be used to guide the search. 'primary_propagator_id' should be in 0..p-1 with p the number of propagators.

Definition at line 670 of file knapsack_solver.h.

Solve()

int64_t operations_research::KnapsackGenericSolver::Solve ( TimeLimit * time_limit, double time_limit_in_seconds, bool * is_solution_optimal )

overridevirtual

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

Implements operations_research::BaseKnapsackSolver.

Definition at line 403 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