Solve the bin packing problem in Python

Bin packing — fit a set of items into as few fixed-capacity bins as possible — is everywhere: filling trucks, VMs onto servers, ads into breaks, files onto disks. The usual answer is a greedy first-fit-decreasing pass, which is quick but not optimal. With quicopt you get the provably fewest bins in a few lines of Python.

The naive approach

First-fit-decreasing sorts items large-to-small and drops each into the first bin that fits. It is a good heuristic, but it can waste a bin and never tells you whether fewer was possible. Trying every assignment is exponential. Model it instead.

Model it as a MILP

y[b] marks bin b as used; x[i][b] puts item i in bin b. Every item goes in exactly one bin, each bin respects its capacity, and we minimize bins used:

from ortools.math_opt.python import mathopt
from quicopt import Client
size = [4, 8, 5, 7, 3, 6]
C = 10
n = len(size)
B = n  # at most n bins
model = mathopt.Model(name="bin_packing")
y = [model.add_binary_variable(name=f"y{b}") for b in range(B)]
x = [[model.add_binary_variable(name=f"x_{i}_{b}") for b in range(B)] for i in range(n)]
for i in range(n):
    model.add_linear_constraint(sum(x[i][b] for b in range(B)) == 1)
for b in range(B):
    model.add_linear_constraint(sum(size[i] * x[i][b] for i in range(n)) <= C * y[b])
model.minimize(sum(y))
print(Client("https://try.quicoptapi.pgi.fz-juelich.de").solve(model).display)

├── status:     optimal
├── feasible:   true
├── objective:  4.0
├── x:          x_0_0=0, x_0_1=0, x_0_2=0, x_0_3=0, x_0_4=0, x_0_5=1, …  (42 variables)
└── solve_time: 0.0185 s

What you get

status: optimal means 4 bins is proven minimal for these six items — no packing uses fewer. The total size is 33 and each bin holds 10, so three bins (capacity 30) can't work; the solver proves four is the floor, which a greedy pass can only guess at.

The same model extends to larger instances and takes side rules as plain linear constraints — you change the data, not the method. (Bin packing is NP-hard, and this compact formulation is bin-symmetric, so it is best on small-to-medium instances; very large packings call for symmetry-breaking or specialized methods.)

Next

• The problem class behind this: Mixed-integer linear (MILP)
• A runnable model for every supported class: Examples
• Set up the client and solve your first model: Getting started

Reference: M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.