# Logical implication between binaries
#
# Encodes prerequisite structure among selectable options: choosing a
# dependent option forces its prerequisite. The inequality form is exact and
# needs no auxiliary variable.
#
# Technique: x ⇒ y becomes x ≤ y; a conjunction premise needs x1 + x2 − 1 ≤
# y.
#
# On this instance the optimum is 17 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Williams, H. P. (2013). Model Building in Mathematical
# Programming, 5th ed. Wiley.
model m
set I = {1, 2, 3, 4, 5}
set D = {1, 2, 3, 4}
const v = {7, 6, 4, 6, 9}, forall i in I
const k = 3
bin x, forall i in I
max sum_{i in I}{v_{i} * x_{i}}
# choosing the dependent forces its prerequisite
constr x_{dep(d)} <= x_{pre(d)}, forall d in D
constr sum_{i in I}{x_{i}} <= k
end
import elytica
def dep(d):
return {1: 2, 2: 3, 3: 4, 4: 5}[d]
def pre(d):
return {1: 1, 2: 2, 3: 3, 4: 4}[d]
Read this through MCP: read with path: "formulations/implication", or resource hlpl://formulations/implication.