Note from June 29, 2020
Although we do not yet know how long the social distancing related to the Covid19 pandemic will last, and regardless of the changes that had to be made in the evaluation of the June 2020 session in relation to what is provided for in this learning unit description, new learnig unit evaluation methods may still be adopted by the teachers; details of these methods have been  or will be  communicated to the students by the teachers, as soon as possible.
Although we do not yet know how long the social distancing related to the Covid19 pandemic will last, and regardless of the changes that had to be made in the evaluation of the June 2020 session in relation to what is provided for in this learning unit description, new learnig unit evaluation methods may still be adopted by the teachers; details of these methods have been  or will be  communicated to the students by the teachers, as soon as possible.
5 credits
30.0 h + 22.5 h
Q1
Teacher(s)
Delvenne JeanCharles (coordinator); Hendrickx Julien;
Language
English
Prerequisites
Basic knowledge of linear programming and the simplex algorithm
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 (branchandcut), Lagrangian relaxation, dynamic programming and approximation algorithms.
Aims
At the end of this learning unit, the student is able to :  
1 
Learning outcomes:

The contribution of this Teaching Unit to the development and command of the skills and learning outcomes of the programme(s) can be accessed at the end of this sheet, in the section entitled “Programmes/courses offering this Teaching Unit”.
Content
 Formulation of combinatorial optimization and integer programming problems.
 Finding bounds on the optimal value and using them to prove optimality
 Recognizing and solving certain easy problems  network flows, trees, matching and assignment problems
 Introduction to the distinction between easy and hard problems: NPhardness
 Intelligent enumeration  the branchandbound algorithm
 Lagrangian relaxation
 Introduction to cutting plane algorithms
 Heuristic methods to find good solutions quickly
Teaching methods
An exercise session is held approximately every two weeks. One or several home exercises on a software (Matlab or other) will be proposed as well.
Evaluation methods
Written exam.
Online resources
Bibliography
Integer Programming, L.A. Wolsey, Wiley, New York 1998.
Faculty or entity
MAP
Programmes / formations proposant cette unité d'enseignement (UE)
Title of the programme
Sigle
Credits
Prerequisites
Aims
Master [120] in Data Science Engineering
Master [120] in Mathematics
Master [120] in Computer Science and Engineering
Master [120] in Mathematical Engineering
Master [120] in Computer Science
Master [120] in Data Science: Information Technology