Catanzaro Daniele (compensates Delvenne Jean-Charles); Delvenne Jean-Charles coordinator; Hendrickx Julien;
Basic knowledge of linear programming and the simplex algorithm
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.
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”.
At the end of this learning unit, the student is able to :
More specifically, at the end of the course, the student should be able to :
formulate different combinatorial problems as integer programmes
explore different formulations for a same problem
find lower and upper bounds to the solution of an integer programme
recognize and solve some integer programmes that are solvable in polynomial time
recognize some integer programmes that are hard to solve (NP-hard)
apply various techniques (branch-and-bound, Lagrangian relaxation, heuristics) to solve hard problems approximately
Tranversal learning outcomes:
Use of Matlab or other softwares to solve medium-size problems
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: NP-hardness
Intelligent enumeration - the branch-and-bound algorithm
Introduction to cutting plane algorithms
Heuristic methods to find good solutions quickly
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.
Integer Programming, L.A. Wolsey, Wiley, New York 1998.
Title of the programme
Master  in Data Science Engineering
Master  in Computer Science and Engineering
Master  in Computer Science
Master  in Mathematical Engineering
Master  in data Science: Information technology