Routing telephone calls¶
How many of 425 requested circuits a five-city network can carry at once — and by which routes.
✔ Verified against the published optimum — 380 circuits, from Guéret, Prins, Sevaux & Heipcke, Applications of Optimization with Xpress-MP §12.3.3.
Both kinds of relation, in one model, each said the way it is. A path serves
exactly one city pair, so call_of is a coordinate and the demand limit groups
through it. A path traverses several arcs, so uses is a (path, arc) table
and the capacity limit contracts against it. Neither could stand in for the
other: a coordinate is single-valued, and an incidence table cannot be grouped
by.
Five cities, six undirected links, five city pairs asking for circuits, and 17 elementary paths between them. A circuit reserves both directions of every link it crosses, which is why the network is undirected and the flow carries no sign.
The model¶
The same model, as math
Routing telephone calls over a five-city network: how many of the 425 requested circuits can be carried at once. A path serves exactly one city pair — a coordinate — and traverses several arcs — an incidence parameter; both relations, each said the way it is. Guéret, Prins, Sevaux and Heipcke, Applications of Optimization with Xpress-MP, section 12.3. Optimum 380 circuits, published in section 12.3.3.
Sets¶
| Symbol | Meaning |
|---|---|
| \(\mathcal{A}\) | index \(a\) --- arc --- an undirected link between two cities, with capacity in circuits |
| \(\mathcal{C}\) | index \(c\) --- call --- a city pair with circuits to place |
| \(\mathcal{P}\) | index \(p\) --- path with \(\mathrm{call\_of}: \mathcal{P} \to \mathcal{C}\) --- a route end to end, serving one city pair |
Parameters¶
| Symbol | Meaning |
|---|---|
| \(\mathit{capacity}\) | capacity over \(\mathcal{A}\) --- circuits an arc can carry |
| \(\mathit{demand}\) | demand over \(\mathcal{C}\) --- circuits a city pair asked for |
| \(\mathit{uses}\) | uses over \(\mathcal{P} \times \mathcal{A}\) --- which arcs a path traverses — a path uses an arc or it does not, so the value is 1 and absence is 0 |
Variables¶
| Symbol | Meaning |
|---|---|
| \(\mathit{flow}\) | flow over \(\mathcal{P}\) --- circuits carried on a path — integral because a multi-commodity flow is not integral by nature, even though this instance's relaxation happens to be |
Objective¶
Subject to¶
within_demand
within_capacity
Variable domains¶
flow
The tabs start from the instance’s tables — one frame per parameter.
description: >-
Routing telephone calls over a five-city network: how many of the 425
requested circuits can be carried at once. A path serves exactly one city
pair — a coordinate — and traverses several arcs — an incidence parameter;
both relations, each said the way it is. Guéret, Prins, Sevaux and Heipcke,
Applications of Optimization with Xpress-MP, section 12.3. Optimum 380
circuits, published in section 12.3.3.
dimensions:
arc:
description: an undirected link between two cities, with capacity in circuits
dtype: str
call:
description: a city pair with circuits to place
dtype: str
path:
description: a route end to end, serving one city pair
dtype: str
lookups:
call_of:
description: the city pair a path serves, end to end
over: path
into: call
parameters:
capacity:
description: circuits an arc can carry
dims: [arc]
demand:
description: circuits a city pair asked for
dims: [call]
uses:
description: >-
which arcs a path traverses — a path uses an arc or it does not, so the
value is 1 and absence is 0
dims: [path, arc]
variables:
flow:
description: >-
circuits carried on a path — integral because a multi-commodity flow is
not integral by nature, even though this instance's relaxation happens to
be
foreach: [path]
domain: integer
bounds:
lower: 0
constraints:
within_demand:
description: a pair cannot be carried more than it asked for, however many paths serve it
foreach: [call]
expression: sum(flow, by=call_of) <= demand
within_capacity:
description: >-
an arc carries every path that traverses it, and no more than its
capacity. A circuit reserves both directions of every arc it crosses,
which is why the network is undirected and the flow is not signed.
foreach: [arc]
expression: sum(flow * uses, over=path) <= capacity
objective:
sense: maximize
description: circuits carried, summed over every path
expression: sum(flow, over=path)
Why the answer is 380 and not 425. Troyes is reachable only over
troyes_nice (80) and troyes_valenciennes (70), so at most 150 circuits can
terminate there — and Troyes must absorb the 80 Nantes–Troyes and the 70
Paris–Troyes, which is 150 exactly. Valenciennes is reached only over
paris_valenciennes (200) and troyes_valenciennes (70), capping everything
ending there at 270 against a demand of 175 plus whatever transits. The binding
cut leaves 45 of the Nantes–Troyes circuits unplaced, and the published routing
says the same: 35 of 80 carried.
That is worth stating because the number can be derived before any solver runs, which is the strongest form a corpus entry can take — the optimum is not merely somebody else's output, it is arithmetic anybody can check.
What it exercises¶
A coordinate and an incidence parameter side by side, each carrying the relation
it fits, in a model neither we nor an energy system wrote. reserves already
proves both idioms, but as our own model built to prove them; this is the
outside witness.
Integrality is the source's, not ours: a multi-commodity flow is not integral by nature, and the book says so before observing that this instance's relaxation happens to be. A MILP has no dual solution, so the entry records none.