KBS_Icon_questionmark link-ico

Optimization 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
Students who successfully complete this module 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 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 familiar with the running time of the discussed algorithms; will be aware of the principles underpinning the discussed algorithms.

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, 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

Staff information

Not applicable

Teaching pattern

Not applicable

Module assessment - more information

Not applicable

Key information

Module code 6CCS3OME

Credit level 6

Assessment

Credit value 15

Semester Semester 2 (spring)

Study abroad module Yes