Algorithms for Network Optimization and Management

Contents

• Introduction and overview
• 0. Review: graphs, linear programming and complexity
• 1. Telecommunication networks and their optimization problems
• 2. Flows, paths and cuts
• 3. Traffic engineering: routing the flows
• 4. Network design and capacity planning
• 5. Exact methods: branch-and-bound, cutting planes and decomposition
• 6. Placement of network components
• 7. Heuristics and matheuristics
• 8. Future networks: virtualization, slicing and autonomy
• 9. Resilience, security and energy
• 10. Hybrid methods: optimization and learning
• 11. Research directions and open problems
• Exercises
• Projects and assessment
• References

Introduction and overview

Audience: a student with an M1 in mathematics, computer science or physics who knows what a linear program is and wants to see how operators decide where to install capacity, how to route traffic and where to place network functions.

Empirical first: on the six-node backbone used throughout this page, routing each demand on one minimum-hop path loads a 5 Gb/s link to 92 %. A linear program routes the same 40 Gb/s with a maximum load of 82.1 %, and a two-link cut proves that nobody can do better. Splitting evenly over all minimum-hop paths, which sounds safer, overloads that link to 123 %.

The course is about decision support for networks. It turns design, planning and operation questions into mathematical programs, solves them exactly when possible and approximately when time is short, and then studies the new problems of virtualized and autonomous networks. It shares its duality and decomposition tools with Convex Optimization and Distributed and Large-Scale Optimization, and its learning-based methods with Graphs in Machine Learning and Reinforcement Learning.

What you will be able to do

• Describe a telecommunication network as an optimization model: graph, capacities, traffic matrix, routing rules, time scale of the decision.
• Compute shortest paths, maximum flows, minimum cuts and minimum-cost flows, and explain why the last ones are integral.
• Write arc-node and arc-path formulations of multicommodity flow problems and solve them with an off-the-shelf solver.
• Formulate traffic engineering, network design, capacity planning and placement problems as linear or mixed-integer programs, and compare the strength of two formulations.
• Derive valid inequalities (cut-set, metric) and lower bounds from LP duality and Lagrangian relaxation.
• Implement branch-and-bound, a subgradient method, column generation and the principle of Benders decomposition on network problems.
• Design, tune and evaluate heuristics, reporting a gap to a proven bound.
• Model network slicing, online admission, resilience, security and energy requirements, starting from a written specification.
• Explain how machine learning can speed up or replace parts of an optimization pipeline, and what guarantees are lost.
• Read a research paper on network optimization, reproduce one of its results and present it.

Official objectives and syllabus (2026–2027)

The course description on master-mva.com presents decision support as essential to plan and manage networks. Its objective is to give knowledge of mathematical optimization methods and of their use for network design and management, methods it calls all the more crucial as algorithmic challenges grow with virtualized and autonomous networks.

The first part refreshes operations research (combinatorial optimization, graph theory) and telecom networks, presents the main exact methods, applies them to network design, capacity planning, traffic engineering and placement of network components, and uses labs with off-the-shelf solvers and heuristics. The second part covers the optimization problems of recent network evolutions, with labs based on research papers. The Université Paris-Saclay course detail repeats the objective and the list of topics.

Extensions beyond the syllabus: the Fortz–Thorup congestion cost and the analysis of even splitting (ch. 3), Γ-robust routing (ch. 9.2), decision-focused learning (ch. 11.7) and the research chapter (ch. 11, self-study).

Where this course fits in the programme

Official prerequisites: operations research, Python programming and networks. The course carries the I&I track label and is limited to 20 students (numerus clausus, master-mva.com).

• Refreshers — Linear Algebra, Analysis and Optimization (linear programming, duality, convexity), Scientific Python (NumPy, SciPy for every lab) and Probability and Statistics (for uncertain traffic in ch. 9).
• Semester 1 courses that prepare it — Convex Optimization and Applications in Machine Learning (Lagrangian duality, subgradients), Foundations of Distributed and Large-Scale Computing Optimization (decomposition), Advanced Learning for Text and Graph Data and Deep Learning (graph neural networks for ch. 10), Optimal Transport for Machine Learning (discrete transport is a minimum-cost flow).
• Related courses of semester 2 — Graphs in Machine Learning, Reinforcement Learning, Stopping Times and Online Algorithms (competitive analysis, ch. 8.3), Sequential Learning, Graphical Models: Discrete Inference and Learning (minimum cuts and LP relaxations) and Artificial Intelligence and the Environment (energy, ch. 9.4).
• After the course — the Research Internship, often hosted by operators, equipment vendors or operations research laboratories.

Course outline

• Review: graphs, linear programming and complexity — incidence matrices, LP duality and complementary slackness, integer programs, NP-hardness.
• Telecommunication networks and their optimization problems — layers, capacities, traffic matrices, routing protocols, virtualization, and the three time scales of decisions.
• Flows, paths and cuts — shortest paths, maximum flow and minimum cut, total unimodularity, multicommodity flows and their feasibility.
• Traffic engineering: routing the flows — congestion objectives, the minimum maximum utilisation LP and its dual, shortest-path routing with weights, explicit and segment routing.
• Network design and capacity planning — fixed-charge design, strong and weak formulations, modular capacities, cut-set and metric inequalities.
• Exact methods — branch-and-bound, cutting planes, Lagrangian relaxation, column generation and Benders decomposition.
• Placement of network components — facility location, SDN controllers, virtual network functions and service chains, virtual network embedding.
• Heuristics and matheuristics — greedy and rounding, local search and metaheuristics, solver-based heuristics, honest evaluation.
• Future networks: virtualization, slicing and autonomy — slicing models, online admission, closed-loop re-optimization, from a standard to a model.
• Resilience, security and energy — survivable design, robust routing, interdiction and monitoring, energy-aware routing.
• Hybrid methods: optimization and learning — learning to branch and to prune, with the guarantees that remain.
• Research directions and open problems — fast and learned traffic engineering at scale, guarantees for heuristics, robustness from data, joint compute–network orchestration, language models for modelling, decision-focused learning (self-study).

Session plan

30 h in class = 10 sessions of 3 h.

The volume is the 30 h of the Université Paris-Saclay programme table, which master-mva.com also announces: 12 h of lectures and 18 h of labs (“TP”). The split below is a proposal: each session combines about 1 h 15 of lecture with a lab, and sessions 8–10 follow the second part of the course, where labs become paper readings and presentations.

Level 1 = foundations, 2 = core models and exact methods, 3 = future networks and research-level material; the level never decreases.

Self-study, outside the 30 h (about 5 h in total): ch. 11 Research directions and open problems (≈ 3 h, with Ex. 19) · finishing the labs on a public SNDlib instance (≈ 2 h).

How to study this module

• Read ch. 0 before session 1; the duality results are used in every later chapter without warning.
• Keep the six-node backbone of ch. 1 in mind: it reappears in ch. 2, 3, 5, 7, 8 and 9, and its numbers can be checked by hand.
• After each session, run the Python blocks of the chapter and change one parameter (traffic volume, capacity, number of candidate paths) to see which constraint becomes binding.
• Do the ★ exercises the same week; the ★★ proofs (Ex. 7–16) prepare the written part of any assessment.
• The Python environment is NumPy, SciPy (whose linprog and milp call the open-source HiGHS solver), NetworkX and scikit-learn. Commercial solvers (CPLEX, Gurobi) have free academic licences and solve the same models faster.
• For the second part, choose a paper from ch. 11 early and read it alongside ch. 8–10.

0. Review: graphs, linear programming and complexity

Every model of the course is a graph with numbers on its arcs, turned into a linear or integer program. This chapter fixes the notation and recalls the three results used everywhere: the incidence matrix, LP duality and the meaning of NP-hardness.

0.1 Graphs and their matrices

A telecom link is full duplex: it is modelled by two opposite arcs with the same capacity, as in the backbone of ch. 1.

0.2 Linear programming and duality

A dual variable is a shadow price: the rate at which the optimal value changes when the right-hand side of its constraint grows. In network models, the dual of a capacity constraint is the value of one more unit of capacity on that link (ch. 3.2, ch. 5.4).

import numpy as np
from scipy.optimize import linprog

# Primal: max 3x1 + 2x2  s.t.  x1 + x2 <= 4,  x1 + 3x2 <= 6,  x1 <= 3.5,  x >= 0
c = np.array([3.0, 2.0])
A = np.array([[1.0, 1.0], [1.0, 3.0], [1.0, 0.0]])
b = np.array([4.0, 6.0, 3.5])
res = linprog(-c, A_ub=A, b_ub=b, bounds=[(0, None)] * 2, method="highs")
x = res.x
y = -res.ineqlin.marginals          # dual prices (HiGHS reports d(min)/db)
print("primal x =", x, " value =", c @ x)
print("dual   y =", y, " value =", b @ y)
print("slack b - Ax =", b - A @ x, " y * slack =", y * (b - A @ x))
print("reduced costs A^T y - c =", A.T @ y - c)

The solver returns the primal and dual solutions of Example 0.7, and every complementary product is zero.

0.3 Integer programs and complexity

The whole of ch. 4–5 is about making z_{LP} close to z_{IP} (strong formulations, cuts) and exploiting the gap (branch-and-bound).

Unless P = NP, an NP-hard problem has no polynomial algorithm. Deciding whether a MILP is feasible is NP-hard, and so are most network problems with integer decisions: the knapsack problem behind capacity upgrades (ch. 5.1), the Steiner tree problem behind network design (ch. 4.1), integer multicommodity flow (ch. 2.4) and the facility location problems of ch. 6 (Garey and Johnson, 1979).

NP-hardness is a worst-case statement. Modern solvers routinely solve network instances with thousands of binary variables, and the exact methods of ch. 5 exploit structure to go further. When the time budget is seconds, heuristics take over (ch. 7–10).

1. Telecommunication networks and their optimization problems

An optimization model of a network needs four ingredients: a graph with capacities, a traffic to carry, a set of routing rules and a time scale for the decision. This chapter introduces them, with only the networking vocabulary the models use.

1.1 Layers, links and capacities

A backbone network is built in layers. The optical layer carries wavelengths on fibres (wavelength-division multiplexing, WDM). The IP/MPLS layer sees each wavelength, or each bundle of them, as one link between two routers.

Capacity is installed in modules: interfaces of 10, 100 or 400 Gb/s, wavelengths, fibre pairs. Its cost is therefore a step function of the volume, which is why capacity planning is an integer problem (ch. 4.4).

1.2 Traffic matrices

Traffic matrices are rarely measured directly; they are estimated from link counts and sampled flows. The simplest model, often used as a prior, is the gravity model.

1.3 Routing

How traffic follows the links depends on the technology.

• Shortest-path protocols (OSPF, IS-IS) give each link an administrative weight; every router forwards a packet along a shortest path to its destination. With ECMP (equal-cost multipath), traffic is split evenly among equal-length next hops. The operator controls the routing only through the weights (ch. 3.3).
• Explicit routing (MPLS traffic engineering, segment routing) lets the operator choose the path of each flow, possibly with a few waypoints (ch. 3.4).
• Software-defined networking (SDN) separates the control plane from the forwarding plane: a logically centralised controller computes the routes and installs them in the switches (McKeown et al., 2008). Where to place the controllers is itself a problem (ch. 6.2).

The quality of a routing is first measured by the utilisation of each link, load divided by capacity. Queueing delay grows quickly as utilisation approaches 1, so operators keep headroom below full load.

import numpy as np, networkx as nx
links = [("A", "B", 10), ("A", "C", 10), ("B", "C", 5), ("B", "D", 10),
         ("C", "E", 5), ("D", "E", 10), ("D", "F", 10), ("E", "F", 10)]      # Gb/s
G = nx.DiGraph([(u, v, {"cap": c}) for u, v, c in links] + [(v, u, {"cap": c}) for u, v, c in links])
nodes, P = sorted(G), {"A": 4, "B": 2, "C": 2, "D": 2, "E": 2, "F": 4}
Z = sum(P[s] * P[t] for s in nodes for t in nodes if s != t)
T = {(s, t): 40 * P[s] * P[t] / Z for s in nodes for t in nodes if s != t}  # gravity, 40 Gb/s

# Route every demand on one minimum-hop path and accumulate the load of each arc.
load = dict.fromkeys(G.edges, 0.0)
for (s, t), d in T.items():
    path = nx.shortest_path(G, s, t)                    # fewest hops, first one found
    for a in zip(path, path[1:]):
        load[a] += d
util = {a: load[a] / G.edges[a]["cap"] for a in G.edges}
worst = max(util, key=util.get)
print("T[A,F] = %.2f Gb/s, T[B,C] = %.2f Gb/s, total %.0f Gb/s" % (T["A", "F"], T["B", "C"], sum(T.values())))
print("most loaded arc", worst, "utilisation %.2f" % util[worst])

The first lines of this block define the backbone; later blocks repeat them so that each one runs on its own. With one minimum-hop path per demand, the arc C→E carries 4.6 Gb/s on 5 Gb/s:

