 | |
| MATH0462-1 | Discrete optimization
 |
|
| Duration : | 30h Th, 30h Pr |
|
| Credits/ECTS : |
| civil engineering in electricity, 3rd year | | | | 6,5 |
|
| civil engineer in computer sciences, 3rd year | | | | 5,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 Engineering Physics, in-depth approach, 2nd year | | Toute l'année | | 5 |
|
|
|
| Holder(s) : | Quentin Louveaux |
|
| Language : | Langue française |
|
| 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.
The second part tackles problems that can be modeled in a graph. In particular we see a series of problems that can be solved efficiently in a graph. We describe also the hard problems that often arise in a graph.
Finally the last part of the course deals with the solving techniques of integer programs: mainly branch-and-bound, branch-and-cut and lattice reformulation. |
|
| 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 : | Three main references are used:
For the first part (and the lattices):
D. Bertsimas, R. Weismantel, Optimization over Integers. Dynamic Ideas, 2005.
For the second part:
R. Ahuja, T. Magnanti, J. Orlin, Network flows. Prentice Hall, 1993.
For the third 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. |
|
|
| |
