KBS_Icon_questionmark link-ico

Optimisation Methods (Module)

Module description

Aims
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.

Learning Outcomes
On successfully completing this module you will be able to express computational problems from various application areas as (discrete) optimisation problems; will be familiar with commonly used algorithms and main algorithmic techniques for optimisation problems; will understand the principles underpinning the discussed algorithms; will be able to select an appropriate algorithm for a given optimisation problem or to develop a new algorithm based on a general algorithmic technique; will be able to analyse the running time of the developed algorithmic solutions.

Provisional Syllabus
Single-source shortest-paths problem:
Dijkstra's algorithm
The Bellman-Ford algorithm
Shortest paths in directed acyclic graphs
All-pairs shortest paths:
Johnson's algorithm
Network flow problems:
Maximum flows, Minimum-cost flows and Multicommodity flows, and their applications
Maximum matching problem and its applications to resource allocation problems
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

Staff information

Not applicable

Teaching pattern

Not applicable

Module assessment - more information

Not applicable

Optional module for

Key information

Module code 7CCSMOME

Credit level 7

Assessment

Credit value 15

Semester Semester 2 (spring)

Study abroad module Yes