Duration
30h Th, 20h Pr, 25h Proj.
Number of credits
Lecturer
Language(s) of instruction
English language
Organisation and examination
Teaching in the second semester
Schedule
Units courses prerequisite and corequisite
Prerequisite or corequisite units are presented within each program
Learning unit contents
Consider a salesman who must visit 20 potential customers in 20 different cities. A natural question he may ask is to know what is the optimal order in which he has to visit all cities so as to minimze the total distance. This famous problem is better known as the traveling salesman problem. It is the typical example of a discrete optimization problem. Indeed, there is a finite number of solutions (the 20! possible permutations of cities) and we may think of testing them all in order to find the optimal one. This approach is however impossible to perform in practice. Even if we were able to test a billion of these solutions per second, it would take us 77 years to test them all.
The traveling salesman problem is one of many discrete optimization problems. Indeed in particular the problems where binary decisions (such as yes or no) have to be taken often arise in practical applications.
Concerning the contents of the course, as a first part, we concentrate on modeling discrete problems as linear integer programs. We discuss some good principles in order to come up with a formulation. We also see what is needed in order to have a good formulation.
Then the last part of the course deals with the solving techniques of integer programs: mainly branch-and-bound, branch-and-cut, lagrangian relaxation, dynamic programming and approximation algorithms. We also consider some classes of important discrete problems that are well solved, namely flow and matching problems.
Learning outcomes of the learning unit
At the end of the course, the student
- will be able to formulate a real problem as an integer programming model
- will be able to compare two formulations of a problem
- will know the main methods to solve integer progamming problems
- will be able to recognize a tractable discrete optimization problem
Prerequisite knowledge and skills
A basic course in linear programming.
Planned learning activities and teaching methods
Traditional tutorials are organized. An implementation project must be achieved.
Mode of delivery (face-to-face ; distance-learning)
Recommended or required readings
Two main references are used: For the first part (and the approximation algorithms): D. Bertsimas, R. Weismantel, Optimization over Integers. Dynamic Ideas, 2005. For the second part: L. Wolsey, Integer Programming. Wiley, 1998.
Assessment methods and criteria
The final exam is oral and composed of theory and exercises.
The final grade is made of 2/3 of the exam grade and 1/3 of the project grade.
If the project is not submitted in May, it has to be resubmitted in August. The absence of any project submitted implies a "no show" grade.
Work placement(s)
Organizational remarks
The course is given in the second semester.
Contacts
Adaptation of teaching commitments following the COVID-19 pandemic for the May-June 2020 session
Teaching methods implemented : distance-learning
Videos of the lectures and the tutorial sessions are available.
Assessment subjects
The material of the lecture correponds to what was taught face-to-face as well as what was taught in videocourses.
Assessment methods
The exam is an oral videoconference exam without preparation and open book.
The exam consists of a theoretical question drawn from the list available in the dox repository. Then an exercise is given to the student who has ten minutes to solve / start the exercise, take a photo of his notes and send it by email to the professor. If the exercise is not finished after 10 minutes, the student orally explains how to finish it. A list of exercise topics will also be made available on the dox repository.
The exam lasts twenty minutes in total (5 minutes for the theory, 10 minutes for preparation of the exercise and 5 minutes for a discussion of the exercise).
Contacts
q.louveaux@uliege.be
Adaptation of teaching commitments following the COVID-19 pandemic for the Aug-Sept 2020 session
Assessment subjects
Assessment methods
Same as June.
The exam is an oral videoconference exam without preparation and open book.
The exam consists of a theoretical question drawn from the list available in the dox repository. Then an exercise is given to the student who has ten minutes to solve / start the exercise, take a photo of his notes and send it by email to the professor. If the exercise is not finished after 10 minutes, the student orally explains how to finish it. A list of exercise topics will also be made available on the dox repository.
The exam lasts twenty-five minutes in total (5-10 minutes for the theory, 10 minutes for preparation of the exercise and 5-10 minutes for a discussion of the exercise).