HLPL / VerTeX Modelling Language Documentation

← formulations

# Mutual exclusion and complementarity
#
# Selects from options where certain pairs cannot coexist. The pairwise form
# is the tightest encoding for isolated conflicts; a clique of mutually
# conflicting options is better written as one constraint summing over the
# clique.
#
# Technique: At most one of a conflicting pair may be chosen: x_i + x_j ≤
#            1.
#
# On this instance the optimum is 19 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Padberg, M. W. (1973). On the facial structure of set packing
# polyhedra. Mathematical Programming 5(1), 199–215. doi:10.1007/BF01580121
model m
set I = {1, 2, 3, 4, 5}
set K = {1, 2, 3, 4}
const v = {6, 7, 6, 3, 6}, forall i in I

bin x, forall i in I

max sum_{i in I}{v_{i} * x_{i}}

# conflicting options may not both be selected
constr x_{first(k)} + x_{second(k)} <= 1, forall k in K
end

import elytica
def first(k):
  return {1: 1, 2: 1, 3: 2, 4: 3}[k]
def second(k):
  return {1: 3, 2: 4, 3: 3, 4: 4}[k]

Read this through MCP: read with path: "formulations/mutual-exclusion", or resource hlpl://formulations/mutual-exclusion.