Bin packing

What it decides

For every item, the solver picks a bin.

Minimal example

from optimaru.bin_packing import solve
from optimaru.bin_packing.models import BinPackingProblemModel, ItemModel

problem = BinPackingProblemModel(
    bin_capacity=10,
    items=[
        ItemModel(id="A", weight=8), ItemModel(id="B", weight=7),
        ItemModel(id="C", weight=3), ItemModel(id="D", weight=2),
    ],
)

core = problem.to_core()
print(solve(core, time_limit_seconds=1.0, random_seed=42))  # a Score such as 0hard/-2soft
solved = BinPackingProblemModel.from_core(core)
print({item.id: item.bin for item in solved.items}, solved.bins_used, solved.bin_loads)

The same use case as a Jupyter notebook, with charts and saved outputs: examples/bin-packing.ipynb ↗

Input parameters

ItemModel

id required Item id. weight required One-dimensional weight or size. color Optional color. At most one item of each color fits in a bin.

ConflictModel

first required Id of one item. second required Id of the item it may not share a bin with.

BinPackingProblemModel

bin_capacity required Maximum load of each bin. All bins are the same. items required Items, each assigned exactly once. conflicts Item pairs that may not share a bin.

Solve parameters

What you pass to the solve call. Time limit, seed and parallel count are here.

The search starts from best fit decreasing and runs late acceptance with change and swap moves, ruin-and-recreate, and two moves that empty bins in one step, because a bin stops costing only when its last item leaves. EmptyBinMove checks the capacity alone. RepackMove puts the items of a few light bins back only where they break nothing, so it is the move that closes bins when items have colors or conflicts. On a 120-item instance with 4 colors and 10 conflicts, whose weights alone need 43 bins, it reaches 43 bins in 2 seconds: one fewer than 0.1.5, and two or three fewer than without the move.

All search options (29)

Set these on a SolverConfig and pass it as config=.

Parameter	Default	Meaning
best_score_limit	—	Stop early once the best score reaches this value. By default it never fires.
change_move_weight	0.75	Relative share of change moves. 0 disables them.
custom_move_probability	1.0	Cap on how often a step may draw a use-case move. 1 means no cap.
descent_weight	0.0	Share of best-improvement descent. 0 turns it off.
empty_bin_candidates	3	Both bin-emptying moves empty one of this many lightest bins. 1 means always the lightest.
empty_bin_moves	True	Enable EmptyBinMove, which moves every item of one light bin into the other bins at once. It checks only the capacity, so with colors or conflicts it seldom closes a bin; repack_moves does.
full_assert	False	Check every incremental score against a full recompute. Slow; for debugging.
late_acceptance_size	0	Late-acceptance history length. 0 picks it from the instance size.
on_new_best	None	Callback run on each new best solution. If it raises, the solve stops and raises the same exception.
parallel_solver_count	1	Independent parallel starts, each with its own seed and the full budget. The best one wins.
random_seed	0	Seed for the search.
repack_moves	True	Enable RepackMove: empty a light bin together with up to repack_partner_bins other light bins, then put the items back heaviest first, each into the fullest bin where it breaks no capacity, color or conflict rule. With colors or conflicts, this is the move that closes bins.
repack_partner_bins	2	Most other light bins RepackMove empties along with the first. 0 means the first bin alone; a negative value raises ValueError.
ruin_recreate	True	Run adaptive ruin-and-recreate kicks when the search stagnates.
ruin_recreate_as_move_max_ruin	12	Most entities that small ruin removes.
ruin_recreate_as_move_weight	0.0	Probability that a step is a small ruin and repair, judged like any other move. Negative picks it automatically where the use case supports that; 0 turns it off.
ruin_recreate_max_ruin_count	60	Absolute cap on entities removed per kick.
ruin_recreate_max_ruin_fraction	0.3	Largest share of the solution one kick removes.
ruin_recreate_min_ruin_fraction	0.1	Smallest share of the solution one kick removes.
ruin_recreate_operator_decay	0.8	How fast operator weights adapt.
ruin_recreate_polish_steps	5000	Hill-climbing moves that polish each kick. Not counted against step_count_limit.
ruin_recreate_rewards	[33.0, 9.0, 3.0, 0.0]	Operator rewards for a new best, a better, an accepted and a rejected result.
ruin_recreate_unimproved_step_trigger	5000	Steps without a new best before a kick.
spent_limit_seconds	30.0	Time budget in seconds, from 0 to 1e9.
step_count_limit	0	Stop after this many steps. 0 means no limit.
swap_move_weight	0.25	Relative share of swap moves. 0 disables them.
unimproved_spent_limit_seconds	0.0	Stop after this many seconds without a new best. 0 means no limit.
unimproved_step_count_limit	0	Stop after this many steps without a new best. 0 means no limit.
value_recommender_probability	0.5	Probability that a change move puts an item into a bin already in use instead of any bin. 0 means off.

What comes back

solve takes the engine object from to_core(), fills it in place and returns the engine Score, such as 0hard/-2soft, with .hard and .soft. Convert with from_core to read the result as a model. When the search moves anything, bins come back numbered from 0 in order of first use.

ItemModel

bin Zero-based bin index. -1 means unsolved.

BinPackingProblemModel

bins_used Non-empty bins. bin_loads Total weight in each bin. score_hard Hard score. 0 means feasible. score_soft Soft score: bins used, negated.

Constraints

Pick them by calling their classes from optimaru.bin_packing.constraints, such as BinCapacityCost(). Only what you pass is scored; pass nothing to keep the defaults. A list may name a constraint more than once, and each pick is scored on its own. Each one takes these parameters:

This continues the minimal example above.

from optimaru.bin_packing.constraints import BinCapacityCost, UsedBinsCost, get_constraints

picked = get_constraints([BinCapacityCost(weight=5), UsedBinsCost()])
print(solve(problem.to_core(), time_limit_seconds=1.0, random_seed=42, constraints=picked))

How constraints work →

Starting from an existing solution

This needs the latest release: pip install -U optimaru.

with_initial_solution(problem, solution) returns a copy of a BinPackingProblemModel whose search starts from solution, a solved model or the same thing as a JSON dict. Call .to_core() on the copy before solve.

This continues the minimal example above.

from optimaru.bin_packing import with_initial_solution

warm = with_initial_solution(problem, solved).to_core()
print(solve(warm, time_limit_seconds=1.0, random_seed=42), warm.bin_loads())

• Items are matched by id. Items left out or at bin -1 are placed around the seeded bins by the best-fit construction before the search starts, and a complete seed skips construction.
• With time_limit_seconds=0 the solve stops at once, so a complete solution comes back as it went in. Use the time limit for this: step_count_limit = 0 means no limit.
• Unknown ids, duplicates and bins outside the item count raise ValueError.

Exceptions and limits

• Bins are one-dimensional and all the same size. The problem has no weight fields: every default weight is 1, and you change a weight through constraints=.

Try it

• Live demo ↗
• Jupyter notebook ↗
• On the solutions page →