mamut_routing_tools.generation.binpacking

The minimum number of vehicles a load needs, computed rather than estimated.

CVRPLIB names an instance X-n101-k25, and that k is the exact optimum of a bin-packing problem over the demands -- not a heuristic's fleet size and not the continuous bound. It is published as a lower bound: the fleet is not fixed and a solution may use more routes than the name says.

The continuous bound ceil(sum(q) / Q) is what this repository published before, and it is genuinely weaker. On the v2 collection it understated the truth on several bases: mamut-metz-n135-poi shipped num_vehicles_lb = 33 where the Martello-Toth bound alone already proves 37. A lower bound that is not tight is not wrong, but it is worth less to anyone using it.

Exactness here is cheap because these demand distributions are kind: capacity is ceil(r * mean demand) for a route-size target r of at least three, so bins hold several items and first-fit-decreasing usually lands on the bound. On the v2 collection L2 == FFD closed 104 of 110 bases with no search at all. The six that did not are handled by a bounded search, and if even that does not close, the bound is published as a bound and said to be one.

BinCount dataclass

BinCount(lower: int, upper: int, method: str)

What is known about the minimum bin count, and how firmly.

continuous_bound

continuous_bound(demands: Sequence[int], capacity: int) -> int

ceil(sum / capacity) -- the bound every load satisfies for free.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/generation/binpacking.py

def continuous_bound(demands: Sequence[int], capacity: int) -> int:
    """``ceil(sum / capacity)`` -- the bound every load satisfies for free."""
    total = sum(demands)
    if total <= 0:
        return 0
    return int(math.ceil(total / capacity))

martello_toth_l2

martello_toth_l2(demands: Sequence[int], capacity: int) -> int

The L2 bound: count the items too big to share, then bound the rest.

For a threshold a, items larger than capacity - a need a bin each and can take no item of size a or more alongside. Items above half capacity cannot pair with each other, so each holds its own bin too, leaving a known amount of room. Everything from a up to half capacity must fit in that room or open new bins. Maximising over a gives the bound.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/generation/binpacking.py

def martello_toth_l2(demands: Sequence[int], capacity: int) -> int:
    """The L2 bound: count the items too big to share, then bound the rest.

    For a threshold ``a``, items larger than ``capacity - a`` need a bin each and
    can take no item of size ``a`` or more alongside. Items above half capacity
    cannot pair with each other, so each holds its own bin too, leaving a known
    amount of room. Everything from ``a`` up to half capacity must fit in that
    room or open new bins. Maximising over ``a`` gives the bound.
    """
    sizes = sorted((int(q) for q in demands if q > 0), reverse=True)
    if not sizes:
        return 0
    half = capacity / 2
    best = continuous_bound(sizes, capacity)
    thresholds = {0} | {size for size in sizes if size <= half}
    for alpha in thresholds:
        big = [size for size in sizes if size > capacity - alpha]
        medium = [size for size in sizes if capacity - alpha >= size > half]
        small = [size for size in sizes if half >= size >= alpha]
        # Room left over in the bins the medium items already occupy.
        spare = len(medium) * capacity - sum(medium)
        overflow = sum(small) - spare
        extra = int(math.ceil(overflow / capacity)) if overflow > 0 else 0
        best = max(best, len(big) + len(medium) + extra)
    return best

cardinality_bound

cardinality_bound(demands: Sequence[int], capacity: int) -> int

How few bins can hold this many items, ignoring the sizes' arithmetic.

L2 reasons about weight and misses counting. Four thousand demands of 3 in bins of 10 weigh 12 000 against 12 000 of capacity, so every weight-based bound says 1200 -- but only three of them fit in a bin, so the answer is 1334. Small-demand instances are exactly where this bites, and demand_type 2 and 3 produce them by design.

An item larger than capacity / (t + 1) cannot appear more than t times in one bin, so counting such items and dividing by t bounds the fleet. Maximising over t costs one pass per value and needs no search.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/generation/binpacking.py