\text{maximum utilisation} = 0.92 .

Chapter 3 shows that a better routing of the same traffic exists, and how to prove that it is optimal.

1.4 Virtualization and autonomy

Three evolutions change the optimization problems.

• Network functions virtualization (NFV) replaces dedicated boxes (firewalls, load balancers, packet gateways) by software, the virtual network functions (VNFs), running on servers in data centres. A service becomes a service function chain: an ordered list of VNFs that a flow must traverse (ch. 6.3).
• Network slicing, central in 5G, shares one physical network among several logical networks, each with its own guarantees of throughput, latency or reliability (ch. 8.2).
• Autonomous networks close the loop: monitoring, analysis, decision and configuration run without a human operator, so decisions must be computed in seconds or less (ch. 8.4).

1.5 Three time scales of decisions

The objectives also vary: installation cost, maximum utilisation, latency, energy, robustness to failures. A good model states which one matters and turns the others into constraints.

2. Flows, paths and cuts

Routing is a flow problem. This chapter solves the single-commodity problems in polynomial time, explains why their solutions are integral, and shows what breaks when several commodities share the capacities.

2.1 Shortest paths

With negative lengths but no negative cycle, the Bellman–Ford algorithm relaxes every arc n - 1 times; a further improvement reveals a negative cycle.

The shortest path problem is also an LP: send one unit from s to t at minimum cost, \min \{ w^\top x : N x = e_s - e_t,\ x \geq 0 \}. Its dual has one potential \pi_v per node: \max \ \pi_s - \pi_t \quad \text{s.t.} \quad \pi_u - \pi_v \leq w_{uv} \ \text{ for every arc } (u, v). Distances to t are optimal potentials. Pricing in column generation (ch. 5.4) is exactly this problem.

2.2 Maximum flow and minimum cut

Augmenting along shortest residual paths (Edmonds and Karp, 1972) terminates after at most nm augmentations, whatever the capacities.

2.3 Total unimodularity and minimum-cost flows

So single-commodity problems with integer data are solved by linear programming, with integral answers for free. Maximum flow, shortest paths, transportation and assignment are all special cases.

import numpy as np, networkx as nx
links = [("A", "B", 10), ("A", "C", 10), ("B", "C", 5), ("B", "D", 10),
         ("C", "E", 5), ("D", "E", 10), ("D", "F", 10), ("E", "F", 10)]      # Gb/s
G = nx.DiGraph([(u, v, {"cap": c}) for u, v, c in links] + [(v, u, {"cap": c}) for u, v, c in links])
ms = {("A", "B"): 2, ("A", "C"): 3, ("B", "C"): 1, ("B", "D"): 4,
      ("C", "E"): 2, ("D", "E"): 1, ("D", "F"): 2, ("E", "F"): 3}          # latency (ms)
for (u, v), w in ms.items():
    G.edges[u, v]["w"] = G.edges[v, u]["w"] = w

print("Dijkstra A->F:", nx.dijkstra_path(G, "A", "F", weight="w"),
      nx.dijkstra_path_length(G, "A", "F", weight="w"), "ms")
value, flow = nx.maximum_flow(G, "A", "F", capacity="cap")
cut_value, (S, Sbar) = nx.minimum_cut(G, "A", "F", capacity="cap")
print("max flow A->F =", value, "| min cut", sorted((u, v) for u in S for v in G[u] if v in Sbar), cut_value)

# Minimum-cost flow: 12 Gb/s from A to F, cost = latency x volume.
G.nodes["A"]["demand"], G.nodes["F"]["demand"] = -12, 12
f = nx.min_cost_flow(G, capacity="cap", weight="w")
print("min cost =", nx.cost_of_flow(G, f, weight="w"),
      "| integral:", all(float(x).is_integer() for u in f for x in f[u].values()))

2.4 Multicommodity flows

A network carries many demands at once, and they share the capacities. Let K be the set of demands of Definition 1.1.

Integrality is lost with several commodities: the constraint matrix is no longer TU, and the LP optimum can split a demand over paths with fractional volumes. Finding an integral multicommodity flow is NP-hard already with two commodities (Even, Itai and Shamir, 1976), and so is routing each demand on a single path (the unsplittable flow problem).

Feasibility is also subtler. The cut condition, that every cut has at least the capacity of the demands crossing it, is necessary but not sufficient. On the complete bipartite graph between \{a_1, a_2\} and \{b_1, b_2, b_3\}, with unit undirected capacities and unit demands a_1 a_2, b_1 b_2, b_2 b_3, b_1 b_3, every cut satisfies it. Yet each demand needs a path of two edges, 8 units in total for 6 available: only 75 % of each demand can be routed.

The theorem is the bridge between routing and dimensioning: it describes the capacity vectors that can carry a traffic matrix without mentioning flows, which ch. 4.5 and Benders decomposition (ch. 5.5) exploit.

3. Traffic engineering: routing the flows

Traffic engineering (TE) chooses how the traffic matrix is routed on a given network, so that no link is congested. This chapter states the usual objectives, solves the splittable problem by linear programming with a dual certificate, and then studies the routings that protocols can actually implement.

3.1 Congestion objectives

Let \ell_a be the load of arc a, the total flow of all demands on it, and u_a = \ell_a / c_a its utilisation.

• Maximum link utilisation (MLU): minimise \max_a u_a. It keeps headroom for traffic surges and is a common objective of TE studies.
• Delay-like convex costs: the M/M/1 queueing approximation gives a mean delay proportional to \sum_a \ell_a / (c_a - \ell_a), which explodes near saturation.
• Piecewise-linear costs: Fortz and Thorup (2000) charge each arc c_a \, \phi(u_a), where \phi is convex with slopes 1, 3, 10, 70, 500 and 5000 on the utilisation intervals cut at 1/3, 2/3, 9/10, 1 and 11/10.

3.2 Minimum maximum utilisation and its dual

For a splittable objective, demands with the same origin can be merged into one commodity with several sinks. This reduces the number of flow vectors from |K| to n, which is what the code below does.

The optimal dual lengths \mu are the shadow prices of the capacities: they say which links limit the network. As long as the same dual stays optimal, one more Gb/s on arc a lowers U^\star at the rate U^\star \mu_a.

import numpy as np, networkx as nx
from scipy.optimize import linprog
links = [("A", "B", 10), ("A", "C", 10), ("B", "C", 5), ("B", "D", 10),
         ("C", "E", 5), ("D", "E", 10), ("D", "F", 10), ("E", "F", 10)]      # Gb/s
G = nx.DiGraph([(u, v, {"cap": c}) for u, v, c in links] + [(v, u, {"cap": c}) for u, v, c in links])
nodes, P = sorted(G), {"A": 4, "B": 2, "C": 2, "D": 2, "E": 2, "F": 4}
Z = sum(P[s] * P[t] for s in nodes for t in nodes if s != t)
T = {(s, t): 40 * P[s] * P[t] / Z for s in nodes for t in nodes if s != t}  # gravity, 40 Gb/s
arcs = list(G.edges); m, n = len(arcs), len(nodes)

# (a) Minimum maximum utilisation, splittable: flows aggregated by source, f[s, a] >= 0, plus U.
nv = n * m + 1
c = np.zeros(nv); c[-1] = 1.0
A_eq = np.zeros((n * n, nv)); b_eq = np.zeros(n * n)
for i, s in enumerate(nodes):
    for j, v in enumerate(nodes):
        for q, (a, b) in enumerate(arcs):
            A_eq[i * n + j, i * m + q] = (a == v) - (b == v)       # out minus in
        b_eq[i * n + j] = sum(T[s, t] for t in nodes if t != s) if v == s else -T.get((s, v), 0)
A_ub = np.zeros((m, nv))
for q, a in enumerate(arcs):
    A_ub[q, q:n * m:m] = 1.0; A_ub[q, -1] = -G.edges[a]["cap"]     # load_a <= U * c_a
r = linprog(c, A_ub=A_ub, b_ub=np.zeros(m), A_eq=A_eq, b_eq=b_eq, method="highs")
mu = -r.ineqlin.marginals                                          # dual "lengths" of the arcs
print("LP optimum U* = %.3f | arcs with a positive dual:" % r.fun,
      [(arcs[q], round(float(mu[q]), 3)) for q in range(m) if mu[q] > 1e-9])

# (b) Shortest-path routing with unit weights and even splitting (ECMP).
def ecmp_load(w):
    load = dict.fromkeys(arcs, 0.0)
    for t in nodes:                                                # one destination at a time
        dist = nx.shortest_path_length(G.reverse(), t, weight=lambda u, v, d: w[v, u])
        inflow = {v: T.get((v, t), 0.0) for v in nodes}
        for v in sorted(nodes, key=lambda v: -dist[v]):           # farthest nodes first
            nxt = [(v, u) for u in G[v] if v != t and abs(dist[v] - w[v, u] - dist[u]) < 1e-9]
            for a in nxt:
                load[a] += inflow[v] / len(nxt); inflow[a[1]] += inflow[v] / len(nxt)
    return load
L = ecmp_load(dict.fromkeys(arcs, 1))
worst = max(arcs, key=lambda a: L[a] / G.edges[a]["cap"])
print("ECMP, unit weights: arc", worst, "utilisation %.3f" % (L[worst] / G.edges[worst]["cap"]))

3.3 Shortest-path routing and the weight-setting problem

With OSPF or IS-IS, the operator does not choose paths: it chooses weights, and the protocol routes every packet on shortest paths for these weights, splitting evenly among equal-cost next hops (ECMP).

Fortz and Thorup proved that finding optimal weights is NP-hard, and showed that local search on the weights comes close to the LP optimum on the backbones they studied (Fortz and Thorup, 2000; 2004). Not every routing is reachable this way.

On the backbone, unit weights send through the 5 Gb/s arc C→E all of the demands A→E, C→E and C→F, and half of A→F, B→E and C→D, that is 6.15 Gb/s. The block above confirms it: \text{ECMP with unit weights:}\quad u_{CE} = 1.231 . Even splitting is worse here than a single path (0.92, ch. 1). Ch. 7.3 tunes the weights by local search.

Complementary slackness explains why weights are powerful. In the min-cost multicommodity LP with capacity duals \pi_a \geq 0, every path carrying flow in an optimal solution is a shortest path for the lengths w_a + \pi_a. Wang, Wang and Zhang (2001) used this to show that optimal routings are shortest-path routings for suitable weights, provided the splitting ratios can be set freely rather than evenly.

3.4 Explicit routing and segment routing

MPLS traffic engineering sets up label-switched paths chosen by the operator. If each demand must follow a single path chosen among a candidate set \mathcal{P}_k (for instance its q shortest paths), the problem becomes a MILP with binary variables z_p: \sum_{p \in \mathcal{P}_k} z_p = 1 \ (k \in K), \qquad \sum_k \sum_{p \in \mathcal{P}_k : a \in p} d_k z_p \leq U c_a \ (a \in A). This is the unsplittable flow problem of ch. 2.4, NP-hard but solved well in practice for moderate sizes, or by rounding (ch. 7.2).

Segment routing (Filsfils et al., 2015) encodes a path as a short list of waypoints; between consecutive waypoints, packets follow the ECMP shortest paths of the protocol. With at most one intermediate waypoint per demand, TE stays an LP.

Bhatia and coauthors (2015) give such LPs for known and for uncertain traffic, and report maximum utilisations close to that of the fully splittable LP in their experiments.

4. Network design and capacity planning

Design decides which links to build; capacity planning decides how many modules to install on them. Both add integer variables to the flow models of ch. 2, and the quality of the formulation, not only its correctness, decides whether a solver can handle it.

4.1 Fixed-charge network design

Let E be a set of candidate links, each with an opening cost f_e and a capacity c_e per direction; arc a belongs to link e(a).

The problem is NP-hard: with zero routing costs, large capacities and demands from one root to a set of terminals, an optimal design is a minimum Steiner tree connecting them.

4.2 Strong and weak formulations

Two formulations with the same integer solutions can have very different LP relaxations. A demand that uses a fraction of a link only needs a fraction of its opening in the weak formulation.

import itertools, time
import numpy as np
from scipy.optimize import milp, LinearConstraint, Bounds
from scipy.sparse import lil_matrix

# Fixed-charge network design on 8 sites: which of the 28 candidate links to open?
rng = np.random.default_rng(1)
n = 8; xy = rng.uniform(0, 100, size=(n, 2))
E = list(itertools.combinations(range(n), 2))                       # candidate links
A = E + [(j, i) for i, j in E]                                      # both directions
length = {(i, j): np.linalg.norm(xy[i] - xy[j]) for i, j in A}
K = [(0, 7, 6), (1, 6, 4), (2, 5, 5), (3, 4, 3), (0, 5, 4), (6, 3, 2), (1, 2, 5), (4, 7, 3)]
cap, fixed = 10.0, 10.0                 # module capacity (Gb/s) and cost per km of an opened link

