operations_research::KnapsackSolver Class Reference

#include <knapsack_solver.h>

Public Types
enum	SolverType {   KNAPSACK_BRUTE_FORCE_SOLVER = 0 , KNAPSACK_64ITEMS_SOLVER = 1 , KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER = 2 , KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER = 3 ,   KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER = 5 , KNAPSACK_MULTIDIMENSION_SCIP_MIP_SOLVER = 6 , KNAPSACK_MULTIDIMENSION_XPRESS_MIP_SOLVER = 7 , KNAPSACK_MULTIDIMENSION_CPLEX_MIP_SOLVER = 8 ,   KNAPSACK_DIVIDE_AND_CONQUER_SOLVER = 9 , KNAPSACK_MULTIDIMENSION_CP_SAT_SOLVER = 10 }

Public Member Functions
	KnapsackSolver (const std::string &solver_name)
	--— KnapsackSolver --—
	KnapsackSolver (SolverType solver_type, const std::string &solver_name)
	KnapsackSolver (const KnapsackSolver &)=delete
	This type is neither copyable nor movable.
KnapsackSolver &	operator= (const KnapsackSolver &)=delete
virtual	~KnapsackSolver ()
void	Init (const std::vector< int64_t > &profits, const std::vector< std::vector< int64_t > > &weights, const std::vector< int64_t > &capacities)
int64_t	Solve ()
bool	BestSolutionContains (int item_id) const
bool	IsSolutionOptimal () const
std::string	GetName () const
bool	use_reduction () const
void	set_use_reduction (bool use_reduction)
void	set_time_limit (double time_limit_seconds)

Detailed Description

This library solves knapsack problems.

Problems the library solves include:

• 0-1 knapsack problems,
• Multi-dimensional knapsack problems,

Given n items, each with a profit and a weight, given a knapsack of capacity c, the goal is to find a subset of items which fits inside c and maximizes the total profit. The knapsack problem can easily be extended from 1 to d dimensions. As an example, this can be useful to constrain the maximum number of items inside the knapsack. Without loss of generality, profits and weights are assumed to be positive.

From a mathematical point of view, the multi-dimensional knapsack problem can be modeled by d linear constraints:

ForEach(j:1..d)(Sum(i:1..n)(weight_ij * item_i) <= c_j
    where item_i is a 0-1 integer variable.

Then the goal is to maximize:

Sum(i:1..n)(profit_i * item_i).

There are several ways to solve knapsack problems. One of the most efficient is based on dynamic programming (mainly when weights, profits and dimensions are small, and the algorithm runs in pseudo polynomial time). Unfortunately, when adding conflict constraints the problem becomes strongly NP-hard, i.e. there is no pseudo-polynomial algorithm to solve it. That's the reason why the most of the following code is based on branch and bound search.

For instance to solve a 2-dimensional knapsack problem with 9 items, one just has to feed a profit vector with the 9 profits, a vector of 2 vectors for weights, and a vector of capacities. E.g.:

Python:

profits = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
weights = [ [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
            [ 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
          ]
capacities = [ 34, 4 ]
 
solver = knapsack_solver.KnapsackSolver(
    knapsack_solver.SolverType
        .KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
    'Multi-dimensional solver')
solver.init(profits, weights, capacities)
profit = solver.solve()

C++:

const std::vector<int64_t> profits = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
const std::vector<std::vector<int64_t>> weights =
    { { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
      { 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
const std::vector<int64_t> capacities = { 34, 4 };
 
KnapsackSolver solver(
    KnapsackSolver::KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
    "Multi-dimensional solver");
solver.Init(profits, weights, capacities);
const int64_t profit = solver.Solve();

Java:

final long[] profits = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
final long[][] weights = { { 1, 2, 3, 4, 5, 6, 7, 8, 9 },
       { 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
final long[] capacities = { 34, 4 };
 
KnapsackSolver solver = new KnapsackSolver(
    KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
    "Multi-dimensional solver");
solver.init(profits, weights, capacities);
final long profit = solver.solve();

Definition at line 112 of file knapsack_solver.h.

Member Enumeration Documentation

SolverType

enum operations_research::KnapsackSolver::SolverType

Enum controlling which underlying algorithm is used.

This enum is passed to the constructor of the KnapsackSolver object. It selects which solving method will be used.

Enumerator
KNAPSACK_BRUTE_FORCE_SOLVER	Brute force method. Limited to 30 items and one dimension, this solver uses a brute force algorithm, ie. explores all possible states. Experiments show competitive performance for instances with less than 15 items.
KNAPSACK_64ITEMS_SOLVER	Optimized method for single dimension small problems Limited to 64 items and one dimension, this solver uses a branch & bound algorithm. This solver is about 4 times faster than KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER.
KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER	Dynamic Programming approach for single dimension problems Limited to one dimension, this solver is based on a dynamic programming algorithm. The time and space complexity is O(capacity * number_of_items).
KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER	CBC Based Solver This solver can deal with both large number of items and several dimensions. This solver is based on Integer Programming solver CBC.
KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER	Generic Solver. This solver can deal with both large number of items and several dimensions. This solver is based on branch and bound.
KNAPSACK_MULTIDIMENSION_SCIP_MIP_SOLVER	SCIP based solver This solver can deal with both large number of items and several dimensions. This solver is based on Integer Programming solver SCIP.
KNAPSACK_MULTIDIMENSION_XPRESS_MIP_SOLVER	XPRESS based solver This solver can deal with both large number of items and several dimensions. This solver is based on Integer Programming solver XPRESS.
KNAPSACK_MULTIDIMENSION_CPLEX_MIP_SOLVER	CPLEX based solver This solver can deal with both large number of items and several dimensions. This solver is based on Integer Programming solver CPLEX.
KNAPSACK_DIVIDE_AND_CONQUER_SOLVER	Divide and Conquer approach for single dimension problems Limited to one dimension, this solver is based on a divide and conquer technique and is suitable for larger problems than Dynamic Programming Solver. The time complexity is O(capacity * number_of_items) and the space complexity is O(capacity + number_of_items).
KNAPSACK_MULTIDIMENSION_CP_SAT_SOLVER	CP-SAT based solver This solver can deal with both large number of items and several dimensions. This solver is based on the CP-SAT solver

Definition at line 119 of file knapsack_solver.h.

Constructor & Destructor Documentation

KnapsackSolver() [1/3]

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

explicit

--— KnapsackSolver --—

Definition at line 1384 of file knapsack_solver.cc.

KnapsackSolver() [2/3]

operations_research::KnapsackSolver::KnapsackSolver	(	SolverType	solver_type,
		const std::string &	solver_name )

Definition at line 1388 of file knapsack_solver.cc.

KnapsackSolver() [3/3]

operations_research::KnapsackSolver::KnapsackSolver ( const KnapsackSolver & )

delete

This type is neither copyable nor movable.

~KnapsackSolver()

operations_research::KnapsackSolver::~KnapsackSolver ( )

virtualdefault

Member Function Documentation

BestSolutionContains()

bool operations_research::KnapsackSolver::BestSolutionContains

(

int

item_id

)

const

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

Definition at line 1640 of file knapsack_solver.cc.

GetName()

std::string operations_research::KnapsackSolver::GetName

(

)

const

Definition at line 1648 of file knapsack_solver.cc.

Init()

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

Initializes the solver and enters the problem to be solved.

Definition at line 1448 of file knapsack_solver.cc.

IsSolutionOptimal()

bool operations_research::KnapsackSolver::IsSolutionOptimal ( ) const

inline

Returns true if the solution was proven optimal.

Definition at line 232 of file knapsack_solver.h.

operator=()

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

delete

set_time_limit()

void operations_research::KnapsackSolver::set_time_limit ( double time_limit_seconds )

inline

Time limit in seconds.

When a finite time limit is set the solution obtained might not be optimal if the limit is reached.

Definition at line 243 of file knapsack_solver.h.

set_use_reduction()

void operations_research::KnapsackSolver::set_use_reduction ( bool use_reduction )

inline

Definition at line 236 of file knapsack_solver.h.

Solve()

int64_t operations_research::KnapsackSolver::Solve

(

)

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

Definition at line 1632 of file knapsack_solver.cc.

use_reduction()

bool operations_research::KnapsackSolver::use_reduction ( ) const

inline

Definition at line 235 of file knapsack_solver.h.

---

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

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