Module description
Aims and Learning Outcomes
To introduce various optimisation problems, efficient algorithms for solving these problems, and general algorithmic techniques which can be applied to a wide range of optimisation problems. The emphasis is put on network optimisation problems and on general optimisation techniques. To discuss applications of optimisation problems in communication systems, computer networks, manufacturing, scheduling, and resource allocation.
On successful completion of this module, students will be able to:
- Model computational problems from various application areas as optimisation problems
- Explain, from underlying first principles, commonly used algorithms and algorithmic techniques
- For given optimisation problems, select, adapt and apply appropriate commonly used algorithms and algorithmic techniques and evaluate their effectiveness
- Evaluate computational complexity and consider limitations of optimisation algorithms, and suggest appropriate mitigation or compromises.
Syllabus
An indication of the types of topics:
Shortest-paths problem:
- Single-source shortest paths: Bellman-Ford and Dijkstra's algorithms
- All-pairs shortest paths
- some special cases: shortest paths in directed acyclic graphs; shortest paths in geographical networks
Network flow problems: algorithms and applications
- Maximum flows, Minimum-cost flows, Multicommodity flows
- Ford-Fulkerson method for the maximum-flow problem
- Successive-shortest-paths algorithm for the minimum-cost flow problem
- Applications of network flow problems
Convexity in optimisation problems
- Convex set and convex functions
- Convex optimisation problems
- Canonical problem forms (linear program, least squares)
Gradient methods
- Gradient descent method
- Stochastic optimisation
- Machine learning applications
Constrained optimisation
- Projected gradient descent
- Dual method
Assessment details
Please note: The below assessment details for the 2025/26 academic year may be updated. The confirmed details will be available on the Student Handbook and on the module KEATS page at the beginning of the semester.