def cardinality_bound(demands: Sequence[int], capacity: int) -> int:
    """How few bins can hold this many items, ignoring the sizes' arithmetic.

    L2 reasons about weight and misses counting. Four thousand demands of 3 in
    bins of 10 weigh 12 000 against 12 000 of capacity, so every weight-based
    bound says 1200 -- but only three of them fit in a bin, so the answer is
    1334. Small-demand instances are exactly where this bites, and
    ``demand_type`` 2 and 3 produce them by design.

    An item larger than ``capacity / (t + 1)`` cannot appear more than ``t``
    times in one bin, so counting such items and dividing by ``t`` bounds the
    fleet. Maximising over ``t`` costs one pass per value and needs no search.
    """
    sizes = sorted((int(q) for q in demands if q > 0), reverse=True)
    if not sizes:
        return 0
    best = 0
    smallest = sizes[-1]
    # Beyond this, the threshold drops under the smallest item and the count
    # stops growing while the divisor keeps rising.
    limit = max(1, capacity // smallest)
    index = 0
    for t in range(1, limit + 1):
        threshold = capacity / (t + 1)
        while index < len(sizes) and sizes[index] > threshold:
            index += 1
        if index:
            best = max(best, int(math.ceil(index / t)))
    return best

first_fit_decreasing

first_fit_decreasing(demands: Sequence[int], capacity: int) -> int

Bins used by FFD -- a constructive upper bound.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/generation/binpacking.py

def first_fit_decreasing(demands: Sequence[int], capacity: int) -> int:
    """Bins used by FFD -- a constructive upper bound."""
    remaining: list[int] = []
    for size in sorted((int(q) for q in demands if q > 0), reverse=True):
        for index, room in enumerate(remaining):
            if room >= size:
                remaining[index] = room - size
                break
        else:
            remaining.append(capacity - size)
    return len(remaining)

best_fit_decreasing

best_fit_decreasing(demands: Sequence[int], capacity: int) -> int

Bins used by BFD. Beats FFD often enough to be worth the second pass.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/generation/binpacking.py

def best_fit_decreasing(demands: Sequence[int], capacity: int) -> int:
    """Bins used by BFD. Beats FFD often enough to be worth the second pass."""
    remaining: list[int] = []
    for size in sorted((int(q) for q in demands if q > 0), reverse=True):
        best_index = -1
        best_room = capacity + 1
        for index, room in enumerate(remaining):
            if size <= room < best_room:
                best_index, best_room = index, room
        if best_index < 0:
            remaining.append(capacity - size)
        else:
            remaining[best_index] -= size
    return len(remaining)

minimum_bins

minimum_bins(demands: Sequence[int], capacity: int, *, node_budget: int = DEFAULT_NODE_BUDGET) -> BinCount

Fewest bins of capacity that hold demands.

Returns what was proven, not a guess: when the bounds meet, lower is the optimum; when the search runs out of budget, lower is still a valid lower bound and proven says so.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/generation/binpacking.py

def minimum_bins(
    demands: Sequence[int],
    capacity: int,
    *,
    node_budget: int = DEFAULT_NODE_BUDGET,
) -> BinCount:
    """Fewest bins of ``capacity`` that hold ``demands``.

    Returns what was proven, not a guess: when the bounds meet, ``lower`` is the
    optimum; when the search runs out of budget, ``lower`` is still a valid lower
    bound and ``proven`` says so.
    """
    if capacity <= 0:
        raise ValueError(f"capacity must be positive, got {capacity}")
    sizes = sorted((int(q) for q in demands if q > 0), reverse=True)
    if not sizes:
        return BinCount(lower=0, upper=0, method="empty")
    if sizes[0] > capacity:
        raise ValueError(
            f"demand {sizes[0]} exceeds capacity {capacity}: no packing exists"
        )

    lower = max(
        continuous_bound(sizes, capacity),
        martello_toth_l2(sizes, capacity),
        cardinality_bound(sizes, capacity),
    )
    upper = min(first_fit_decreasing(sizes, capacity), best_fit_decreasing(sizes, capacity))
    if lower >= upper:
        return BinCount(lower=upper, upper=upper, method="bounds-met")

    budget = [int(node_budget)]
    for target in range(lower, upper):
        try:
            if _packs_into(sizes, capacity, target, budget):
                return BinCount(lower=target, upper=target, method="search")
        except _BudgetExhausted:
            return BinCount(lower=lower, upper=upper, method="budget-exhausted")
        lower = target + 1
    return BinCount(lower=upper, upper=upper, method="search")

minimum_vehicles

minimum_vehicles(demands: Sequence[int], capacity: int) -> int

The published k: the best proven lower bound on the fleet.

Valid as a lower bound in every case, exact in all but the rare instance whose search does not close. Callers that need to know which they got should use :func:minimum_bins.

Source code in MAMUT-routing-tools/src/mamut_routing_tools/generation/binpacking.py

def minimum_vehicles(demands: Sequence[int], capacity: int) -> int:
    """The published ``k``: the best proven lower bound on the fleet.

    Valid as a lower bound in every case, exact in all but the rare instance
    whose search does not close. Callers that need to know which they got should
    use :func:`minimum_bins`.
    """
    return minimum_bins(demands, capacity).lower