# Piecewise-linear, incremental (delta) form
#
# An alternative to the convex-combination form. The level is the sum of
# filled segment fractions, and ordering constraints force segments to be
# consumed left to right, so the cost picks up each segment's slope in turn.
# Locally ideal, and uses one binary fewer than the lambda form.
#
# Technique: Fill segments in order: delta_s in [0,1], and a segment may
# only start once the previous one is full, enforced by z_s.
#
# On this instance the optimum is 10 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Markowitz, H. M. and Manne, A. S. (1957). On the solution of
# discrete programming problems. Econometrica 25(1), 84–110.
# doi:10.2307/1907744
model m
set S = {1, 2, 3, 4}
const w = {3, 2, 2, 1}, forall s in S
const g = {2, 2, 4, 5}, forall s in S
const d = 5
var 0 <= delta <= 1, forall s in S
bin z, forall s in S
min sum_{s in S}{g_{s} * w_{s} * delta_{s}}
# the level is the total of the filled segment fractions
constr sum_{s in S}{w_{s} * delta_{s}} >= d
# a segment may only be entered once the previous one is completely full
constr delta_{s} <= z_{s-1}, forall s in S setminus {1}
constr z_{s} <= delta_{s}, forall s in S
end
import elytica
Read this through MCP: read with path: "formulations/piecewise-incremental", or resource hlpl://formulations/piecewise-incremental.