Skip to main content
KBS_Icon_questionmark link-ico

Optimisation Methods

Key information

  • Module code:

    6CCS3OME

  • Level:

    6

  • Semester:

      Spring

  • Credit value:

    15

Module description

Aims and Learning Outcomes

To introduce various 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:

  • Model computational problems from various application areas as optimisation problems
  • Explain, from underlying first principles, commonly used algorithms and algorithmic techniques
  • For given optimisation problems, select, adapt and apply appropriate commonly used algorithms and algorithmic techniques and evaluate their effectiveness
  • Evaluate computational complexity and consider limitations of optimisation algorithms, and suggest appropriate mitigation or compromises. 

 

Syllabus

An indication of the types of topics:

shortest-paths problem:

  • Single-source shortest paths: Bellman-Ford and Dijkstra's algorithms
  • All-pairs shortest paths
  • some special cases: shortest paths in directed acyclic graphs; shortest paths in geographical networks

Network flow problems: algorithms and applications 

  • Maximum flows, Minimum-cost flows, Multicommodity flows
  • Ford-Fulkerson method for the maximum-flow problem
  • Successive-shortest-paths algorithm for the minimum-cost flow problem
  • Applications of network flow problems

Convexity in optimisation problems

  • Convex set and convex functions
  • Convex optimisation problems
  • Canonical problem forms (linear program, least squares)

Gradient methods

  • Gradient descent method
  • Stochastic optimisation
  • Machine learning applications

Constrained optimisation

  • Projected gradient descent
  • Dual method

Assessment details

Please note: The below assessment details for the 2024/25 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.