# Robust counterpart under box uncertainty
#
# Protects a capacity constraint against coefficients that may each vary
# within a known interval. Because the variables are non-negative, the worst
# case is attained at the upper corner of every interval independently, so
# the robust counterpart is another linear constraint with no extra
# variables — the simplest uncertainty set, and the only one whose
# counterpart stays an LP with no growth.
#
# Technique: Replace each uncertain coefficient by its worst-case value
# over the box: for a <= constraint with non-negative variables,
# the nominal coefficient plus its deviation.
#
# On this instance the optimum is 13 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Soyster, A. L. (1973). Convex programming with set-inclusive
# constraints and applications to inexact linear programming. Operations
# Research 21(5), 1154–1157.
model m
set I = {1, 2, 3, 4}
const v = {5, 3, 4, 4}, forall i in I
const a = {2, 5, 3, 5}, forall i in I
const dev = {1, 3, 1, 2}, forall i in I
const lim = 16
bin x, forall i in I
max sum_{i in I}{v_{i} * x_{i}}
# every coefficient at the top of its interval simultaneously: with x >= 0 that
# is the worst case, so no auxiliary variables are needed
constr sum_{i in I}{[a_{i} + dev_{i}] * x_{i}} <= lim
end
import elytica
Read this through MCP: read with path: "formulations/robust-box-uncertainty", or resource hlpl://formulations/robust-box-uncertainty.