 | |
| MATH0462-1 | Discrete optimization
 |
|
| Duration : | 30h Th, 30h Pr |
|
| Credits/ECTS : |
| Master in Biomedical Engineering, in-depth approach, 2nd year | | Toute l'année | | 5 |
|
| Master in Electrical Engineering, in-depth approach, 2nd year | | Toute l'année | | 5 |
|
| Master in Computer Engineering, in-depth approach, 2nd year | | Toute l'année | | 5 |
|
| Master in Computer science, Research Focus, 2nd year | | Toute l'année | | 6 |
|
| Master in Mechanical Engineering, in-depth approach, 2nd year | | Toute l'année | | 5 |
|
| Master in Engineering Physics, in-depth approach, 2nd year | | Toute l'année | | 5 |
|
| Master in Statistics : General, Professional focus, 2nd year | | Toute l'année | | 6 |
|
|
|
| Holder(s) : | Quentin Louveaux |
|
| Language : | French language |
|
| Course 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. Indded in particular the problems where binary decisions (such as yes or no) have to be taken often arise in practical applications. |
|
| Course objective : | 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, lattice reformulation, lagrangian relaxation and approximation algorithms. |
|
| Prerequisites : | A basic course in linear programming. |
|
| Workshops : | Five series of exercicses must be given roughly every three weeks.
A project consists of, either implementing some algorithm, or reading an article. At the end the project must be presented in a seminar-like fashion. |
|
| Written notes : | Two main references are used:
For the first part (and the lattices 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 : | The five exercises count for 25%.
The project counts for 25%.
An oral exam with preparation (possibly with open book) counts for 50%. |
|
| Remarks : | The course is given in the first semester.
The schedule is to be determined with the teacher. |
|
|
| |
