Module description
Aims and Learning Outcomes
To introduce various discrete 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 express computational problems from various application areas as (discrete) optimisation problems
- Be familiar with commonly used algorithms and main algorithmic techniques for optimisation problems
- Be aware of the principles underpinning the discussed algorithms
- Be able to select an appropriate algorithm or a general algorithmic technique for a given optimisation problem
- Be familiar with the running time of the discussed algorithms.
Syllabus
An indication of the types of topics:
Single-source shortest-paths problem:
- Dijkstra's algorithm
- The Bellman-Ford algorithm
- Shortest paths in directed acyclic graphs
- Shortest paths in geographical networks
All-pairs shortest paths:
Network flow problems:
- Maximum flows, Minimum-cost flows, Multicommodity flows
- Maximum matching problem
- The Ford-Fulkerson method for the maximum-flow problem
- The Successive-shortest-paths algorithm for the minimum-cost flow problem
Linear programming (LP):
- Basic properties of LP problems
- LP formulation of network flow problems
- Integer programming
Computationally hard optimisation problems:
- Polynomial-time problems and NP problems
- NP-hard optimisation problems
Optimisation techniques for NP-hard problems:
- Branch-and-bound method for finding exact solutions
- Simulated annealing
- Genetic algorithms
Assessment details
Please note: The below assessment details for the 2023/24 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.
100% Examination