Session: Semester 2, 2013
Coordinator: Julian Mestre

COMP3530: Discrete Optimization

Introduction

This unit introduces students to the algorithmic theory and applications of discrete optimization. The main aims of this unit are: (i) learn how to model various practical problems as abstract optimization problems, (ii) learn the theory underlying efficient algorithms for solving these problems, (iii) learn how to use these tools in practice.

Specific topics include: Linear and integer programming, polyhedral theory, min-cost max-flow problems, approximation algorithms, fixed parameter tractability, local search and meta-heuristics.

Assumed Knowledge

This course assumes basic linear algebra, and a good knowledge of algorithm design and analysis techniques

Assessment

In addition, there is a final exam barrier of 40%.

Lecture time table

Other Resources

Please go to the E-Learning site to the full UoS outline, access assignments, quizzes, and your marks for this unit.

Schedule

Date Topic Lecture notes Scribbles
- Background material w0 background -
Jul 31 Introduction to discrete optimization w1 introduction w1 scribbles
Aug 7 Simplex w2 simplex w2 scribbles
Aug 14 Linear programming duality w3 duality -
Aug 21 Applications of linear programming w4 applications w4 scribbles
Aug 28 Integral polyhedra w5 integral w5 scribbles
Sep 4 Integer linear programming w6 ip w6 scribbles
Sep 11 Large scale optimization w7 large scale w7 scribbles
Sep 18 Lagrangian relaxation w8 lagrangian w8 scribbles
Sep 25 Maximum submodular coverage w9 sub coverage w9 scribbles
October 9 Minimum weight submodular cover w10 min sub cover w10 scribbles
October 16 Iterative methods for assignment problems w11 iterative assignment w11 scribbles
October 23 Iterative methods for connectivity problems w12 iterative connectivity w12 scribbles