def model(strong):
    nx_, ny = len(A) * len(K), len(E)
    nv = nx_ + ny
    c = np.zeros(nv)
    for q, a in enumerate(A):
        for k in range(len(K)): c[k * len(A) + q] = 0.1 * length[a]   # routing cost per Gb/s
    c[nx_:] = [fixed * length[e] for e in E]
    rows_eq, beq = lil_matrix((len(K) * n, nv)), []
    for k, (s, t, d) in enumerate(K):
        for v in range(n):
            for q, (i, j) in enumerate(A):
                if i == v: rows_eq[k * n + v, k * len(A) + q] = 1
                if j == v: rows_eq[k * n + v, k * len(A) + q] = -1
            beq.append(d * ((v == s) - (v == t)))
    ub = []
    for q, (i, j) in enumerate(A):                                  # sum_k x_a^k <= cap * y_e
        e = E.index((min(i, j), max(i, j)))
        r = np.zeros(nv); r[[k * len(A) + q for k in range(len(K))]] = 1; r[nx_ + e] = -cap; ub.append(r)
        if strong:                                                  # x_a^k <= d_k * y_e
            for k, (_, _, d) in enumerate(K):
                r = np.zeros(nv); r[k * len(A) + q] = 1; r[nx_ + e] = -d; ub.append(r)
    cons = [LinearConstraint(rows_eq.tocsr(), beq, beq), LinearConstraint(np.array(ub), -np.inf, 0)]
    integ = np.r_[np.zeros(nx_), np.ones(ny)]
    lb, ubd = np.zeros(nv), np.r_[np.full(nx_, np.inf), np.ones(ny)]
    lp = milp(c, constraints=cons, integrality=np.zeros(nv), bounds=Bounds(lb, ubd))
    t0 = time.perf_counter()
    ip = milp(c, constraints=cons, integrality=integ, bounds=Bounds(lb, ubd))
    return lp.fun, ip.fun, ip.mip_node_count, time.perf_counter() - t0, int(round(ip.x[nx_:].sum()))

for strong in (False, True):
    lp, ip, nodes, sec, opened = model(strong)
    print("%-6s LP bound %7.1f | optimum %7.1f | gap %4.1f%% | B&B nodes %4d | %.2f s | links opened %d"
          % ("strong" if strong else "weak", lp, ip, 100 * (ip - lp) / ip, nodes, sec, opened))

4.3 A modelling toolbox

Real requirements are logical as much as linear. The standard linearisations, with binary y, y', continuous 0 \leq x \leq M and a constant M bounding x:

Big-M constraints are correct for any valid M but weak when M is large: the relaxation can set y = x / M, close to zero. Use the smallest valid bound, here the demand or the capacity, as in Definition 4.2.

4.4 Modular capacities and cut-set inequalities

In capacity planning the network exists; the question is how many modules to install. With an integer number y_e \geq 0 of modules of capacity C on each link (shared by both directions here) and cost \kappa_e per module, the network loading problem is \min \sum_{e} \kappa_e y_e \quad \text{s.t.} \quad \text{flows carry } T, \qquad \sum_{k} (x^k_{uv} + x^k_{vu}) \leq C y_e \ \ (e = uv),\ y_e \in \mathbb{Z}_{\geq 0}.

Its LP relaxation installs fractional modules exactly where needed and is weak. The classic remedy is to add cuts.

On the backbone with C = 10 Gb/s and S = \{A, B, C\}, the demand across is 2 \times 12.31 = 24.6 Gb/s. The LP relaxation can install 2.46 modules on the cut; the inequality demands 3. Barahona (1996) and Bienstock and coauthors (1998) used cut-set inequalities and their extensions to strengthen the relaxation of network loading problems substantially.

4.5 Metric inequalities and multi-period planning

Theorem 2.12 removes the flows altogether. With capacities shared by both directions, it holds with one length \mu_e per link and the same proof. A capacity vector C y carries the traffic if and only if \sum_{e} \mu_e \, C y_e \geq \sum_{k} d_k \, \mathrm{dist}_\mu(s_k, t_k) \qquad \text{for all } \mu \geq 0 . The capacity formulation minimises the module cost subject to these metric inequalities and integrality. There are infinitely many of them, but given y a violated one is found by solving one multicommodity LP: this is Benders decomposition (ch. 5.5).

Planning is also dynamic. With forecast traffic matrices T^1, \dots, T^H for successive periods, modules installed earlier remain, so the cumulative capacities satisfy y^h_e \geq y^{h-1}_e, and the cost of period h is discounted. Delaying an installation saves money but risks congestion if the forecast is wrong, a trade-off revisited with robust models in ch. 9.2.

5. Exact methods: branch-and-bound, cutting planes and decomposition

A solver call hides several algorithms. This chapter opens the box: it enumerates cleverly (branch-and-bound), tightens the relaxation (cutting planes), and splits large models into easy pieces (Lagrangian relaxation, column generation, Benders decomposition), each on a network problem.

5.1 Branch-and-bound

The search order matters. Depth-first search finds feasible solutions quickly and uses little memory; best-bound search processes the node of smallest LP value and minimises the number of nodes. Solvers mix both, and choose the branching variable by estimating the bound improvement (strong branching, pseudo-costs), a step that ch. 10.2 learns.

import numpy as np
# Depth-first branch-and-bound for a 0-1 knapsack: choose link upgrades (value v, price w)
# within a budget W. The bound at a node is the LP relaxation, solved greedily (Dantzig).
rng = np.random.default_rng(4)
n = 30; v = rng.integers(10, 60, n).astype(float); w = rng.integers(5, 40, n).astype(float)
W = 0.4 * w.sum()
order = np.argsort(-v / w); v, w = v[order], w[order]        # sort by value per unit of budget

def lp_bound(i, cap, val):
    """Value of the LP relaxation over items i.. with remaining budget cap."""
    while i < n and w[i] <= cap:
        cap -= w[i]; val += v[i]; i += 1
    return val + (v[i] * cap / w[i] if i < n else 0.0)

best, nodes = 0.0, 0
stack = [(0, W, 0.0)]                                        # (next item, budget left, value)
while stack:
    i, cap, val = stack.pop(); nodes += 1
    best = max(best, val)
    if i == n or lp_bound(i, cap, val) <= best:              # prune by bound
        continue
    stack.append((i + 1, cap, val))                          # branch x_i = 0
    if w[i] <= cap:
        stack.append((i + 1, cap - w[i], val + v[i]))        # branch x_i = 1 (explored first)
print("optimum %.0f | root LP bound %.1f | nodes explored %d of 2^%d = %d"
      % (best, lp_bound(0, W, 0.0), nodes, n, 2 ** n))

The knapsack models a budget of link upgrades, each with a value and a price. Thirty items have about 10^9 subsets; with a root bound only 0.7 % above the optimum, branch-and-bound explores 118 nodes and proves the optimum, 761.

5.2 Cutting planes and branch-and-cut

Gomory’s fractional cut applies this rounding to a row of the optimal simplex tableau, and is violated by the current vertex. For a capacity row with binary variables, \sum_j a_j y_j \leq b, a cover is a set J with \sum_{j \in J} a_j > b; the inequality \sum_{j \in J} y_j \leq |J| - 1 is valid, since not all of J fits. The cut-set inequalities of Proposition 4.5 are problem-specific cuts.

Branch-and-cut separates cuts at the nodes of the tree. Together with presolve and primal heuristics, it is what modern solvers do: HiGHS (used here), SCIP, CPLEX and Gurobi.

5.3 Lagrangian relaxation

Some constraints link otherwise independent subproblems. In multicommodity flows, only the capacity constraints couple the demands.

L is concave and piecewise linear. If x_\lambda minimises the Lagrangian at \lambda, the violation g = A x_\lambda - b is a subgradient: L(\lambda') \leq L(\lambda) + g^\top (\lambda' - \lambda) \quad \text{for all } \lambda' \geq 0 . The projected subgradient method updates \lambda \leftarrow \max(0, \lambda + t_k g) with steps t_k \to 0 and \sum_k t_k = \infty. When the subgradients are bounded, the best value found converges to z_{LD}.

Relaxing the capacities of the min-cost multicommodity flow with multipliers \pi_a leaves one shortest-path problem per demand, for the lengths w_a + \pi_a. The multipliers act as congestion tolls.

import numpy as np, networkx as nx
links = [("A", "B", 10), ("A", "C", 10), ("B", "C", 5), ("B", "D", 10),
         ("C", "E", 5), ("D", "E", 10), ("D", "F", 10), ("E", "F", 10)]      # Gb/s
G = nx.DiGraph([(u, v, {"cap": c}) for u, v, c in links] + [(v, u, {"cap": c}) for u, v, c in links])
nodes, P = sorted(G), {"A": 4, "B": 2, "C": 2, "D": 2, "E": 2, "F": 4}
Z = sum(P[s] * P[t] for s in nodes for t in nodes if s != t)
T = {(s, t): 40 * P[s] * P[t] / Z for s in nodes for t in nodes if s != t}  # gravity, 40 Gb/s
ms = {("A", "B"): 2, ("A", "C"): 3, ("B", "C"): 1, ("B", "D"): 4,
      ("C", "E"): 2, ("D", "E"): 1, ("D", "F"): 2, ("E", "F"): 3}          # latency (ms)
for (u, v), w in ms.items():
    G.edges[u, v]["w"] = G.edges[v, u]["w"] = w
arcs = list(G.edges); cap = np.array([G.edges[a]["cap"] for a in arcs])

# Relax the capacity constraints with multipliers pi >= 0: the relaxed problem splits
# into one shortest-path problem per demand, for the arc lengths w + pi.
pi, best = np.zeros(len(arcs)), -np.inf
for k in range(300):
    for a, p in zip(arcs, pi):
        G.edges[a]["red"] = G.edges[a]["w"] + p
    load, value = np.zeros(len(arcs)), -pi @ cap
    for (s, t), d in T.items():
        path = nx.shortest_path(G, s, t, weight="red")
        value += d * nx.path_weight(G, path, "red")
        for a in zip(path, path[1:]):
            load[arcs.index(a)] += d
    best = max(best, value)                      # every L(pi) is a lower bound
    pi = np.maximum(0.0, pi + (load - cap) / (k + 1))   # projected subgradient step
print("best Lagrangian bound after 300 steps: %.3f" % best)

The subproblem is a set of shortest paths, which have integral LP solutions, so Theorem 5.6 predicts that the best bound is the LP optimum of the min-cost multicommodity flow; the next block computes it, 170.769, and the subgradient method reaches it within 300 steps.

5.4 Column generation

The arc-path formulation (Definition 2.10) has one variable per path. Column generation works with a small subset of paths, the restricted master problem, and adds the paths that can improve it.

import numpy as np, networkx as nx
from scipy.optimize import linprog
links = [("A", "B", 10), ("A", "C", 10), ("B", "C", 5), ("B", "D", 10),
         ("C", "E", 5), ("D", "E", 10), ("D", "F", 10), ("E", "F", 10)]      # Gb/s
G = nx.DiGraph([(u, v, {"cap": c}) for u, v, c in links] + [(v, u, {"cap": c}) for u, v, c in links])
nodes, P = sorted(G), {"A": 4, "B": 2, "C": 2, "D": 2, "E": 2, "F": 4}
Z = sum(P[s] * P[t] for s in nodes for t in nodes if s != t)
T = {(s, t): 40 * P[s] * P[t] / Z for s in nodes for t in nodes if s != t}  # gravity, 40 Gb/s
ms = {("A", "B"): 2, ("A", "C"): 3, ("B", "C"): 1, ("B", "D"): 4,
      ("C", "E"): 2, ("D", "E"): 1, ("D", "F"): 2, ("E", "F"): 3}          # latency (ms)
for (u, v), w in ms.items():
    G.edges[u, v]["w"] = G.edges[v, u]["w"] = w
arcs, K = list(G.edges), list(T)
cap = [G.edges[a]["cap"] for a in arcs]

# Restricted master: path variables x_p, one artificial variable per demand (cost M).
cols = [(k, tuple(nx.shortest_path(G, *k, weight="w"))) for k in K]
for it in range(1, 50):
    n = len(cols)
    cost = [nx.path_weight(G, p, "w") for _, p in cols] + [1e3] * len(K)
    A_eq = np.hstack([np.array([[k == kk for kk, _ in cols] for k in K], float), np.eye(len(K))])
    A_ub = np.hstack([np.array([[a in set(zip(p, p[1:])) for _, p in cols] for a in arcs], float),
                      np.zeros((len(arcs), len(K)))])
    r = linprog(cost, A_ub=A_ub, b_ub=cap, A_eq=A_eq, b_eq=[T[k] for k in K], method="highs")
    u, pi = r.eqlin.marginals, -r.ineqlin.marginals          # duals: demands, capacities
    for a, p in zip(arcs, pi):
        G.edges[a]["red"] = G.edges[a]["w"] + p
    new = [(k, tuple(nx.shortest_path(G, *k, weight="red"))) for k in K]     # pricing
    new = [(k, p) for i, (k, p) in enumerate(new) if nx.path_weight(G, p, "red") < u[i] - 1e-9]
    if not new:
        break
    cols += new
