HLPL / VerTeX Modelling Language Documentation

← formulations

# Fixed-charge network design
#
# Chooses which arcs to build as well as how much to send over them. The
# binaries are what take this out of the totally unimodular world — the flow
# part alone would be integral, but paying to open an arc makes it a genuine
# mixed-integer problem.
#
# Technique: A binary opens each arc and a big-M capacity link ties flow to
#            it: f_a <= u_a · y_a, with the tightest valid M being the arc
#            capacity.
#
# On this instance the optimum is 37 (minimisation), confirmed
# independently by integer enumeration plus simplex before publication.
#
# Reference: Magnanti, T. L. and Wong, R. T. (1984). Network design and
# transportation planning: models and algorithms. Transportation Science
# 18(1), 1–55. doi:10.1287/trsc.18.1.1
model m
set V = {1, 2, 3, 4}
set A = {1, 2, 3, 4, 5}
set outA(V) = outArcs()
set inA(V) = inArcs()
const c = {5, 3, 2, 2, 1}, forall a in A
const g = {5, 5, 4, 3, 2}, forall a in A
const u = {2, 2, 1, 3, 2}, forall a in A
const b = {4, 0, 0, -4}, forall v in V

var 0 <= f <= infty, forall a in A
bin y, forall a in A

min sum_{a in A}{c_{a} * f_{a}} + sum_{a in A}{g_{a} * y_{a}}

# flow only on an arc that has been built, capped at that arc's capacity
constr f_{a} <= u_{a} * y_{a}, forall a in A
constr sum_{a in outA(v)}{f_{a}} - sum_{a in inA(v)}{f_{a}} = b_{v}, forall v in V
end

import elytica

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

Read this through MCP: read with path: "formulations/fixed-charge-network-design", or resource hlpl://formulations/fixed-charge-network-design.