Combinatorial optimization

linma2450  2020-2021  Louvain-la-Neuve

Combinatorial optimization
Due to the COVID-19 crisis, the information below is subject to change, in particular that concerning the teaching mode (presential, distance or in a comodal or hybrid format).
5 credits
30.0 h + 22.5 h
Q1
Teacher(s)
Delvenne Jean-Charles; Hendrickx Julien;
Language
English
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

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

Due to the COVID-19 crisis, the information in this section is particularly likely to change.

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

Due to the COVID-19 crisis, the information in this section is particularly likely to change.

Written or oral exam (depending on the circumstances and on the number of students), and grades of the homework.
The exam can take place remotely if required by the sanitary situation or practical constraints. The teaching team may organize a (compulsory) oral exam to obtain complementary information in case of need, or of doubt on the grade to assign.
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
Force majeure
Teaching methods
Lecture and supervised exercices sessions take place online.
Evaluation methods
The exam is written, on site. An exam of adapted form will be proposed to the students with a valid quarantine certificate or a 'formulaire retour' from the Foreign Office, if the teachers (Julien Hendrickx and Jean-Charles Delvenne) are warned asap and in any case before the main exam. This alternative exam will cover the same topics as the main exam, and will be organised in a form compatible with the situation of the student.


Programmes / formations proposant cette unité d'enseignement (UE)

Title of the programme
Sigle
Credits
Prerequisites
Aims
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