CSE444 Optimization and constraints

Bernd Meyer and Kim Marriott

Prohibitions: CSE446.

Optimization and constraint solving is at the core of many extremely important industrial applications, such as timetabling, resource allocation, airline scheduling or fleet coordination. They 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.

Topics include:
1.Characterization and examples of optimization and satisfaction problems.
2.Complexity of optimization and satisfaction problems.
3.Overview of techniques for handling intractable problems.
4.Constraint Solving, Gauss-Jordan.
5.Linear programming, Simplex, MIP.
6.Non-linear programming, Euler-Lagrange, quadratic programming.
7.Stochastic search methods and their origins in nature: Simulated annealing, Taboo Search, Genetic algorithms, Neural networks, Ant colony optimization.
8.New trends in stochastic optimization.
9.Constraint satisfaction methods: Backtracking Solver, consistency methods, Boltzman machines.
10.Modelling languages & tools.

The subject consists of two parts: The first part is oriented towards modelling and programming optimization problems in specialized languages. It details methods and algorithms used in their implementation, i.e. algorithms for constraint solving and linear optimization, as well as programming techniques with such languages. We will particularly look at OPL (the Optimization Programming Language) and at the CLP paradigm (Constraint Logic Programming). The second part of the course discusses advanced methods and algorithms for constraint solving and optimization that are not directly available in such languages. A particular emphasis is on stochastic optimization methods.

Back to 2001 Honours subjects