com.google.ortools.algorithms

Class KnapsackSolver

java.lang.Object

com.google.ortools.algorithms.KnapsackSolver

public class KnapsackSolver
extends java.lang.Object

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();

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	KnapsackSolver.SolverType Enum controlling which underlying algorithm is used.

Field Summary

Fields

Modifier and Type	Field and Description
protected boolean	swigCMemOwn

Constructor Summary

Constructors

Modifier	Constructor and Description
	KnapsackSolver(KnapsackSolver.SolverType solver_type, java.lang.String solver_name)
protected	KnapsackSolver(long cPtr, boolean cMemoryOwn)
	KnapsackSolver(java.lang.String solver_name)

Method Summary

Modifier and Type	Method and Description
boolean	bestSolutionContains(int item_id) Returns true if the item 'item_id' is packed in the optimal knapsack.
void	delete()
protected void	finalize()
protected static long	getCPtr(KnapsackSolver obj)
java.lang.String	getName()
void	init(long[] profits, long[][] weights, long[] capacities) Initializes the solver and enters the problem to be solved.
boolean	isSolutionOptimal() Returns true if the solution was proven optimal.
void	setTimeLimit(double time_limit_seconds) Time limit in seconds.
void	setUseReduction(boolean use_reduction)
long	solve() Solves the problem and returns the profit of the optimal solution.
protected static long	swigRelease(KnapsackSolver obj)
boolean	useReduction()

Methods inherited from class java.lang.Object

clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

swigCMemOwn

protected transient boolean swigCMemOwn

Constructor Detail

KnapsackSolver

protected KnapsackSolver(long cPtr,
                         boolean cMemoryOwn)

KnapsackSolver

public KnapsackSolver(java.lang.String solver_name)

KnapsackSolver

public KnapsackSolver(KnapsackSolver.SolverType solver_type,
                      java.lang.String solver_name)

Method Detail

getCPtr

protected static long getCPtr(KnapsackSolver obj)

swigRelease

protected static long swigRelease(KnapsackSolver obj)

finalize

protected void finalize()

Overrides:

finalize in class java.lang.Object

delete

public void delete()

init

public void init(long[] profits,
                 long[][] weights,
                 long[] capacities)

Initializes the solver and enters the problem to be solved.

solve

public long solve()

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

bestSolutionContains

public boolean bestSolutionContains(int item_id)

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

isSolutionOptimal

public boolean isSolutionOptimal()

Returns true if the solution was proven optimal.

getName

public java.lang.String getName()

useReduction

public boolean useReduction()

setUseReduction

public void setUseReduction(boolean use_reduction)

setTimeLimit

public void setTimeLimit(double time_limit_seconds)

Time limit in seconds.

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