# Piecewise-linear cost, convex-combination form
#
# Prices an activity along a piecewise-linear cost curve. Both the level and
# its cost are written as convex combinations of the same breakpoint
# weights, so any feasible weighting names a point on the curve. Adjacency
# is enforced with segment binaries, which is what makes the form exact for
# a non-convex curve rather than only for a convex one.
#
# Technique: Express x and f(x) as the same convex combination of
# breakpoints, with the lambda weights summing to 1 and at most
# two adjacent ones nonzero.
#
# On this instance the optimum is 3 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Dantzig, G. B. (1963). Linear Programming and Extensions.
# Princeton University Press. doi:10.1515/9781400884179
model m
set B = {1, 2, 3}
set S = {1, 2}
const xb = {0, 2, 4}, forall b in B
const fb = {0, 3, 6}, forall b in B
const adj = {{1, 0},
{1, 1},
{0, 1}}, forall b in B, forall s in S
const d = 2
var 0 <= lam <= 1, forall b in B
bin z, forall s in S
var 0 <= x <= 4
var 0 <= cost <= 7
min cost
# x and its cost are the SAME convex combination of the breakpoints
constr x = sum_{b in B}{xb_{b} * lam_{b}}
constr cost = sum_{b in B}{fb_{b} * lam_{b}}
constr sum_{b in B}{lam_{b}} = 1
# exactly one segment is active, and only its two endpoints may carry weight
constr sum_{s in S}{z_{s}} = 1
constr lam_{b} <= sum_{s in S}{adj_{b,s} * z_{s}}, forall b in B
constr x >= d
end
import elytica
Read this through MCP: read with path: "formulations/piecewise-lambda", or resource hlpl://formulations/piecewise-lambda.