Skip to main content

Knapsack and Bin Packing

Knapsack and bin packing both use capacities, but they answer different questions. Knapsack selects a valuable subset for one limited container; bin packing must place every item while minimizing how many containers are opened.

Prerequisites​

Complete network-flow problems.

Learning goals​

  • Distinguish selection variables from item-to-bin assignment variables.
  • State weight, capacity, value, and objective units.
  • Recognize interchangeable-bin symmetry and add valid symmetry breaking.
  • Validate placement, load, and objective independently from solver fields.

Formulation before solver choice​

For bin packing, let xib∈{0,1}x_{ib}\in\{0,1\} assign item ii to candidate bin bb, and yb∈{0,1}y_b\in\{0,1\} open bin bb. With item weights wiw_i kilograms and capacity CC kilograms,

\sum_iw_ix_{ib}\le Cy_b\ \forall b.$$ Candidate bins are interchangeable, so many variable assignments describe the same physical packing. Ordering $y_b\ge y_{b+1}$ and nonincreasing loads removes some symmetry without removing a physically distinct solution. It is a performance aid, not a new operating requirement. ## Worked example ```python from ortools.sat.python import cp_model weights = [4, 3, 3, 2] # kilograms capacity = 5 bins = range(len(weights)) model = cp_model.CpModel() x = [[model.new_bool_var(f"item_{i}_bin_{b}") for b in bins] for i in range(len(weights))] y = [model.new_bool_var(f"bin_{b}_open") for b in bins] loads = [model.new_int_var(0, capacity, f"load_{b}") for b in bins] for i in range(len(weights)): model.add_exactly_one(x[i]) for b in bins: model.add(loads[b] == sum(weights[i] * x[i][b] for i in range(len(weights)))) model.add(loads[b] <= capacity * y[b]) for b in range(len(weights) - 1): model.add(y[b] >= y[b + 1]) model.add(loads[b] >= loads[b + 1]) model.minimize(sum(y)) solver = cp_model.CpSolver() solver.parameters.num_search_workers = 1 solver.parameters.random_seed = 0 status = solver.solve(model) if status != cp_model.OPTIMAL: raise RuntimeError(solver.status_name(status)) used_loads = [solver.value(loads[b]) for b in bins if solver.value(y[b])] assignments = [sum(solver.value(x[i][b]) for b in bins) for i in range(len(weights))] print(f"status={solver.status_name(status)} bins_used={len(used_loads)} loads_kg={used_loads}") print(f"each_item_once={assignments == [1, 1, 1, 1]} capacity_kg={capacity}") print("symmetry_breaking=open_bins_and_loads_nonincreasing") ``` Expected output: ```text status=OPTIMAL bins_used=3 loads_kg=[5, 4, 3] each_item_once=True capacity_kg=5 symmetry_breaking=open_bins_and_loads_nonincreasing ``` The total weight is 12 kg, so the lower bound $\lceil12/5\rceil=3$ proves that two bins cannot suffice. CP-SAT returns an `OPTIMAL` three-bin packing, and direct checks confirm every item is assigned once and no load exceeds 5 kg. ## Limitations and common mistakes - Knapsack may leave items out; bin packing may not. Reusing one formulation for the other changes the question. - Weight is only one possible dimension; volume, incompatibilities, balance, and fragility may matter. - Symmetry breaking must preserve at least one representative of every physical solution. - CP-SAT uses integer coefficients; scale rational measurements carefully and document precision loss. - This four-item proof says nothing about large-instance solve time. ## Practice Add a fifth 2 kg item. Derive a weight lower bound, solve, and check whether the bound is tight. Then state one compatibility rule that a one-dimensional capacity model misses. ## Next steps Represent precedence and shared machines explicitly in [scheduling and resource allocation](./scheduling-and-resource-allocation). ## Primary sources Checked 2026-10-19: Google OR-Tools `9.15`, [bin-packing guide](https://developers.google.com/optimization/pack/bin_packing), [knapsack guide](https://developers.google.com/optimization/pack/knapsack), and [CP-SAT solver/status documentation](https://developers.google.com/optimization/cp/cp_solver).