CSC444 Optimization and constraints

Course outline:
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:

• Characterization and examples of optimization and satisfaction problems.
• Complexity of optimization and satisfaction problems.
• Overview of techniques for handling intractable problems.
• Constraint Solving, Gauss-Jordan.
• Linear programming, Simplex, MIP.
• Stochastic search methods and their origins in nature: Simulated annealing, Taboo Search, Genetic algorithms, Neural networks, Ant colony optimization.
• Constraint satisfaction methods: Backtracking Solver, consistency methdC, Boltzman machines.
• Modelling languages & tools.

Lectures:
Tuesdays 11.00 - 1.00pm (E6)

Assessment:
T.B.A.

Courseware

Back to 2000 Honours subjects