# At most one nonzero (SOS1 by binaries)
#
# Permits at most one activity to take a nonzero value, the condition a
# solver would otherwise express as a special ordered set of type 1. Written
# with explicit binaries and variable upper bounds it needs no
# solver-specific declaration.
#
# Technique: Bound each continuous variable by its own indicator and allow
# at most one indicator to be 1.
#
# On this instance the optimum is 18 (maximisation), 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 I = {1, 2, 3, 4, 5}
const p = {3, 3, 3, 2, 5}, forall i in I
const u = {5, 6, 2, 7, 3}, forall i in I
var 0 <= x <= infty, forall i in I
bin y, forall i in I
max sum_{i in I}{p_{i} * x_{i}}
# x_i is zero unless its indicator is on, and only one may be on
constr x_{i} <= u_{i} * y_{i}, forall i in I
constr sum_{i in I}{y_{i}} <= 1
end
import elytica
Read this through MCP: read with path: "formulations/sos1-at-most-one", or resource hlpl://formulations/sos1-at-most-one.