# Bin packing
#
# Packs items into as few bins as possible. Each bin's capacity row is
# multiplied by its open indicator so an unused bin can hold nothing, which
# is the fixed-charge pattern applied per bin.
#
# Technique: Assignment binaries plus per-bin capacity gated on a bin-used
# binary.
#
# On this instance the optimum is 3 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Martello, S. and Toth, P. (1990). Knapsack Problems: Algorithms
# and Computer Implementations. Wiley.
model m
set I = {1, 2, 3, 4, 5}
set B = {1, 2, 3, 4}
const s = {5, 4, 5, 2, 3}, forall i in I
const c = 7
bin x, forall i in I, forall b in B
bin y, forall b in B
min sum_{b in B}{y_{b}}
# each item in exactly one bin
constr sum_{b in B}{x_{i,b}} = 1, forall i in I
# a bin's contents fit only if the bin is open
constr sum_{i in I}{s_{i} * x_{i,b}} <= c * y_{b}, forall b in B
end
import elytica
Read this through MCP: read with path: "formulations/bin-packing", or resource hlpl://formulations/bin-packing.