Show/hide main menu

Modules

6CCS3OME Optimisation Methods

Credit value: 15
Lecturer:
Dr Kathleen Steinhoefel and Brendan Michael (office hours)
Semester: 2
Teaching pattern: weekly 2-hour lecture and 1-hour tutorial
Assessment: 100% written examination, 2 hours (Marking Model 2 - Double Marking)

Learning aims & 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 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 be aware of the principles underpinning the discussed algorithms, will be able to select an appropriate algorithm or a general algorithmic technique for a given optimisation problem; will be familiar with the running time of the discussed algorithms.

Syllabus
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:
  • 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 
Suggested reading/resources

 

 


17 January 2018
Sitemap Site help Terms and conditions  Privacy policy  Accessibility  Modern slavery statement  Contact us

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454