HLPL / VerTeX Modelling Language Documentation

← formulations

# Shortest path by arc selection
#
# Finds a least-cost path as a unit flow. Arcs are a flat index set with
# script functions giving tail and head, and the balance constraint sums
# over parametric out/in arc sets per node.
#
# Technique: Flow conservation on node balances: outflow − inflow equals +1
#            at the source, −1 at the sink, 0 elsewhere.
#
# On this instance the optimum is 12 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Ahuja, R. K., Magnanti, T. L. and Orlin, J. B. (1993). Network
# Flows: Theory, Algorithms, and Applications. Prentice Hall.
model m
set V = {1, 2, 3, 4, 5}
set A = {1, 2, 3, 4, 5, 6, 7}
set outA(V) = outArcs()
set inA(V) = inArcs()
const c = {9, 4, 9, 5, 8, 8, 5}, forall a in A
const b = {1, 0, 0, 0, -1}, forall v in V

bin x, forall a in A

min sum_{a in A}{c_{a} * x_{a}}

# unit flow leaves the source, arrives at the sink, balances elsewhere
constr sum_{a in outA(v)}{x_{a}} - sum_{a in inA(v)}{x_{a}} = b_{v}, forall v in V
end

import elytica
def outArcs():
  return {1: [1, 2], 2: [3, 4], 3: [5, 6], 4: [7], 5: []}
def inArcs():
  return {1: [], 2: [1], 3: [2, 3], 4: [4, 5], 5: [6, 7]}

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