print("column generation: %d master solves, %d paths, cost %.3f" % (it, len(cols), r.fun))

Starting from one shortest path per demand, the artificial variables absorb what the capacities refuse; the duals then price the congested arcs, pricing adds 10 detours, and the second master is optimal: 40 paths and the cost 170.769 of the 480-variable arc-node LP. When paths must be integral (unsplittable routing), column generation is embedded in branch-and-bound: branch-and-price (Barnhart et al., 1998).

5.5 Benders decomposition

In capacity planning, fixing the capacities y leaves a pure routing LP. Benders (1962) keeps y in a master problem and lets the routing subproblem return cuts.

The algorithm alternates: solve the master (minimise \sum_e \kappa_e y_e over integer y subject to the cuts found so far), test the routing, add a cut if infeasible. When routing costs matter, optimality cuts built from the dual of the routing LP are added as well. Each cut corresponds to an extreme ray or point of a fixed dual polyhedron, so finitely many cuts suffice. Costa (2005) surveys Benders decomposition for fixed-charge network design.

6. Placement of network components

Where should controllers, caches, gateways or virtual functions run? Placement problems are facility location problems on a graph, sometimes coupled with routing. This chapter formulates them and compares exact and greedy solutions.

6.1 Facility location

Let I be the clients (switches, users, traffic sources), J the candidate sites and d_{ij} the cost of serving i from j, typically a latency.

All three are NP-hard on general graphs. The constraint z_{ij} \leq y_j is the strong form of linking, as in Definition 4.2; it makes the LP relaxation of the p-median often integral or nearly so on practical instances.

6.2 Controller placement in SDN

In a software-defined network, each switch talks to a controller. Heller, Sherwood and McKeown (2012) posed the controller placement problem: average latency leads to the p-median, worst-case latency to the p-center.

The simplest heuristic adds sites one at a time, each time the one that reduces the cost most. Its quality is understood through submodularity.

A set function g is submodular when an element adds less to a larger set: for S \subseteq S' and j \notin S', g(S \cup \{j\}) - g(S) \geq g(S' \cup \{j\}) - g(S') .

The guarantee is on savings, not on the cost itself; in practice greedy is often within a few per cent of the optimum. A swap-based local search (ch. 7.3) may improve it, but not always: Exercise 13 shows a greedy solution that no single swap improves.

import numpy as np, networkx as nx
from scipy.optimize import milp, LinearConstraint, Bounds
from scipy.sparse import coo_matrix

# Controller placement as a p-median problem on a random geometric topology of 30 switches.
G = nx.random_geometric_graph(30, 0.3, seed=5)
for u, v in G.edges:
    G.edges[u, v]["ms"] = 10 * np.hypot(*np.subtract(G.nodes[u]["pos"], G.nodes[v]["pos"]))
D = nx.floyd_warshall_numpy(G, weight="ms")          # switch-to-switch latency (ms)
n, p = len(D), 3

def p_median(D, p, cand):
    """min sum_ij D_ij z_ij  s.t.  sum_j z_ij = 1,  sum_j y_j = p,  z_ij <= y_j  (sites in cand)."""
    n, m = len(D), len(cand); nv = n * m + m
    z = np.arange(n * m).reshape(n, m); y = n * m + np.arange(m)
    assign = coo_matrix((np.ones(n * m), (np.repeat(np.arange(n), m), z.ravel())), (n, nv))
    count = coo_matrix((np.ones(m), (np.zeros(m, int), y)), (1, nv))
    link = coo_matrix((np.r_[np.ones(n * m), -np.ones(n * m)],
                       (np.r_[z.ravel(), z.ravel()], np.r_[z.ravel(), np.tile(y, n)])), (n * m, nv))
    cons = [LinearConstraint(assign, 1, 1), LinearConstraint(count, p, p), LinearConstraint(link, -np.inf, 0)]
    r = milp(np.r_[D[:, cand].ravel(), np.zeros(m)], constraints=cons,
             integrality=np.r_[np.zeros(n * m), np.ones(m)], bounds=Bounds(0, 1))
    return r.fun, sorted(cand[j] for j in range(m) if r.x[y[j]] > 0.5)

opt, sites = p_median(D, p, list(range(n)))
chosen = []                                           # greedy: add the site that helps most
for _ in range(p):
    chosen.append(min((j for j in range(n) if j not in chosen),
                      key=lambda j: D[:, chosen + [j]].min(1).sum()))
greedy = D[:, chosen].min(1).sum()
print("optimum: sites %s, mean latency %.2f ms, worst %.2f ms" % (sites, opt / n, D[:, sites].min(1).max()))
print("greedy:  sites %s, mean latency %.2f ms (ratio %.3f)" % (sorted(chosen), greedy / n, greedy / opt))

6.3 VNF placement and service function chains

A service function chain is an ordered list of functions (f_1, \dots, f_L) that the traffic of a request must traverse, for instance firewall, then load balancer, then cache. Each node v offers a compute capacity R_v (cores), each function f consumes r_f per instance, and links have capacities.

The joint problem, placement plus routing with capacities, is NP-hard; MILPs solve instances of tens of nodes, and heuristics or decompositions handle larger ones (Herrera and Botero, 2016, survey the field).

6.4 Virtual network embedding

A slice or a tenant may ask for a whole virtual network: virtual nodes with compute demands, virtual links with bandwidth demands. Virtual network embedding maps virtual nodes to distinct physical nodes and virtual links to physical paths, within capacities, at minimum cost. It contains the unsplittable flow problem and is NP-hard (Fischer et al., 2013, survey it).

• Two-stage heuristics map nodes first, greedily on available capacity, then route the links by shortest paths or multicommodity flows.
• Coordinated mapping solves a relaxation of the joint MILP and rounds it (Chowdhury, Rahman and Boutaba, 2009).
• Path splitting, when the substrate allows it, turns link mapping into an LP and raises the acceptance rate (Yu et al., 2008).

7. Heuristics and matheuristics

When the instance is too large or the time budget too short for an exact method, a heuristic returns a good solution without proof of optimality. This chapter builds heuristics for the problems of ch. 3–6 and insists on measuring their quality against a bound.

7.1 Measuring a heuristic

A heuristic value z_H means little alone. Three measures make it informative:

• the gap to a lower bound z_{LB} (LP, Lagrangian, cut bound), (z_H - z_{LB}) / z_H, which bounds the distance to the unknown optimum;
• the running time, or the time needed to reach a target quality;
• the variability over seeds and over instances of the same family, reported as a distribution, not a single best run.

A test set should contain instances of several sizes and structures, for example from SNDlib (Orlowski et al., 2010) or the Internet Topology Zoo (Knight et al., 2011), never only the instances used to tune parameters.

7.2 Constructive heuristics and rounding

Greedy algorithms build a solution step by step, choosing the locally best move: open the site with the largest saving (ch. 6.2), route demands one by one on the shortest path with enough residual capacity, largest demands first.

LP rounding solves the relaxation and rounds it. For unsplittable routing, Raghavan and Thompson (1987) choose for each demand one path at random, with the probabilities given by the path flows of the LP solution.

In practice, rounding is followed by a repair step and a local search, and repeated with several seeds.

7.3 Local search and metaheuristics

Metaheuristics escape local optima in different ways.

• Simulated annealing (Kirkpatrick, Gelatt and Vecchi, 1983) accepts a worse neighbour with probability e^{-\Delta / \theta}, where \Delta is the deterioration and the temperature \theta decreases over time.
• Tabu search (Glover, 1989) moves to the best neighbour even if it is worse, and forbids undoing recent moves for a number of iterations.
• GRASP (Feo and Resende, 1995) repeats a randomised greedy construction followed by local search, and keeps the best result.

For the weight-setting problem of Definition 3.5, Fortz and Thorup (2000) used a local search whose basic move changes one weight, evaluated with the cost \phi. A minimal version follows.

import numpy as np, networkx as nx
links = [("A", "B", 10), ("A", "C", 10), ("B", "C", 5), ("B", "D", 10),
         ("C", "E", 5), ("D", "E", 10), ("D", "F", 10), ("E", "F", 10)]      # Gb/s
G = nx.DiGraph([(u, v, {"cap": c}) for u, v, c in links] + [(v, u, {"cap": c}) for u, v, c in links])
nodes, P = sorted(G), {"A": 4, "B": 2, "C": 2, "D": 2, "E": 2, "F": 4}
Z = sum(P[s] * P[t] for s in nodes for t in nodes if s != t)
T = {(s, t): 40 * P[s] * P[t] / Z for s in nodes for t in nodes if s != t}  # gravity, 40 Gb/s
arcs, rng = list(G.edges), np.random.default_rng(0)

def ecmp_load(w):                                   # as in ch. 3
    load = dict.fromkeys(arcs, 0.0)
    for t in nodes:
        dist = nx.shortest_path_length(G.reverse(), t, weight=lambda u, v, d: w[v, u])
        inflow = {v: T.get((v, t), 0.0) for v in nodes}
        for v in sorted(nodes, key=lambda v: -dist[v]):
            nxt = [(v, u) for u in G[v] if v != t and abs(dist[v] - w[v, u] - dist[u]) < 1e-9]
            for a in nxt:
                load[a] += inflow[v] / len(nxt); inflow[a[1]] += inflow[v] / len(nxt)
    return load

def phi(x):                                         # Fortz-Thorup cost per unit of capacity
    bp, slope = [0, 1/3, 2/3, 0.9, 1, 1.1, np.inf], [1, 3, 10, 70, 500, 5000]
    return sum(s * max(0.0, min(x, b) - a) for a, b, s in zip(bp, bp[1:], slope))

def evaluate(w):
    L = ecmp_load(w)
    u = {a: L[a] / G.edges[a]["cap"] for a in arcs}
    return sum(G.edges[a]["cap"] * phi(u[a]) for a in arcs), max(u.values())

w = dict.fromkeys(arcs, 1)
best = evaluate(w)
print("unit weights: cost %7.2f, max utilisation %.3f" % best)
for it in range(400):                               # first-improvement random local search
    a = arcs[rng.integers(len(arcs))]
    old, w[a] = w[a], int(rng.integers(1, 21))
    cand = evaluate(w)
    if cand[0] < best[0]:
        best = cand
    else:
        w[a] = old
print("local search: cost %7.2f, max utilisation %.3f (LP optimum 0.821)" % best)

7.4 Matheuristics

Matheuristics use a MILP solver as a component, which is often the fastest way to good solutions for network problems with a strong formulation.

• Relax-and-fix and fix-and-optimise: solve the problem with most binaries fixed or relaxed, then free a small block (one region, one period) at a time.
• Local branching (Fischetti and Lodi, 2003): around an incumbent \bar y, add the constraint that at most q binaries change, and let the solver search this neighbourhood: \sum_{j : \bar y_j = 1} (1 - y_j) + \sum_{j : \bar y_j = 0} y_j \leq q .
• RINS (Danna, Rothberg and Le Pape, 2005): fix the variables on which the incumbent and the LP solution agree, and solve the remaining sub-MILP.
• Time-limited solving with warm start: give the solver a heuristic solution as incumbent and a time limit; it returns a solution and a gap.

These methods answer the “very short computation times” of autonomous networks (ch. 8.4) without giving up the model: the same formulation provides the bound that certifies the answer.

8. Future networks: virtualization, slicing and autonomy

The second part of the course turns to the problems created by virtualized, sliced and autonomous networks. The models are variants of those of ch. 3–6, but decisions arrive continuously, must be taken in seconds, and must respect guarantees written in standards and contracts.

8.1 What changes

• Joint resources: a request consumes bandwidth on links and compute on servers, so routing and placement are coupled (ch. 6.3).
• Dynamics: slices and service chains are created, scaled and removed over minutes or hours, not years.
• Uncertainty: future requests are unknown when the current one is decided.
• Time limits: an autonomous network decides without a human in the loop, often within a second.
• Reconfiguration costs: moving a running function or rerouting a flow disturbs the service, so a new solution should stay close to the current one.

8.2 Network slicing as admission and embedding

It generalises the multi-dimensional knapsack problem and is NP-hard. When all requests are known in advance, a MILP solves moderate instances; in reality they arrive one by one.

import numpy as np, networkx as nx
from itertools import islice
from scipy.optimize import milp, LinearConstraint
links = [("A", "B", 10), ("A", "C", 10), ("B", "C", 5), ("B", "D", 10),
         ("C", "E", 5), ("D", "E", 10), ("D", "F", 10), ("E", "F", 10)]      # Gb/s
G = nx.DiGraph([(u, v, {"cap": c}) for u, v, c in links] + [(v, u, {"cap": c}) for u, v, c in links])
nodes, arcs, rng = sorted(G), list(G.edges), np.random.default_rng(7)

