<- Archives UCL - Programme d'études ->



Combinatorial optimization [ LINMA2450 ]


5.0 crédits ECTS  30.0 h + 22.5 h   1q 

Teacher(s) Delvenne Jean-Charles ;
Language English
Place
of the course
Louvain-la-Neuve
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.
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.
Content 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 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.
Cycle et année
d'étude
> Master [120] in Computer Science
> Master [120] in Computer Science and Engineering
> Master [120] in Mathematical Engineering
> Master [120] in Statistics: General
Faculty or entity
in charge
> MAP


<<< Page précédente