Introduction

Optimization and constraint solving techniques are at the core of many extremely important industrial applications, such as timetabling, resource allocation, airline scheduling and fleet coordination. These methods are also fascinating from a theoretical point of view, because they are instances of computationally hard problems and therefore require specialized techniques to be made tractable. This course discusses the various paradigms and methods that can be used to solve constraint problems and optimization problems.

Lectures will cover:

• Introduction; Computational Complexity; Cook's Theorem;
• Linear Programming; Simplex Method;
• Integer and Mixed Integer Programming;
• Network Flow; Branch & Bound Methods;
• Duality;
• Euler-Lagrange Multiplier Methods; Kuhn-Tucker Conditions
• Non-linear Programming;
• Interior Point Methods (optional, time permitting);
• Introduction to Stochastic Constraint Solving and Optimization;
• Meta-Heuristics: Tabu Search, Simulated Annealing;
• Genetic Algorithms;
• Ant Colony Optimization;
• Constraint Handling in Meta-Heuristics (optional, time permitting).

The lectures will be held in 75/G55 on Monday from 11am-12pm and on Tuesday from 10am-12pm
The lectures for CSE460 will finish in week 7

The course will be taught by Dr Bernd Meyer. Consulation 4pm-6pm Wednesday Rm 148, Blg 75 or by appointment.

Textbooks

There are several recommended books for this subject:

• Introduction to Mathematical Programming. Wayne L.  Winston. Duxbury Press, 1995.
• New Ideas in Optimization, selected chapters. David Corne, Marco Dorigo and Frank Glover (Eds.). McGraw Hill, 2000.

The next two books are are only marginally relevant for CSE460, but will help if you are interested in the programming related aspects (which are covered in CSE461).

• The OPL Optimization Programming Language. Pascal van Hentenryck. MIT Press, 1999.
• Constraint Programming-An Introduction. Kim Marriott and Peter Stuckey. MIT Press, 1998.

In addition to this, selected research papers will be referenced throughout the course.

The lecture material will be loosely based on this material and will be available on the Web.

Assessment

There will be two assignments based on the course material. The individual assignments will be worth 40% (Assignment 1, due Friday 25th of August) and 60% (Assignment 2, due Friday 29th of September).