Aims

This course is about finding effective ways to solve discrete optimization problems that arise in graphs, production planning, logistics, circuit layout, etc. Given that most practical problems are "hard", the emphasis is on understanding how to model such problems and then choose an appropriate algorithm - branch-and-bound, branch-and-cut, decomposition, heuristics - so as to produce provably optimal solutions, or practical solutions of guaranteed quality.

Main themes

The course is about different ways to solve optimization problems with discrete or integer variables, which are used to handle indivisibilities, or on/off decisions, such as choosing an edge in a graph, buying a machine, using a warehouse, etc. Such problems arise in scheduling trains or aircraft, constructing a tour in a graph, drawing up a production plan for electricity generation, etc. The theory involves the study of polyhedra, matrices, graphs and aspects of complexity and the development of tight formulations. The algorithmic approaches covered include implicit enumeration and cutting planes (branch-and-cut), Lagrangian relaxation, dynamic programming and approximation algorithms.

Content and teaching methods

INTRODUCTION
Lecture 1: Formulation of combinatorial optimization and integer programming problems
Lecture 2: Finding bounds on the optimal value and using them to prove optimality
EASY PROBLEMS
Lecture 3: Recognizing certain easy problems - network flows, trees
Lecture 4: Matching and sssignment Problems
Lecture 5: Introduction to the distinction between easy and hard problems
HARD PROBLEMS
Lecture 6: Intelligent enumeration - the branch-and-bound algorithm
Lecture 7: Lagrangian relaxation - a decomposition approach
Lecture 8: Using the geometry - general cutting plane algotihms
Lecture 9: Using problem structure - specialized cutting planes, branch-and-cut
Lecture10: Heuristic methods to find good solutions quickly
FURTHER TOPICS
Lecture 11: Problems solvable by dynamic programming
Lecture 12: Decomposition using column generation
Lecture 13: More on formulations and problem solving

Other information (prerequisite, evaluation (assessment methods), course materials recommended readings, ...)

An exercise session is held every two weeks. The students will be expected to use a commercial modelling language and optimization system to solve several small practical problems.They will also be asked to program and test one of the algorithms seen in the course.
REFERENCE: Integer Programming, L.A. Wolsey, Wiley, New York 1998.

Programmes in which this activity is taught

Other credits in programs