Breadth-first branch and bound in Python
Branch and bound that expands the tree level by level using a FIFO queue of live nodes.
- File
breadth_first_branch_and_bound.py, 85 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/breadth-first-branch-and-bound/. The authors are listed in prov/Z9RZB6.jsonl.
from collections import deque
from collections.abc import Callable, Iterable, Sequence
from typing import TypeVar
N = TypeVar("N")
def breadth_first_branch_and_bound(
root: N,
children: Callable[[N], Iterable[N]],
upper_bound: Callable[[N], float],
is_leaf: Callable[[N], bool],
value: Callable[[N], float],
stats: dict[str, int] | None = None,
) -> tuple[float, N | None]:
"""Maximise value over the leaves of the tree below root.
children(n) yields the feasible children of an inner node in the order
to try them. upper_bound(n) must be at least value(x) for every leaf x
below n. Returns (best value, best leaf), or (-inf, None) if the tree has
no leaf. Live nodes wait in a FIFO queue, so the tree is expanded level
by level.
"""
if stats is None:
stats = {}
stats.update(expanded=0, generated=1, max_live=1)
z = float("-inf") # @line L1
best: N | None = None # @line L1
queue: deque[N] = deque([root]) # @line L2
while queue: # @line L3
node = queue.popleft() # @line L4
if upper_bound(node) <= z: # @line L5
continue
if is_leaf(node): # @line L6
v = value(node)
if v > z: # @line L7
z, best = v, node
continue # @line L8
stats["expanded"] += 1
kept = [c for c in children(node) if upper_bound(c) > z] # @line L9 @line L10
stats["generated"] += len(kept)
queue.extend(kept) # @line L10
stats["max_live"] = max(stats["max_live"], len(queue))
return z, best # @line L11
Item = tuple[float, float] # (value, weight)
KNode = tuple[int, float, float, tuple[int, ...]] # (level, weight, value, taken)
def knapsack(values: Sequence[float], weights: Sequence[float], capacity: float, stats: dict[str, int] | None = None) -> tuple[float, list[int]]:
"""0-1 knapsack by breadth-first branch and bound with the fractional bound.
Returns the best value and the sorted list of chosen item indices.
Items with weight 0 are allowed; weights and values must be nonnegative.
"""
n = len(values)
order = sorted(range(n), key=lambda i: (-(values[i] / weights[i]) if weights[i] > 0 else float("-inf"), i))
def ub(node: KNode) -> float:
k, w, v, _ = node
room = capacity - w
for j in order[k:]:
if weights[j] <= room:
room -= weights[j]
v += values[j]
else:
return v + values[j] * room / weights[j]
return v
def kids(node: KNode) -> list[KNode]:
k, w, v, taken = node
j = order[k]
out: list[KNode] = []
if w + weights[j] <= capacity:
out.append((k + 1, w + weights[j], v + values[j], taken + (j,)))
out.append((k + 1, w, v, taken))
return out
z, best = breadth_first_branch_and_bound((0, 0.0, 0.0, ()), kids, ub, lambda x: x[0] == n, lambda x: x[2], stats)
assert best is not None
return z, sorted(best[3])
test_breadth_first_branch_and_bound.py 87 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/breadth-first-branch-and-bound/. The authors are listed in prov/Z9RZB6.jsonl.
import itertools
import random
from breadth_first_branch_and_bound import breadth_first_branch_and_bound, knapsack
def brute_knapsack(values, weights, capacity):
best = 0
for mask in itertools.product([0, 1], repeat=len(values)):
if sum(w for w, m in zip(weights, mask) if m) <= capacity:
best = max(best, sum(v for v, m in zip(values, mask) if m))
return best
def test_example_of_the_page() -> None:
stats: dict[str, int] = {}
assert knapsack([40, 30, 50, 10], [2, 5, 10, 5], 16, stats) == (90, [0, 2])
assert stats == {"expanded": 14, "generated": 26, "max_live": 12}
def test_edges() -> None:
assert knapsack([], [], 10) == (0, [])
assert knapsack([5], [3], 2) == (0, [])
assert knapsack([5], [3], 3) == (5, [0])
assert knapsack([5, 7], [0, 0], 0) == (12, [0, 1])
# a tree without leaves: the root is a dead end
assert breadth_first_branch_and_bound(0, lambda n: [], lambda n: 0, lambda n: False, lambda n: 0) == (float("-inf"), None)
# the root is the only leaf
assert breadth_first_branch_and_bound(0, lambda n: [], lambda n: 3, lambda n: True, lambda n: 3) == (3, 0)
def test_deep_tree() -> None:
n = 5000
z, best = breadth_first_branch_and_bound(
0, lambda k: [k + 1], lambda k: n, lambda k: k == n, lambda k: k
)
assert (z, best) == (n, n)
def test_random_knapsack_against_brute_force() -> None:
rng = random.Random(20240601)
for _ in range(600):
n = rng.randint(0, 9)
values = [rng.randint(0, 30) for _ in range(n)]
weights = [rng.randint(0, 15) for _ in range(n)]
capacity = rng.randint(0, 40)
z, chosen = knapsack(values, weights, capacity)
assert z == brute_knapsack(values, weights, capacity)
assert sum(weights[i] for i in chosen) <= capacity
assert sum(values[i] for i in chosen) == z
def test_random_trees_against_brute_force() -> None:
rng = random.Random(7)
for _ in range(500):
depth = rng.randint(0, 5)
# node = tuple of child indices; leaves at full depth get random values
table: dict[tuple[int, ...], int] = {}
def kids(node: tuple[int, ...]) -> list[tuple[int, ...]]:
return [node + (i,) for i in range(rng_kids[node])]
rng_kids: dict[tuple[int, ...], int] = {}
stack = [()]
leaves = []
while stack:
node = stack.pop()
if len(node) == depth:
table[node] = rng.randint(-20, 20)
leaves.append(node)
continue
rng_kids[node] = rng.randint(0, 3)
stack.extend(node + (i,) for i in range(rng_kids[node]))
def ub(node: tuple[int, ...]) -> float:
below = [table[x] for x in leaves if x[: len(node)] == node]
return max(below) + rng.randint(0, 3) if below else -100
z, best = breadth_first_branch_and_bound((), kids, ub, lambda x: len(x) == depth, lambda x: table[x])
if leaves:
assert z == max(table.values())
assert best is not None and table[best] == z
else:
assert (z, best) == (float("-inf"), None)
What the next level needs
- the tests did not run in this build