# Maximum clique
#
# Finds the largest mutually adjacent set of vertices. The constraint runs
# over the complement graph, which is the mirror of independent set — a
# clique in G is an independent set in the complement of G, and the two
# formulations differ only in which pairs they forbid.
#
# Technique: Forbid every NON-edge: y_u + y_v <= 1 for each pair with no
# edge between them.
#
# On this instance the optimum is 10 (maximisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Bomze, I. M., Budinich, M., Pardalos, P. M. and Pelillo, M.
# (1999). The maximum clique problem. Handbook of Combinatorial
# Optimization, 1–74.
model m
set V = {1, 2, 3, 4, 5}
set N = {1, 2, 3, 4, 5, 6, 7}
const w = {9, 6, 1, 3, 3}, forall v in V
bin y, forall v in V
max sum_{v in V}{w_{v} * y_{v}}
# a pair with no edge between them cannot both be in a clique
constr y_{lo(k)} + y_{hi(k)} <= 1, forall k in N
end
import elytica
def lo(k):
return {1: 1, 2: 1, 3: 1, 4: 2, 5: 2, 6: 2, 7: 3}[k]
def hi(k):
return {1: 2, 2: 4, 3: 5, 4: 3, 5: 4, 6: 5, 7: 5}[k]
Read this through MCP: read with path: "formulations/max-clique", or resource hlpl://formulations/max-clique.