Optimization Methods

King's College London

Course Description

  • Course Name

    Optimization Methods

  • Host University

    King's College London

  • Location

    London, England

  • Area of Study

    Computer Programming, Computer Science, Information Sciences

  • Language Level

    Taught In English

  • Course Level Recommendations

    Upper

    ISA offers course level recommendations in an effort to facilitate the determination of course levels by credential evaluators.We advice each institution to have their own credentials evaluator make the final decision regrading course levels.

    Hours & Credits

  • UK Credits

    15
  • Recommended U.S. Semester Credits
    4
  • Recommended U.S. Quarter Units
    6
  • Overview

    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

Course Disclaimer

Courses and course hours of instruction are subject to change.

Eligibility for courses may be subject to a placement exam and/or pre-requisites.

Some courses may require additional fees.

Credits earned vary according to the policies of the students' home institutions. According to ISA policy and possible visa requirements, students must maintain full-time enrollment status, as determined by their home institutions, for the duration of the program.

Please reference fall and spring course lists as not all courses are taught during both semesters.

Please note that some courses with locals have recommended prerequisite courses. It is the student's responsibility to consult any recommended prerequisites prior to enrolling in their course.