# 40 slice requests (s, t, bandwidth, revenue), each needing one path among its 3 shortest.
R = []
for _ in range(40):
    s, t = rng.choice(nodes, 2, replace=False)
    b = float(rng.integers(1, 6)); R.append((s, t, b, b * rng.uniform(1, 3)))
paths = [list(islice(nx.shortest_simple_paths(G, s, t), 3)) for s, t, _, _ in R]

# Online: accept a request if one of its candidate paths has enough residual capacity.
res, online = {a: G.edges[a]["cap"] for a in arcs}, 0.0
for (s, t, b, r), Ps in zip(R, paths):
    for p in Ps:
        if all(res[a] >= b for a in zip(p, p[1:])):
            for a in zip(p, p[1:]):
                res[a] -= b
            online += r
            break

# Offline optimum, all requests known: binary x_{i,p}, at most one path per request.
cols = [(i, set(zip(p, p[1:]))) for i, Ps in enumerate(paths) for p in Ps]
one = np.array([[i == j for i, _ in cols] for j in range(len(R))], float)
capa = np.array([[R[i][2] * (a in A) for i, A in cols] for a in arcs])
sol = milp(-np.array([R[i][3] for i, _ in cols]), integrality=np.ones(len(cols)), bounds=(0, 1),
           constraints=[LinearConstraint(one, 0, 1), LinearConstraint(capa, 0, [G.edges[a]["cap"] for a in arcs])])
print("revenue online %.1f | offline optimum %.1f | ratio %.2f" % (online, -sol.fun, online / -sol.fun))

On the backbone, 40 requests of 1 to 5 Gb/s exceed the capacity. Accepting greedily in order of arrival earns 156.4, against 177.1 for the offline optimum: 88 % of what full knowledge of the future would give.

8.3 Online optimization and competitive ratio

Good online algorithms therefore reserve capacity. Awerbuch, Azar and Plotkin (1993) price each link exponentially in its utilisation and accept a request only if its revenue exceeds the price of its cheapest path; when each request is small compared with link capacities, this achieves a competitive ratio logarithmic in the number of nodes (and in the range of request durations). The same primal–dual idea, prices from dual variables, underlies the column generation of ch. 5.4. The Stopping Times and Online Algorithms course develops competitive analysis in depth.

8.4 Autonomous networks and fast re-optimization

An autonomous network runs a closed loop: monitor the state, analyse it, plan a decision, execute it, often abbreviated MAPE. The planning step is an optimization problem re-solved every few seconds or minutes, on a state that changed little.

Three techniques make the loop fast enough.

• Warm starts: the previous solution is feasible or nearly so, and gives the solver an incumbent and a basis.
• Restricted neighbourhoods: only the part of the network affected by the change is re-optimised, as in local branching (ch. 7.4).
• Time-scale decomposition: slow, global decisions (placement, capacity reservation for slices) are optimised rarely; fast, local ones (routing, scaling) are taken by simple rules or learned policies (ch. 10) within the reserved resources.

8.5 From a standard to a model

Requirements of future networks are written in specifications by standardisation bodies such as 3GPP, ETSI and the IETF, not as equations. Turning such a text into a model is a skill in itself; a reliable method has five steps.

1. Glossary to sets: list the entities (sites, slices, functions, links) and give each a set and an index.
2. Quantities to parameters: list every number given or implied (capacities, budgets, latencies) with its unit.
3. Decisions to variables: ask what the operator chooses; distinguish binary choices from quantities.
4. “Shall” to constraints, “should” to objectives: mandatory requirements become constraints; preferences become objective terms or soft constraints with penalties.
5. Check with a small instance: solve it by hand or with a solver, and verify that every sentence of the text is reflected.

9. Resilience, security and energy

Three requirements now shape network optimization beyond cost and congestion: surviving failures and traffic surprises, resisting attacks, and consuming less energy. Each adds constraints or scenarios to the models of ch. 3–6, and they pull in different directions.

9.1 Survivable network design

A failure of one link or node must not interrupt service. Protection reserves backup resources in advance; restoration reroutes after the failure using spare capacity.

Suurballe (1974) gives a combinatorial algorithm for the same problem with two runs of Dijkstra.

At the topology level, surviving any single link failure requires a 2-edge-connected design. In the formulation of Definition 4.1 this is the family of cut constraints \sum_{e \in \delta(S)} y_e \geq 2 \qquad (\emptyset \neq S \subsetneq V), exponentially many, but separated by a minimum-cut computation (Theorem 2.4) on the current solution (Kerivin and Mahjoub, 2005, survey survivable design).

The model has one copy of the routing per scenario; with hundreds of links, it is solved by Benders decomposition or column generation, one subproblem per scenario (ch. 5.4–5.5).

9.2 Robust routing under uncertain traffic

Traffic matrices are forecasts. A robust model requires feasibility for every matrix of an uncertainty set, and fixes the routing as fractions f^k_a \in [0, 1] of each demand, so that the load of arc a is \sum_k d_k f^k_a.

The hose model and oblivious routing, two other uncertainty models used in telecommunications, are described in ch. 11.3.

9.3 Security: interdiction and monitoring

Security problems put an adversary in the model.

Wood (1993) proved the problem NP-hard, even when every removal costs 1. Yet, with unit costs, both halves are easy separately: the best attack on a fixed cut removes its B largest arcs, and the cut for a fixed attack is a minimum cut. The difficulty lies in choosing them together.

Other security requirements are covering or separation constraints.

