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, mincost maxflow problems, approximation algorithms, fixed parameter tractability, local search and metaheuristics.
Assumed Knowledge
This course assumes basic linear algebra, and a good knowledge of algorithm design and analysis techniques
Assessment
 Assignments — 20%
 Project — 30%
 Final Exam — 50%
Lecture time table

Lecture time: Wednesday 10:00am  noon
Lecture location: SIT Lecture Theatre 123 
Lab time: Monday 11:00  noon
Lab location: SIT Lab 115
Other Resources
Please go to the ELearning 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 