# Piecewise-linear via SOS2-style adjacency
#
# Evaluates a piecewise-linear function using the adjacency condition a
# solver would express as a special ordered set of type 2. Written out with
# binaries it needs no solver-specific declaration, at the cost of one
# binary per segment — the same trade the SOS1 case makes.
#
# Technique: At most two lambda weights may be nonzero and they must be
# adjacent — written with one binary per breakpoint pair rather
# than a solver-native SOS2 declaration.
#
# On this instance the optimum is 2.5 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Beale, E. M. L. and Tomlin, J. A. (1970). Special facilities in
# a general mathematical programming system for non-convex problems using
# ordered sets of variables. OR 69, 447–454.
model m
set B = {1, 2, 3}
set S = {1, 2}
const xb = {0, 2, 4}, forall b in B
const fb = {0, 5, 16}, forall b in B
const adj = {{1, 0},
{1, 1},
{0, 1}}, forall b in B, forall s in S
const need = 1
var 0 <= lam <= 1, forall b in B
bin z, forall s in S
var 0 <= lvl <= 4
var 0 <= cost <= 17
min cost
constr lvl = 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 active; only its two endpoints may carry weight,
# which is precisely the SOS2 adjacency condition
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 lvl >= need
end
import elytica
Read this through MCP: read with path: "formulations/sos2-piecewise", or resource hlpl://formulations/sos2-piecewise.