COMP557

Optimisation

Aims

To provide a foundation for modelling various continuous and discrete optimisation problems.

    To provide the tools and paradigms for the design and analysis of algorithms for continuous and discrete optimisation problems. Apply these tools to real-world problems.

    To review the links and interconnections between optimisation and computational complexity theory.

    To provide an in-depth, systematic and critical understanding of selected significant topics at the intersection of optimisation, algorithms and (to a lesser extent) complexity theory, together with the related research issues.

    Syllabus

    1

    Basics: Linear Algebra, Geometry and Graph Theory. (5 lectures)

    Linear Programming: Introduction, Definitions and Examples, Simplex Algorithm, Matrices, Linear Programming Duality, Primal-Dual Method, Geometric and Algebraic views of Linear Programming. (9 lectures)

    Algorithms and Complexity: Time Bounds, Size of the Instance, Elements of the Analysis of Algorithms, Information about Ellipsoid Algorithm. (2 lectures)

    Efficient Algorithms for Selected Optimisation Problems, e.g., Max-Flow, Matchings. (4 lectures)

    Integer Linear Programming: Polytopes, Total Unimodularity, Heuristics, Cutting-Planes and Branch-and-Bound (TSP). (3 lectures)

    Algorithms for Hard Optimisation Problems: Approximation Algorithms, Information about NP-Completeness, Approximation Algorithms for selected Hard Optimisation Problems (e.g., Set Cover, Set Packing, Knapsack). (7 lectures)

    Recommended Texts

    Primary texts:

    D. Bertsimas, J.N. Tsitsiklis. "Linear Optimization." Athena Scientific, 1997.

    V. Chvatal. "Linear Programming." W.H. Freeman, 1983.

    W.J.Cook, W.H. Cunningham, W.R. Pulleyblank and A. Schrijver. "Combinatorial Optimization." John Wiley and Sons, 1998.

    V.V. Vazirani. Approximation Algorithms. Springer, 2001.

    Further reading:

    C.H. Papadimitriou, K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publicaion, 1998.

    A. Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, 1986.

    J. Kleinberg, E. Tardos. Algorithm Design. Addison-Wesley, 2005.

    Learning Outcomes

    A critical awareness of current problems and research issues in the field of optimisation.

    The ability to formulate optimisation models for the purpose of modelling particular applications.

    The ability to use appropriate algorithmic paradigms and techniques in context of a particular optimisation model.

    The ability to read, understand and communicate research literature in the field of optimisation.

    The ability to recognise potential research opportunities and research directions.

    Learning Strategy

    Lectures

    Tutorials

    Seminars

    Formal Lectures: Students will be expected to attend three hours of formal lectures in a typical week accompanied by one hour of seminar given by students in groups, or one hour of tutorials.

    Private study: In a typical week students will be expected to devote six hours of unsupervised time to private study. The time allowed per week for private study will typically include three hours of time for reflection and consideration of lecture material and background reading, and three hours for completion of practical exercises.