# Disjunctive (either-or) constraints
#
# Requires at least one of two resource constraints to hold rather than
# both. A binary selects which is active; the inactive one is relaxed by a
# big-M chosen large enough to be non-binding but no larger.
#
# Technique: Relax one of two constraints with a big-M term controlled by a
# binary, so exactly one is enforced.
#
# On this instance the optimum is 23 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Balas, E. (1979). Disjunctive programming. Annals of Discrete
# Mathematics 5, 3–51. doi:10.1016/S0167-5060(08)70342-X
model m
set I = {1, 2, 3}
const v = {8, 9, 6}, forall i in I
const f = {4, 1, 1}, forall i in I
const g = {3, 1, 5}, forall i in I
const M = 25
bin x, forall i in I
bin y
max sum_{i in I}{v_{i} * x_{i}}
# y = 1 relaxes the first constraint, y = 0 relaxes the second;
# whichever is not relaxed must hold
constr sum_{i in I}{f_{i} * x_{i}} <= 6 + M * y
constr sum_{i in I}{g_{i} * x_{i}} <= 4 + M * [1 - y]
end
import elytica
Read this through MCP: read with path: "formulations/either-or", or resource hlpl://formulations/either-or.