# Absolute value in the objective
#
# Minimises total absolute deviation from a target vector. The absolute
# value is replaced by one auxiliary variable per term bounded below by both
# signs of the deviation; minimisation drives it down to the true absolute
# value.
#
# Technique: Replace |e| by t with t ≥ e and t ≥ −e when minimising.
#
# On this instance the optimum is 2 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Charnes, A. and Cooper, W. W. (1955). Generalizations of the
# warehousing model. Operational Research Quarterly 6(4), 131–172.
# doi:10.2307/3006550
model m
set I = {1, 2, 3, 4}
const a = {2, 4, 1, 2}, forall i in I
const c = 7
int 0 <= x <= 8, forall i in I
int 0 <= t <= 20, forall i in I
min sum_{i in I}{t_{i}}
# t_i bounds |a_i - x_i| from both sides; minimisation makes it exact
constr t_{i} >= a_{i} - x_{i}, forall i in I
constr t_{i} >= x_{i} - a_{i}, forall i in I
constr sum_{i in I}{x_{i}} <= c
end
import elytica
Read this through MCP: read with path: "formulations/absolute-value", or resource hlpl://formulations/absolute-value.