Optimisation Methods

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:

• 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 

 

Assessment details

Please note: The below assessment details for the 2022/23 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

Module description disclaimer

King’s College London reviews the modules offered on a regular basis to provide up-to-date, innovative and relevant programmes of study. Therefore, modules offered may change. We suggest you keep an eye on the course finder on our website for updates.

Please note that modules with a practical component will be capped due to educational requirements, which may mean that we cannot guarantee a place to all students who elect to study this module.

Please note that the module descriptions above are related to the current academic year and are subject to change.