• Monitor placement: an intrusion-detection function must see every flow; with y_v = 1 for a monitored node, each used path p needs \sum_{v \in p} y_v \geq 1, a hitting-set problem.
• Isolation: functions of different tenants must not share a server, z_{fv} + z_{f'v} \leq 1, or a sensitive slice must not share links (Example 8.5).

9.4 Energy-aware networking

Network equipment consumes much of its power even when idle, so the consumption of a link is well approximated by P_0 y_e + P_1 \ell_e, with a large fixed part P_0 when the link is on. Turning off links at low traffic saves energy (Gupta and Singh, 2003; Chiaraviglio, Mellia and Neri, 2012).

import numpy as np, networkx as nx
from scipy.optimize import milp, LinearConstraint
links = [("A", "B", 10), ("A", "C", 10), ("B", "C", 5), ("B", "D", 10),
         ("C", "E", 5), ("D", "E", 10), ("D", "F", 10), ("E", "F", 10)]      # Gb/s
G = nx.DiGraph([(u, v, {"cap": c}) for u, v, c in links] + [(v, u, {"cap": c}) for u, v, c in links])
nodes, P = sorted(G), {"A": 4, "B": 2, "C": 2, "D": 2, "E": 2, "F": 4}
Z = sum(P[s] * P[t] for s in nodes for t in nodes if s != t)
T = {(s, t): 40 * P[s] * P[t] / Z for s in nodes for t in nodes if s != t}  # gravity, 40 Gb/s
arcs, n, m, E = list(G.edges), len(nodes), len(G.edges), len(links)
link_of = {a: e for e, (u, v, _) in enumerate(links) for a in [(u, v), (v, u)]}  # arc -> link

def green(scale, mu=0.9):
    """Fewest powered links that carry scale * T with utilisation <= mu (flows per source)."""
    nv = n * m + E
    A_eq, b_eq = np.zeros((n * n, nv)), np.zeros(n * n)
    for i, s in enumerate(nodes):
        for j, v in enumerate(nodes):
            for q, (a, b) in enumerate(arcs):
                A_eq[i * n + j, i * m + q] = (a == v) - (b == v)
            b_eq[i * n + j] = scale * (sum(T[s, t] for t in nodes if t != s) if v == s else -T.get((s, v), 0))
    A_ub = np.zeros((m, nv))
    for q, a in enumerate(arcs):
        A_ub[q, q:n * m:m] = 1                         # load of arc a ...
        A_ub[q, n * m + link_of[a]] = -mu * G.edges[a]["cap"]   # ... <= mu * c_a * y_link
    x = milp(np.r_[np.zeros(n * m), np.ones(E)], integrality=np.r_[np.zeros(n * m), np.ones(E)],
             bounds=(0, np.r_[np.full(n * m, np.inf), np.ones(E)]),
             constraints=[LinearConstraint(A_eq, b_eq, b_eq), LinearConstraint(A_ub, -np.inf, 0)]).x
    return [links[e][:2] for e in range(E) if x[n * m + e] > 0.5]

for scale in (1.0, 0.6, 0.3):
    on = green(scale)
    print("traffic %3.0f%%: %d of %d links powered, connected after any single failure: %s"
          % (100 * scale, len(on), E, nx.is_connected(nx.Graph(on)) and not nx.has_bridges(nx.Graph(on))))

10. Hybrid methods: optimization and learning

Operators solve the same kinds of instances again and again: the same network, slightly different traffic. Machine learning can exploit this regularity to speed up optimization or to replace parts of it. This chapter classifies the hybrid methods, implements one, and says which guarantees survive; learned routing is discussed in ch. 11.1.

10.1 Three ways to combine learning and optimization

Bengio, Lodi and Prouvost (2021) distinguish learning end to end, learning to configure an algorithm, and learning alongside an optimization algorithm. For network problems, this gives three practical patterns.

• Learning to configure or assist an exact solver: a model takes the decisions that the solver takes by rules, such as the branching variable or which cuts to add. The solver stays exact; only its speed changes.
• Learning to predict solutions: a model predicts part of the solution (values of binaries, a candidate set) that a solver then completes or repairs.
• End-to-end learned heuristics: a neural policy builds the solution directly, trained by imitation or by reinforcement learning (Khalil et al., 2017; Kool, van Hoof and Welling, 2019).

The further one goes down this list, the faster the answer and the weaker the guarantee.

10.2 Learning inside branch-and-bound

Strong branching evaluates each candidate variable by solving the two child LPs and picks the one that improves the bound most. It gives small trees but costs many LP solves per node. Khalil and coauthors (2016) learned to rank candidates like strong branching from cheap features; Gasse and coauthors (2019) imitated it with a graph neural network.

A graph neural network on this graph is invariant to the order of variables and constraints, and applies to instances of any size. Proposition 5.2 holds whatever fractional variable is branched on, so the learned solver still returns a proven optimum. A bad model makes it slower, never wrong.

10.3 Learning to prune

A second idea predicts which binaries are likely to be one in the optimum, and solves a reduced problem. For the controller placement of ch. 6.2, a classifier scores every site from cheap features, and the p-median MILP is solved over the best-scored sites only.

import numpy as np, networkx as nx
from scipy.optimize import milp, LinearConstraint, Bounds
from scipy.sparse import coo_matrix
from sklearn.linear_model import LogisticRegression

def p_median(D, p, cand):
    """Exact p-median restricted to the candidate sites cand (MILP solved by HiGHS)."""
    n, m = len(D), len(cand); nv = n * m + m
    z = np.arange(n * m).reshape(n, m); y = n * m + np.arange(m)
    assign = coo_matrix((np.ones(n * m), (np.repeat(np.arange(n), m), z.ravel())), (n, nv))
    count = coo_matrix((np.ones(m), (np.zeros(m, int), y)), (1, nv))
    link = coo_matrix((np.r_[np.ones(n * m), -np.ones(n * m)],
                       (np.r_[z.ravel(), z.ravel()], np.r_[z.ravel(), np.tile(y, n)])), (n * m, nv))
    cons = [LinearConstraint(assign, 1, 1), LinearConstraint(count, p, p), LinearConstraint(link, -np.inf, 0)]
    r = milp(np.r_[D[:, cand].ravel(), np.zeros(m)], constraints=cons,
             integrality=np.r_[np.zeros(n * m), np.ones(m)], bounds=Bounds(0, 1))
    return r.fun, {cand[j] for j in range(m) if r.x[y[j]] > 0.5}

def greedy_order(D, k):
    chosen = []
    for _ in range(k):
        rest = [j for j in range(len(D)) if j not in chosen]
        chosen.append(min(rest, key=lambda j: D[:, chosen + [j]].min(1).sum()))
    return chosen

def instance(seed, n=30, p=3):
    rng = np.random.default_rng(seed)
    while True:
        G = nx.random_geometric_graph(n, 0.35, seed=int(rng.integers(1 << 30)))
        if nx.is_connected(G): break
    for u, v in G.edges:
        G.edges[u, v]["ms"] = 10 * np.hypot(*np.subtract(G.nodes[u]["pos"], G.nodes[v]["pos"]))
    D = np.array(nx.floyd_warshall_numpy(G, weight="ms"))
    g = greedy_order(D, 2 * p)
    rank = np.full(n, 2 * p); rank[g] = np.arange(2 * p)        # position in the greedy order
    cover = (D <= np.median(D)).sum(1)                           # nodes within the median latency
    f = np.c_[D.mean(1), D.max(1), cover, rank, rank < p]
    return D, (f - f.mean(0)) / (f.std(0) + 1e-9)

p, n = 3, 30
train = [instance(s) for s in range(40)]
X = np.vstack([f for _, f in train])
labels = [p_median(D, p, list(range(n)))[1] for D, _ in train]          # optimal sites
y = np.concatenate([[j in S for j in range(n)] for S in labels])
clf = LogisticRegression().fit(X, y)

gaps = {(name, k): [] for name in ("learned", "central") for k in (6, 10, 15)}
for s in range(100, 120):                                        # 20 unseen instances
    D, f = instance(s)
    opt, _ = p_median(D, p, list(range(n)))
    for name, score in [("learned", clf.predict_proba(f)[:, 1]), ("central", -D.mean(1))]:
        for k in (6, 10, 15):                                    # size of the pruned candidate set
            val, _ = p_median(D, p, list(np.argsort(-score)[:k]))
            gaps[name, k].append(100 * (val - opt) / opt)
for (name, k), g in gaps.items():
    print("%-7s keep %2d of %d sites: optimal on %2d/20, mean gap %5.2f%%"
          % (name, k, n, sum(x < 1e-6 for x in g), np.mean(g)))

11. Research directions and open problems

This chapter is for self-study. It points to active lines of research that extend ch. 3–10, with papers to start from; each section ends with questions that are still open. It also serves as a reading list for the paper presentations of the second part of the course.

11.1 Traffic engineering at the scale of global networks

Wide-area networks of cloud providers are routed by centralised controllers: B4 (Jain et al., 2013) and SWAN (Hong et al., 2013) solve TE linear programs every few minutes. As networks and the number of demands grow, the LP of ch. 3.2 becomes too slow for the control loop.

• NCFlow (Abuzaid et al., 2021) contracts the topology into clusters, solves smaller problems and stitches them together.
• POP (Narayanan et al., 2021) splits the demands and the capacities into random sub-problems solved in parallel.
• Learned TE replaces the solve by a trained model. Valadarsky and coauthors (2017) studied learning to route under unknown future traffic; DOTE (Perry et al., 2023) maps recent traffic directly to splitting ratios, trained on the congestion objective; Teal (Xu et al., 2023) combines a learned model with a few steps of an optimization method.
• Learned network models replace formulas that are hard to write: RouteNet (Rusek et al., 2020) is a graph neural network that predicts per-path delay and jitter from the topology, the routing and the traffic matrix, fast enough to be used inside a search over routings.

Two cautions apply to all learned controllers. They must be compared with the LP of ch. 3.2 on the same traffic, since the LP is the best any routing can do. And their behaviour on traffic unlike the training data, failures included, must be tested, because no bound comes with them.

How far from optimal can these methods be? MetaOpt (Namyar et al., 2024) searches for the traffic matrices on which a heuristic performs worst, by writing the heuristic and the optimum in one multi-level optimization problem.

• Can such worst-case gaps be computed for learned TE policies, whose behaviour has no closed form?
• Which decompositions keep a provable bound on the loss of optimality?

11.2 Learning for combinatorial optimization

The methods of ch. 10.1–10.3 are surveyed by Bengio, Lodi and Prouvost (2021) and, for graph neural networks, by Cappart and coauthors (2023). Learned branching (Gasse et al., 2019) and learned primal heuristics, such as the neural diving of Nair and coauthors (2020), report large speed-ups on distributions of similar instances.

• Models trained on small instances do not always generalise to larger ones; size generalisation of graph neural networks is not understood.
• Network problems come with a fixed topology and changing traffic. Which representation of a MILP exploits this structure best?
• When a learned policy replaces a solver in an autonomous network, what certificate of quality can it return with its answer?

11.3 Robustness from data

Robust models (ch. 9.2) need uncertainty sets. Besides the Γ-budget, two models are common in telecommunications. The hose model (Duffield et al., 1999) bounds only the total traffic sent and received by each node, which customers of virtual private networks can state. Oblivious routing goes further: one routing for all traffic matrices, with a guaranteed ratio to the best routing of each matrix, computable by LP (Applegate and Cohen, 2003).

The parameter \Gamma or the hose bounds are usually chosen by hand. Bertsimas, Gupta and Kallus (2018) build uncertainty sets from data with statistical guarantees, and distributionally robust optimization protects against a set of distributions rather than of scenarios.

• How should uncertainty sets be built from measured traffic matrices, which are themselves estimated from link counts?
• How should robustness to traffic and to failures be combined without making the model intractable?

11.4 Joint orchestration of computing and networking

Virtualization (ch. 6.3, 8) makes compute and network one resource pool, from data centres to edge servers next to base stations. Surveys of network functions virtualization (Mijumbi et al., 2016) and of NFV resource allocation (Herrera and Botero, 2016) list the models: VNF placement, chaining, scaling and migration, usually as MILPs solved by heuristics.

• Placement, routing and admission are decided at different time scales. How should the layers of the decomposition of ch. 8.4 exchange information without losing too much optimality?
• How should reconfiguration costs (ch. 8.4) be calibrated against service disruptions measured in practice?

11.5 Energy and carbon

Energy-aware routing (ch. 9.4) and green networking (Bianzino et al., 2012) originally targeted the electricity bill. The goal is shifting towards carbon: the carbon intensity of electricity varies by place and hour, so where and when computation and traffic happen matters, not only how much.

• Turning links off conflicts with resilience (Example 9.8) and with fast reaction to traffic surges; how much can be saved with guaranteed recovery times?
• How should the embodied carbon of equipment, which favours using fewer devices longer, enter design models?

11.6 From specifications to models with language models

Ch. 8.5 builds a model from a specification by hand. Large language models are now used to draft optimization models from text: the NL4Opt competition (Ramamonjison et al., 2023) set up a benchmark of linear programs described in natural language, and OptiMUS (AhmadiTeshnizi, Gao and Udell, 2024) combines language models with solvers to formulate and solve MILPs.

• Telecom specifications are long, cross-referenced and full of defined terms. Can a model be extracted from them reliably, and verified against the text?
• How should a generated formulation be tested, beyond solving it once: small instances with known answers, sensitivity checks, comparison with an expert model?

11.7 Decision-focused learning

Optimization models need parameters (future demands, latencies) that are predicted. The usual pipeline, predict then optimize, fits a predictor by least squares and plugs its output into the solver. But prediction errors do not matter equally: an error that does not change the decision costs nothing.

Decision-focused learning trains the predictor to minimise regret rather than prediction error. Regret is piecewise constant in \hat c, so it is replaced by a surrogate: the SPO+ loss of Elmachtoub and Grigas (2022) is convex and computed with one call to the optimization oracle per sample.

• Regret-based training needs many solver calls; how should it scale to the MILPs of ch. 4–6, whose optimal decisions jump with the parameters?
• Which predictions in network planning, traffic or failure rates, gain most from being trained for the decision?

Exercises

Exercises are sorted by level: ★ applies the course, ★★ combines results or asks for a short proof, ★★★ is open-ended. The session plan says which exercises follow which session. Numerical answers refer to the six-node backbone of ch. 1 unless stated otherwise.

1. ★ Duality by hand. Maximise 5x_1 + 4x_2 subject to 6x_1 + 4x_2 \leq 24, x_1 + 2x_2 \leq 6 and x \geq 0, graphically. Write the dual, find its solution from complementary slackness, and check that the two values agree.

   Solution: the optimum is at the intersection of the two constraints, x = (3, 1.5), of value 21. Both constraints are tight, so both duals may be positive; the dual constraints 6y_1 + y_2 = 5 and 4y_1 + 2y_2 = 4 give y = (0.75, 0.5). The dual value is 24 \cdot 0.75 + 6 \cdot 0.5 = 21 (Theorem 0.5, Proposition 0.6).

2. ★ A gravity matrix. With the weights of Example 1.3 and 40 Gb/s in total, compute T_{AB}, the total traffic leaving A, and the traffic from \{A, B, C\} to \{D, E, F\}. Repeat the last computation when all weights are equal.

   Solution: T_{AB} = 40 \cdot 8 / 208 = 1.54 Gb/s; A sends 40 \cdot 4 \cdot 12 / 208 = 9.23 Gb/s. Across the cut, 40 \cdot 64 / 208 = 12.31 Gb/s. With equal weights every ordered pair carries 40 / 30 Gb/s and nine pairs cross, so 12 Gb/s: the heavy end nodes A and F add little here.

3. ★ Dijkstra and a cut. Run Dijkstra from A with the latencies of the ch. 2 block and give the order in which nodes become permanent. Then compute the maximum flow from A to F when the capacity of C–E is raised to 10 Gb/s, and give a minimum cut.

   Solution: A (0), B (2), C (3), E (5), D (6), F (8), with ties C via B and D via E. With C–E at 10 Gb/s, the cut \{A, B, C\} has capacity 20, as do the cuts around A and around F; the maximum flow is 20 Gb/s, each of these cuts certifying it (Theorem 2.4).

4. ★ Integral or not. (a) Show that the matrix with rows (1, 1, 0), (0, 1, 1), (1, 0, 1) is not totally unimodular. (b) Why is the LP relaxation of the assignment problem integral? (c) Why can the arc-node LP of a two-commodity flow not always have integral optimal solutions?

   Solution: (a) its determinant is 2; it is the incidence matrix of a triangle, an odd cycle. (b) The node–edge incidence matrix of a bipartite graph is TU: negating the rows of one side, which preserves total unimodularity, gives the node–arc incidence matrix of the graph with every edge oriented towards that side (Theorem 2.6). (c) Integral two-commodity flow is NP-hard (Even, Itai and Shamir, 1976), so an LP cannot solve it in general unless P = NP; the capacity rows coupling the commodities break total unimodularity.

5. ★ Cut bounds for the maximum utilisation. Compute the bound of Theorem 3.3 for S = \{A\}, S = \{C\} and S = \{A, B, C\}. Which link upgrade lowers U^\star, and to what value if C–E becomes 10 Gb/s?

   Solution: 9.23/20 = 0.46, 5.38/20 = 0.27 and 12.31/15 = 0.821. Only the links of the binding cut matter: raising C–E to 10 Gb/s gives a cut of 20 Gb/s and, as the LP confirms, U^\star = 12.31 / 20 = 0.615 .

6. ★ Modelling with binaries. With y_e (link built) and z_v (node equipped), write linear constraints for: (a) a link may be built only if both end nodes are equipped; (b) at most two of the three links at node B are built; (c) a built link carries at least 1 Gb/s; (d) the number of 10 Gb/s modules is enough for the load \ell_e.

   Solution: (a) y_{uv} \leq z_u and y_{uv} \leq z_v; (b) y_{AB} + y_{BC} + y_{BD} \leq 2.

   3. \ell_e \geq y_e together with \ell_e \leq c_e y_e; (d) an integer q_e \geq 0 with \ell_e \leq 10 q_e, counted in the objective (ch. 4.3–4.4).

7. ★★ The cut condition is not enough. (a) Prove that the cut condition is necessary for a multicommodity flow, and sufficient for one commodity. (b) On the complete bipartite example of ch. 2.4, use Theorem 2.12 with \mu \equiv 1 to prove that at most 75 % of every demand can be routed simultaneously. (c) Give a routing that achieves 75 %.

   Solution: (a) all demand crossing a cut uses its links; for one commodity, Theorem 2.4. (b) Routing a fraction \lambda of each demand requires 6 \geq \lambda \cdot 4 \cdot 2, so \lambda \leq 0.75.

   3. Split each b_i b_j demand equally through a_1 and a_2 (load 0.75 on each edge) and the a_1 a_2 demand equally through b_1, b_2, b_3 (0.25 more): every edge carries exactly 1.

8. ★★ The best possible Fortz–Thorup cost. Using Proposition 3.1, write the LP that minimises the Fortz–Thorup cost over splittable routings, and solve it in Python for the backbone. After session 7, compare with the local search of Example 7.3.

   Hints and expected result: the affine pieces of c \, \phi(\ell / c) are \ell,\quad 3\ell - \tfrac{2}{3}c,\quad 10\ell - \tfrac{16}{3}c,\quad 70\ell - \tfrac{178}{3}c,\quad 500\ell - \tfrac{1468}{3}c,\quad 5000\ell - \tfrac{16318}{3}c . The LP value is 149.74, so the weights found by local search (178.21) are within 16 % of the best splittable routing for this cost.

9. ★★ Cut-set inequalities on the backbone. Consider the network loading problem of ch. 4.4 on the eight backbone links, with modules of 10 Gb/s shared by both directions and unit cost per module. (a) Show that the LP relaxation can install 2.46 modules across \{A, B, C\}. (b) In Python, compare the LP bound, the bound with all cut-set inequalities (2^5 - 1 cuts) and the integer optimum.

   Hints and expected result: (a) the demand across is 2 \times 12.31 Gb/s. (b) The LP gives 6.77 modules, the LP with cut-set inequalities 8.0, the integer optimum 9: the root gap falls from 24.8 % to 11.1 % (Proposition 4.5).

10. ★★ Search strategies in branch-and-bound. Modify the knapsack block of ch. 5.1 to process nodes in best-bound order (a priority queue on the LP bound). Count the nodes and explain the difference with depth-first search.

    Hints and expected result: counting every node taken from the queue, as the block does, best-bound explores about 90 nodes instead of 118 (89 or 90, depending on how ties are broken) and reaches the same optimum, 761. Discarding a node without counting it, when its bound is no better than the incumbent at the moment it is taken, brings the count to about 60.

    Best-bound never expands a node whose bound is below the optimum, which minimises the tree; depth-first finds good incumbents early and needs less memory.

11. ★★ Lagrangian and LP bounds. (a) Prove that relaxing the capacity constraints of the min-cost multicommodity flow gives a Lagrangian dual equal to its LP optimum. (b) For the fixed-charge design of Definition 4.1, relax the weak linking constraints instead: what is the subproblem, and is its bound better than the weak LP bound?

    Solution: (a) the subproblem is a set of shortest-path problems, whose LPs have integral optimal solutions (Theorem 2.6), so Theorem 5.6 gives z_{LD} = z_{LP}. (b) The subproblem splits into shortest paths for the flows and a trivial problem in y (y_e = 1 if its reduced cost is negative); both have the integrality property, so the bound equals the weak LP bound, no better.

12. ★★ Column generation for the maximum utilisation. Write the arc-path version of the MLU program of Definition 3.2 and its dual. Show that pricing is a shortest-path problem, and that the dual is exactly the formula of Theorem 3.3.

    Solution: the primal, with duals in parentheses, is \min U \quad \text{s.t.} \quad \sum_{p \in \mathcal{P}_k} x_p = d_k \ (\sigma_k), \qquad \sum_{p \ni a} x_p \leq U c_a \ (\mu_a \geq 0). The column of U gives the dual constraint \sum_a \mu_a c_a \leq 1, and a path column gives \sigma_k \leq \sum_{a \in p} \mu_a.

    Pricing therefore seeks a path of \mu-length below \sigma_k: a shortest-path problem. At the optimum \sigma_k = \mathrm{dist}_\mu(s_k, t_k), and the dual maximises \sum_k d_k \sigma_k under the normalisation: this is Theorem 3.3.

13. ★★ Swap local search for placement. Starting from the greedy solution of Example 6.3, implement a local search that replaces one open site by a closed one while the mean latency decreases. Does it reach the optimum? What neighbourhood would?

    Hints and expected result: no single swap improves the greedy sites 11, 18 and 27, so local search stops at 2.90 ms, 2.4 % above the optimum (sites 12, 17 and 18). The optimum differs in two sites, so a 2-swap neighbourhood, simulated annealing or a restart strategy (GRASP) is needed (ch. 7.3).

14. ★★ Randomised rounding in numbers. An LP solution sends half of each of 20 demands of 1 Gb/s through a link of 10 Gb/s, and half on another path. After independent randomised rounding (Proposition 7.1), compute the probability that the link carries at least 14 Gb/s. Repeat with 200 demands of 0.1 Gb/s.

    Solution: the load is 1 Gb/s times a binomial variable with 20 trials of probability 0.5, so the probability is \sum_{j \geq 14} \binom{20}{j} 2^{-20} = 0.058. With 200 demands of 0.1 Gb/s it is 7.5 \cdot 10^{-9}: rounding is safe when each demand is small compared with the capacity.

15. ★★ A Γ-robust capacity constraint. Three demands are routed entirely on one arc, with nominal volumes 2, 3 and 4 Gb/s and deviations 2, 1 and 3 Gb/s. Compute the worst-case load for \Gamma = 1, 1.5 and 2, and give dual values (\theta, \rho) of Theorem 9.4 that certify the first and last results.

    Solution: the nominal load is 9 Gb/s. The worst cases add 3, then 3 + 0.5 · 2 = 4, then 3 + 2 = 5, hence 12, 13 and 14 Gb/s.

    For \Gamma = 1, take \theta = 2 and \rho = (0, 0, 1): the dual value is 2 + 1 = 3.

    For \Gamma = 2, take \theta = 1 and \rho = (1, 0, 2): the dual value is 2 + 3 = 5.

16. ★★ Green and survivable. Add to the block of ch. 9.4 the cut constraints of ch. 9.1, at least two powered links across every cut (31 cuts suffice on six nodes), and solve again for 100 %, 60 % and 30 % of the traffic.

    Hints and expected result: enumerate the sets S containing A. Six links are powered at every traffic level, the ring A–B–D–F–E–C–A, which survives every single link failure. Survivability costs one powered link at low traffic (Example 9.8).

17. ★★★ From a specification to a model. Write the complete MILP of Example 8.5 for the backbone, with the latencies of ch. 2 as link delays (ms), ten slices of 1 to 3 Gb/s (four low-latency, two operators) and their 3 shortest candidate paths. Solve it, then relax the 5 ms budget to 8 ms and discuss.

    Hints and expected result: filter candidate paths by delay for low-latency slices; generate the isolation constraints only for pairs of paths that share an arc; link activation is x_{ip} \leq y_e. Check every sentence of the excerpt against a constraint, and test on an instance small enough to verify by hand. With 5 ms, slices between distant nodes such as A and F (8 ms at best) cannot be low-latency, so the delay budget drives the choice of paths.

18. ★★★ Learning to prune, continued. Extend the block of ch. 10.3: (a) use the pruned solution as a warm start of the full MILP instead of a final answer (Proposition 10.3), and measure the solve time; (b) replace the hand-made features by a small graph neural network in PyTorch, trained on the same labels; (c) test on instances with 50 nodes.

    Hints and expected result: SciPy’s milp has no warm-start option, so (a) is best done with a solver that has one (HiGHS through highspy, SCIP or a commercial solver). Report gaps and times as distributions over test instances; expect the learned features to degrade on larger instances, which ch. 11.2 discusses.

19. ★★★ Paper study. Choose one paper cited in ch. 11, read it, and reproduce one quantitative result or figure on public data, at reduced scale if needed. Present it in ten minutes: problem, model, method, your result, limits, and one open question.

    Hints and expected result: a good presentation states the model in the notation of this page (sets, variables, constraints), the bound or baseline the method is compared with, and where your number differs from the published one, with an explanation.

Projects and assessment

The Université Paris-Saclay course detail describes the assessment as “Evaluation Continue non Intégrale” (non-integral continuous assessment); master-mva.com gives no modality, and no weights are displayed. The course description announces labs with solvers and heuristics in the first part, and the reading and presentation of research papers in the second. The subjects below fit that pattern: each is a lab-scale implementation or a paper study, sized for continuous assessment. The written exam is a proposal for self-assessment: the official pages do not say whether the assessment includes one.

Solo projects

1. [Solo · ≈ 20 h] OSPF weight optimisation (paper study: Fortz and Thorup, 2000). How close does local search on weights come to the best splittable routing as the traffic grows?
   • Implement: ECMP load evaluation, the Fortz–Thorup cost, a local search on weights with incremental evaluation, and the LP lower bound of Proposition 3.1 (ch. 3, 7).
   • Data: one SNDlib instance with its traffic matrix (Orlowski et al., 2010), scaled from low to saturating load.
   • Deliverables: code, a 4–6 page report, a 10-minute talk.
   • Success criterion: the curve of cost against total traffic for unit weights, optimised weights and the LP bound, with the gap of optimised weights below 25 % up to the load where the LP reaches utilisation 1.
2. [Solo · ≈ 20 h] Branch-and-price for unsplittable routing (paper study: Barnhart, Hane and Vance, 2000). When does a path formulation beat the compact arc-node MILP?
   • Implement: column generation for the path LP (ch. 5.4), branching on the arcs used by a demand, and the compact MILP of ch. 3.4 solved by HiGHS for comparison.
   • Data: synthetic instances on the backbone and on a public SNDlib topology, with increasing numbers of demands.
   • Deliverables: code, report and talk as above.
   • Success criterion: identical optima on all instances solved by both methods, and a plot of solve times showing where each method wins.
3. [Solo · ≈ 20 h] The price of robustness in capacity planning (paper study: Bertsimas and Sim, 2004). How much capacity does protection against Γ simultaneous traffic deviations cost?
   • Implement: the network loading problem of ch. 4.4 with the robust counterpart of Theorem 9.4, for \Gamma from 0 to the number of demands.
   • Data: an SNDlib instance; deviations of 30 % of each demand.
   • Deliverables: code, report and talk as above.
   • Success criterion: a curve of cost against \Gamma, and the empirical probability that sampled traffic overloads a link, decreasing with \Gamma, from at least 1000 samples.

Group projects

1. [Group of 3 · ≈ 30 h each] Learning to branch on network design (paper study: Gasse et al., 2019). Can a graph neural network imitate strong branching on fixed-charge network design and reduce the size of the search tree?
   • Data: synthetic instances of Definition 4.1 with the strong formulation, 10 to 20 sites.
   • Split: member A writes a Python branch-and-bound with LPs solved by HiGHS and the instance generator (ch. 4, 5.1); member B implements strong branching and collects the imitation data; member C trains the bipartite GNN of Definition 10.1 in PyTorch and runs the evaluation.
   • Deliverables: shared code, one report of 8–10 pages, a 20-minute talk.
   • Success criterion: on held-out instances, including larger ones, fewer nodes than most-fractional branching and a time per node far below strong branching.
2. [Group of 2–3 · ≈ 30 h each] Energy-aware and survivable routing (paper study: Chiaraviglio, Mellia and Neri, 2012). How much energy can switching links off save over a day, with and without survivability?
   • Data: an SNDlib topology with a day of traffic matrices, or a Topology Zoo network (Knight et al., 2011) with gravity traffic modulated over 24 hours.
   • Split: member A solves the MILP of Definition 9.7 per hour; member B implements a greedy switch-off heuristic and compares it with the MILP; member C adds the 2-edge-connectivity cuts and measures the cost of survivability (ch. 9.1, 9.4).
   • Deliverables: shared code, one report of 8–10 pages, a 20-minute talk.
   • Success criterion: a curve of powered links over the day for the three variants, the heuristic within 10 % of the MILP, and every survivable solution verified against all single link failures.
3. [Group of 3 · ≈ 30 h each] Online slicing with service chains (paper study: Awerbuch, Azar and Plotkin, 1993; Addis et al., 2015). How close can online admission of chained slices come to the offline optimum?
   • Data: the backbone and one public topology, with random sequences of requests (chain of 2–3 functions, bandwidth, compute, revenue) and adversarial sequences.
   • Split: member A writes the offline MILP of Definition 6.4 with admission (ch. 6.3, 8.2); member B implements greedy and exponential-pricing online admission (ch. 8.3); member C writes a one-page specification of the service in the style of Example 8.5, derives the model from it, and runs the evaluation.
   • Deliverables: shared code, one report of 8–10 pages, a 20-minute talk.
   • Success criterion: the distribution of the online/offline revenue ratio over at least 100 sequences, with price-based admission beating greedy on the adversarial ones.

Written exam (proposal)

Format: 2 hours, one handwritten A4 sheet allowed, no electronic device, four exercises.

1. Question (4 points). Explain why a minimum-cost flow with one commodity and integer data has an integral optimal solution, whereas the multicommodity flow LP may not. State the definitions and results you use, and give the consequence for routing each demand on a single path.

   Expected: total unimodularity, Theorem 2.6 with the column argument, Corollary 2.7 with Cramer’s rule; the capacity rows coupling commodities break the structure, and integral two-commodity flow is NP-hard (Even, Itai and Shamir); single-path routing is therefore a MILP, solved by branch-and-bound, column generation or rounding.

2. Computation (6 points). A four-node ring A–B–C–D–A has links of 10 Gb/s and a chord A–C of 5 Gb/s. Demands: 12 Gb/s from A to C and 6 Gb/s from B to D. (a) Give a cut bound on the maximum utilisation. (b) Find a routing that attains it. (c) Compute the maximum utilisation of ECMP with unit weights. (d) Find a weight for the arc A→C that brings it to 0.8.

   Expected: (a) S = \{A, B\}: 18 Gb/s across arcs A→D, A→C, B→C of total capacity 25, so U^\star \geq 0.72. (b) 3.6 Gb/s on the chord, 4.2 through B and 4.2 through D for A→C; 3 and 3 for B→D: all cut arcs at 0.72. (c) A→C takes the chord alone: 12 / 5 = 2.4. (d) Weight 2 creates three equal paths: 4 Gb/s each, chord at 0.8, every other arc at 0.7 or less.

3. Short proof (5 points). (a) Prove the cut-set inequality of Proposition 4.5. (b) Prove that the Lagrangian function gives a lower bound for every \lambda \geq 0, and that the constraint violation at a minimiser is a subgradient.

   Expected: (a) the capacity-crossing argument, then Chvátal–Gomory rounding of an integer left-hand side. (b) Theorem 5.6 for the bound; for the subgradient, L(\lambda') \leq c^\top x_\lambda + \lambda'^\top (A x_\lambda - b) = L(\lambda) + (\lambda' - \lambda)^\top (A x_\lambda - b).

4. Modelling (5 points). Every request of a service needs a firewall then a NAT function. Servers have 16 cores; a firewall instance uses 4, a NAT instance 2, and each instance serves at most 5 Gb/s. Traffic must stay within 10 ms from source to destination. Write the sets, variables, constraints and objective of a minimum-cost placement and routing model, and explain how you would solve it every second for a large network.

   Expected: Definition 6.4 with instance counts per server, core and throughput capacities, the chain order through flow segments or the layered graph of Proposition 6.5, a latency filter on candidate paths; offline MILP for planning, and for the per-second loop a warm-started re-optimisation with reconfiguration costs or a heuristic (ch. 7.4, 8.4).

Grading rubric (proposal)

References

Official references

• Neither the master-mva.com course page nor the Université Paris-Saclay course detail lists a bibliography for 2026–2027. The master-mva.com page links a presentation of the course (“Presentation: here”).

Textbooks

• M. Pióro, D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks, Morgan Kaufmann, 2004 — the reference for ch. 1–5 and 9.
• R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993 — ch. 2.
• D. Bertsimas, J. N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997 — ch. 0 and 5.
• L. A. Wolsey, Integer Programming, 2nd ed., Wiley, 2020 — ch. 4–5.
• M. Conforti, G. Cornuéjols, G. Zambelli, Integer Programming, Springer, 2014.
• A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003.
• B. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms, 6th ed., Springer, 2018.
• M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
• G. Desaulniers, J. Desrosiers, M. M. Solomon (eds.), Column Generation, Springer, 2005 — ch. 5.4.
• A. Ben-Tal, L. El Ghaoui, A. Nemirovski, Robust Optimization, Princeton University Press, 2009 — ch. 9.2.
• V. V. Vazirani, Approximation Algorithms, Springer, 2001 — ch. 6–7.
• A. Borodin, R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998 — ch. 8.3.
• E.-G. Talbi, Metaheuristics: From Design to Implementation, Wiley, 2009 — ch. 7.
• D. Bertsekas, R. Gallager, Data Networks, 2nd ed., Prentice Hall, 1992 — ch. 1 and 3.
• J. F. Kurose, K. W. Ross, Computer Networking: A Top-Down Approach, 8th ed., Pearson, 2021 — networking background for ch. 1.

Flows, paths and complexity (ch. 0–2)

• E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik 1, 1959.
• L. R. Ford, D. R. Fulkerson, “Maximal flow through a network”, Canadian Journal of Mathematics 8, 1956.
• J. Edmonds, R. M. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems”, Journal of the ACM 19(2), 1972.
• S. Even, A. Itai, A. Shamir, “On the complexity of timetable and multicommodity flow problems”, SIAM Journal on Computing 5(4), 1976.
• M. Iri, “On an extension of the maximum-flow minimum-cut theorem to multicommodity flows”, Journal of the Operations Research Society of Japan 13(3), 1971.
• K. Onaga, O. Kakusho, “On feasibility conditions of multicommodity flows in networks”, IEEE Transactions on Circuit Theory 18(4), 1971.

Networks and traffic engineering (ch. 1, 3)

• N. McKeown et al., “OpenFlow: enabling innovation in campus networks”, ACM SIGCOMM Computer Communication Review 38(2), 2008.
• B. Fortz, M. Thorup, “Internet traffic engineering by optimizing OSPF weights”, IEEE INFOCOM, 2000.
• B. Fortz, M. Thorup, “Increasing Internet capacity using local search”, Computational Optimization and Applications 29(1), 2004.
• Y. Wang, Z. Wang, L. Zhang, “Internet traffic engineering without full mesh overlaying”, IEEE INFOCOM, 2001.
• C. Filsfils, N. K. Nainar, C. Pignataro, J. C. Cardona, P. Francois, “The segment routing architecture”, IEEE GLOBECOM, 2015.
• R. Bhatia, F. Hao, M. Kodialam, T. V. Lakshman, “Optimized network traffic engineering using segment routing”, IEEE INFOCOM, 2015.
• S. Orlowski, R. Wessäly, M. Pióro, A. Tomaszewski, “SNDlib 1.0 — Survivable Network Design Library”, Networks 55(3), 2010.
• S. Knight, H. X. Nguyen, N. Falkner, R. Bowden, M. Roughan, “The Internet Topology Zoo”, IEEE Journal on Selected Areas in Communications 29(9), 2011.

Network design and exact methods (ch. 4–5)

• F. Barahona, “Network design using cut inequalities”, SIAM Journal on Optimization 6(3), 1996.
• D. Bienstock, S. Chopra, O. Günlük, C.-Y. Tsai, “Minimum cost capacity installation for multicommodity network flows”, Mathematical Programming 81(2), 1998.
• R. E. Gomory, “Outline of an algorithm for integer solutions to linear programs”, Bulletin of the American Mathematical Society 64(5), 1958.
• A. M. Geoffrion, “Lagrangean relaxation for integer programming”, Mathematical Programming Study 2, 1974.
• J. F. Benders, “Partitioning procedures for solving mixed-variables programming problems”, Numerische Mathematik 4, 1962.
• A. M. Costa, “A survey on Benders decomposition applied to fixed-charge network design problems”, Computers & Operations Research 32(6), 2005.
• C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh, P. H. Vance, “Branch-and-price: column generation for solving huge integer programs”, Operations Research 46(3), 1998.
• C. Barnhart, C. A. Hane, P. H. Vance, “Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems”, Operations Research 48(2), 2000.

Placement and heuristics (ch. 6–7)

• B. Heller, R. Sherwood, N. McKeown, “The controller placement problem”, ACM SIGCOMM Workshop on Hot Topics in Software Defined Networks (HotSDN), 2012.
• G. L. Nemhauser, L. A. Wolsey, M. L. Fisher, “An analysis of approximations for maximizing submodular set functions — I”, Mathematical Programming 14, 1978.
• J. G. Herrera, J. F. Botero, “Resource allocation in NFV: a comprehensive survey”, IEEE Transactions on Network and Service Management 13(3), 2016.
• B. Addis, D. Belabed, M. Bouet, S. Secci, “Virtual network functions placement and routing optimization”, IEEE International Conference on Cloud Networking (CloudNet), 2015.
• A. Fischer, J. F. Botero, M. Till Beck, H. de Meer, X. Hesselbach, “Virtual network embedding: a survey”, IEEE Communications Surveys & Tutorials 15(4), 2013.
• N. M. M. K. Chowdhury, M. R. Rahman, R. Boutaba, “Virtual network embedding with coordinated node and link mapping”, IEEE INFOCOM, 2009.
• M. Yu, Y. Yi, J. Rexford, M. Chiang, “Rethinking virtual network embedding: substrate support for path splitting and migration”, ACM SIGCOMM Computer Communication Review 38(2), 2008.
• P. Raghavan, C. D. Thompson, “Randomized rounding: a technique for provably good algorithms and algorithmic proofs”, Combinatorica 7(4), 1987.
• S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by simulated annealing”, Science 220(4598), 1983.
• F. Glover, “Tabu search — Part I”, ORSA Journal on Computing 1(3), 1989.
• T. A. Feo, M. G. C. Resende, “Greedy randomized adaptive search procedures”, Journal of Global Optimization 6(2), 1995.
• M. Fischetti, A. Lodi, “Local branching”, Mathematical Programming 98, 2003.
• E. Danna, E. Rothberg, C. Le Pape, “Exploring relaxation induced neighborhoods to improve MIP solutions”, Mathematical Programming 102(1), 2005.

Future networks, resilience, security and energy (ch. 8–9)

• B. Awerbuch, Y. Azar, S. Plotkin, “Throughput-competitive on-line routing”, IEEE Symposium on Foundations of Computer Science (FOCS), 1993.
• R. Mijumbi, J. Serrat, J.-L. Gorricho, N. Bouten, F. De Turck, R. Boutaba, “Network function virtualization: state-of-the-art and research challenges”, IEEE Communications Surveys & Tutorials 18(1), 2016.
• J. W. Suurballe, “Disjoint paths in a network”, Networks 4(2), 1974.
• H. Kerivin, A. R. Mahjoub, “Design of survivable networks: a survey”, Networks 46(1), 2005.
• D. Bertsimas, M. Sim, “The price of robustness”, Operations Research 52(1), 2004.
• N. G. Duffield, P. Goyal, A. Greenberg, P. Mishra, K. K. Ramakrishnan, J. E. van der Merwe, “A flexible model for resource management in virtual private networks”, ACM SIGCOMM, 1999.
• D. Applegate, E. Cohen, “Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs”, ACM SIGCOMM, 2003.
• R. K. Wood, “Deterministic network interdiction”, Mathematical and Computer Modelling 17(2), 1993.
• M. Gupta, S. Singh, “Greening of the Internet”, ACM SIGCOMM, 2003.
• L. Chiaraviglio, M. Mellia, F. Neri, “Minimizing ISP network energy cost: formulation and solutions”, IEEE/ACM Transactions on Networking 20(2), 2012.
• A. P. Bianzino, C. Chaudet, D. Rossi, J.-L. Rougier, “A survey of green networking research”, IEEE Communications Surveys & Tutorials 14(1), 2012.

Optimization and learning (ch. 10–11)

• Y. Bengio, A. Lodi, A. Prouvost, “Machine learning for combinatorial optimization: a methodological tour d’horizon”, European Journal of Operational Research 290(2), 2021.
• E. B. Khalil, P. Le Bodic, L. Song, G. Nemhauser, B. Dilkina, “Learning to branch in mixed integer programming”, AAAI Conference on Artificial Intelligence, 2016.
• M. Gasse, D. Chételat, N. Ferroni, L. Charlin, A. Lodi, “Exact combinatorial optimization with graph convolutional neural networks”, NeurIPS, 2019.
• E. Khalil, H. Dai, Y. Zhang, B. Dilkina, L. Song, “Learning combinatorial optimization algorithms over graphs”, NeurIPS, 2017.
• W. Kool, H. van Hoof, M. Welling, “Attention, learn to solve routing problems!”, ICLR, 2019.
• V. Nair et al., “Solving mixed integer programs using neural networks”, arXiv:2012.13349, 2020.
• Q. Cappart, D. Chételat, E. B. Khalil, A. Lodi, C. Morris, P. Veličković, “Combinatorial optimization and reasoning with graph neural networks”, Journal of Machine Learning Research 24, 2023.
• K. Rusek, J. Suárez-Varela, P. Almasan, P. Barlet-Ros, A. Cabellos-Aparicio, “RouteNet: leveraging graph neural networks for network modeling and optimization in SDN”, IEEE Journal on Selected Areas in Communications 38(10), 2020.
• A. Valadarsky, M. Schapira, D. Shahaf, A. Tamar, “Learning to route”, ACM Workshop on Hot Topics in Networks (HotNets), 2017.
• Y. Perry, F. Vieira Frujeri, C. Hoch, S. Kandula, I. Menache, M. Schapira, A. Tamar, “DOTE: rethinking (predictive) WAN traffic engineering”, USENIX NSDI, 2023.
• Z. Xu, F. Y. Yan, R. Singh, J. T. Chiu, A. M. Rush, M. Yu, “Teal: learning-accelerated optimization of WAN traffic engineering”, ACM SIGCOMM, 2023.
• A. N. Elmachtoub, P. Grigas, “Smart ‘predict, then optimize’”, Management Science 68(1), 2022.
• S. Jain et al., “B4: experience with a globally-deployed software defined WAN”, ACM SIGCOMM, 2013.
• C.-Y. Hong et al., “Achieving high utilization with software-driven WAN”, ACM SIGCOMM, 2013.
• F. Abuzaid, S. Kandula, B. Arzani, I. Menache, M. Zaharia, P. Bailis, “Contracting wide-area network topologies to solve flow problems quickly”, USENIX NSDI, 2021.
• D. Narayanan, F. Kazhamiaka, F. Abuzaid, P. Kraft, A. Agrawal, S. Kandula, S. Boyd, M. Zaharia, “Solving large-scale granular resource allocation problems efficiently with POP”, ACM SOSP, 2021.
• P. Namyar et al., “Finding adversarial inputs for heuristics using multi-level optimization”, USENIX NSDI, 2024.
• D. Bertsimas, V. Gupta, N. Kallus, “Data-driven robust optimization”, Mathematical Programming 167(2), 2018.
• R. Ramamonjison et al., “NL4Opt competition: formulating optimization problems based on their natural language descriptions”, Proceedings of the NeurIPS 2022 Competitions Track, PMLR 220, 2023.
• A. AhmadiTeshnizi, W. Gao, M. Udell, “OptiMUS: scalable optimization modeling with (MI)LP solvers and large language models”, ICML, 2024.