HLPL / VerTeX Modelling Language Documentation

← formulations

# Graph colouring
#
# Assigns colours so no edge is monochromatic, minimising colours used. The
# colour-used indicator is dominated by the assignment variables, which is
# what turns a feasibility question into a minimisation.
#
# Technique: One binary per (vertex, colour); adjacent vertices may not
#            share a colour; a colour-used binary counts the palette.
#
# On this instance the optimum is 3 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Mehrotra, A. and Trick, M. A. (1996). A column generation
# approach for graph coloring. INFORMS Journal on Computing 8(4), 344–354.
# doi:10.1287/ijoc.8.4.344
model m
set V = {1, 2, 3, 4, 5, 6}
set E = {1, 2, 3, 4, 5, 6, 7, 8}
set K = {1, 2, 3}

bin x, forall v in V, forall k in K
bin u, forall k in K

min sum_{k in K}{u_{k}}

# exactly one colour per vertex
constr sum_{k in K}{x_{v,k}} = 1, forall v in V
# endpoints of an edge differ in every colour class
constr x_{alpha(e),k} + x_{beta(e),k} <= 1, forall e in E, forall k in K
# a colour counts as used if any vertex takes it
constr x_{v,k} <= u_{k}, forall v in V, forall k in K
end

import elytica
def alpha(e):
  return {1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 1, 7: 2, 8: 3}[e]
def beta(e):
  return {1: 2, 2: 3, 3: 4, 4: 5, 5: 6, 6: 6, 7: 4, 8: 6}[e]

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