Teacher(s)
Language
English
> Frenchfriendly
> Frenchfriendly
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.
Learning outcomes
At the end of this learning unit, the student is able to :  
1 
Learning outcomes:

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
Lectures, possibly complemented by individual discovery of certain topics, and supervised exercises sessions. These activities take place in the classroom or in “comodal” form depending on practical constraints and on the number of students present.
Students also complete one or several more advanced homework, using an optimization software.
Students also complete one or several more advanced homework, using an optimization software.
Evaluation methods
A written exam will count for 85% of the grade. The remaining 15% are obtained through homework (between 1 and 3 problem sets to be solved during the semester).
Online resources
Bibliography
Integer Programming, L.A. Wolsey, Wiley, New York 1998.
Teaching materials
 Documents sur la page Moodle / Documents on the Moodle page
Faculty or entity
Programmes / formations proposant cette unité d'enseignement (UE)
Title of the programme
Sigle
Credits
Prerequisites
Learning outcomes
Master [120] in Mathematics
Master [120] in Computer Science and Engineering
Master [120] in Computer Science
Master [120] in Mathematical Engineering
Master [120] in Data Science Engineering
Master [120] in Data Science: Information Technology