Combinatorial optimization

Teacher(s)

Hendrickx Julien; Nunes Grapiglia Geovani;

Language

English
> French-friendly

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 (branch-and-cut), Lagrangian relaxation, dynamic programming and approximation algorithms.

Learning outcomes

At the end of this learning unit, the student is able to :
1	Learning outcomes: AA1: 1,2 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

Content

1. Formulation of combinatorial optimization and integer programming problems.
2. Finding bounds on the optimal value and using them to prove optimality
3. Recognizing and solving certain easy problems - network flows, trees, matching and assignment problems  
4. Introduction to the distinction between easy and hard problems: NP-hardness
5. Intelligent enumeration - the branch-and-bound algorithm
6. Lagrangian relaxation
7. Introduction to cutting plane algorithms
8. 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 “co-modal” 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.

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

Moodle page of the course.

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

MAP