Computer Laboratory

Course pages 2014–15

Flows in Networks

Principal lecturer: Dr Richard Gibbens
Additional lecturer: Dr Andrei Bejan
Taken by: MPhil ACS, Part III
Code: L110
Hours: 16 (14 lectures + 2 example classes)
Prerequisites: Familiarity with the basics of mathematical optimization problems, graph theory, game theory and packet-based communication networks

Aims

This module aims to provide an understanding of models for flows in networks and to illustrate these ideas by considering road and communication networks.

Syllabus

  • Mathematical foundations: unconstrained and constrained optimization and equilibrium concepts [2 lectures]
  • Applications to traffic assignment and road pricing in road transport networks. [4 lectures]
  • Applications to computer packet networks including decentralised flow control and network utility maximization. [4 lectures]
  • Mathematical foundations: game-theoretic notions of equilibrium, Braess's paradox and the price of anarchy for network problems. [4 lectures]

Objectives

On completion of this module, students should:

  • Have a broad understanding of how optimization and game theory underpin our understanding of diverse resource allocation problems in networks;
  • have a familiarity with models for road and communication networks.

Coursework

Coursework will take the form of two example sheets with two associated example classes.

Practical work

None.

Assessment

The lectured content will be assessed by written test, set and marked by the course leader. The mark will be expressed as a percentage and will form 80% of the overall result. Each example sheet will be ticked (pass/fail) and worth 10% of the overall result.

Recommended reading

Sheffi, Y. (1985). Urban transportation networks: equilibrium analysis with mathematical programming methods.. Prentice-Hall. Available online.
Srikant, R. (2004). The Mathematics of Internet congestion control. Birkhauser.
Roughgarden, T. (2005). Selfish routing and the price of anarchy. MIT Press.