pykp.solvers.

branch_and_bound

pykp.solvers.branch_and_bound(items: list[Item], capacity: float, n=1) → Solution

Solves the knapsack problem using the branch-and-bound algorithm.

Parameters:

items: list[Item]

Items that can be included in the knapsack.

capacity: float

Maximum weight capacity of the knapsack.

Returns:

SolutionSolution

If n = 1, the optimal arrangements of items in the knapsack. If n > 1, all arrangements that yield the n highest possible values in the knapsack.

Other Parameters:

n: int, optional

The n-best solutions to return. If set to 1, the solver returns all solutions that achieve the distinct optimal value. If set to n, the solver returns the solutions that achieve the n-highest possible values. Defaults to 1.

Examples

Solve a knapsack problem using the branch-and-bound algorithm

>>> from pykp.knapsack import Item
>>> from pykp import solvers
>>>
>>> items = [
...     Item(value=10, weight=5),
...     Item(value=15, weight=10),
...     Item(value=5, weight=5),
>>> ]
>>> capacity = 15
>>> solvers.branch_and_bound(items, capacity)
[(v: 25, w: 15, s: 6)]

Alternatively, construct an instance of the Knapsack class and call the solve method with “branch_and_bound” as the method argument

>>> from pykp.knapsack import Item
>>> from pykp.knapsack import Knapsack
>>>
>>> items = [
...     Item(value=10, weight=5),
...     Item(value=15, weight=10),
...     Item(value=5, weight=5),
... ]
>>> capacity = 15
>>> instance = Knapsack(items=items, capacity=capacity)
>>> instance.solve(method="branch_and_bound")
>>> instance.optimal_nodes
[(v: 25, w: 15, s: 6)]

If there are multiple solutions with the same optimal value, all will be returned.

>>> from pykp.knapsack import Item
>>> from pykp.knapsack import Knapsack
>>>
>>> items = [
...     Item(value=10, weight=5),
...     Item(value=15, weight=10),
...     Item(value=4, weight=2),
...     Item(value=6, weight=3),
... ]
>>> capacity = 15
>>> instance = Knapsack(items=items, capacity=capacity)
>>> instance.solve(method="branch_and_bound")
>>> instance.optimal_nodes
[(v: 25, w: 15, s: 9), (v: 25, w: 15, s: 7)]

Use the optional n argument to return the n-best solutions found by the solver.

>>> from pykp.knapsack import Item
>>> from pykp.knapsack import Knapsack
>>> from pykp import solvers
>>>
>>> items = [
...     Item(value=10, weight=5),
...     Item(value=15, weight=10),
...     Item(value=4, weight=2),
...     Item(value=6, weight=3),
... ]
>>> capacity = 15
>>> solvers.branch_and_bound(items, capacity, n=3)
[(v: 25, w: 15, s: 9), (v: 25, w: 15, s: 7), (v: 21, w: 13, s: 3)]

Note

The n argument is on solution values, not the number of solutions. If n is set to 1, the solver returns all solutions that achieve the distinct optimal value. More than one solution may be returned if there are multiple solutions with the same optimal value. Similarly, if n is set to n, the solver returns all solutions that achieve the n-highest possible values.