# Capacitated lot sizing
#
# Adds a production ceiling to uncapacitated lot sizing, which is what makes
# the problem hard: without it a period can always cover all future demand
# and the shortest-path reformulation applies. The big-M on the setup row is
# tightened to the smaller of the capacity and the demand still to be met,
# because a looser one weakens the relaxation for nothing.
#
# Technique: Wagner–Whitin balance plus a per-period capacity that the
# setup binary gates: x_t <= min(capacity, remaining demand) *
# y_t.
#
# On this instance the optimum is 30 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Bitran, G. R. and Yanasse, H. H. (1982). Computational
# complexity of the capacitated lot size problem. Management Science 28(10),
# 1174–1186.
model m
set T = {1, 2, 3}
const d = {3, 3, 1}, forall t in T
const M = {3, 3, 1}, forall t in T
const f = 10
const h = 3
const lim = 3
int 0 <= x <= 3, forall t in T
int 0 <= s <= 7, forall t in T
bin y, forall t in T
min f * sum_{t in T}{y_{t}} + h * sum_{t in T}{s_{t}}
constr s_{1} = x_{1} - d_{1}
constr s_{t} = s_{t-1} + x_{t} - d_{t}, forall t in T setminus {1}
# production needs its setup, and cannot exceed capacity
constr x_{t} <= M_{t} * y_{t}, forall t in T
constr x_{t} <= lim, forall t in T
end
import elytica
Read this through MCP: read with path: "formulations/capacitated-lot-sizing", or resource hlpl://formulations/capacitated-lot-sizing.