 | | |
| MATH0462-1 | Discrete optimization
|
|
| Duration : | 30h Th, 30h Pr |
|
| Number of credits : |
| Master in Biomedical Engineering, in-depth approach, 1st year | | 5 |
|
| Master in Biomedical Engineering, in-depth approach, 2nd year | | 5 |
|
| Master in Electrical Engineering, in-depth approach, 2nd year | | 5 |
|
| Master of science in computer science and engineering, in-depth approach, 1st year | | 5 |
|
| Master in Computer science, Research Focus, 2nd year | | 6 |
|
| Master in Mechanical Engineering, in-depth approach, 2nd year | | 5 |
|
| Master in Engineering Physics, in-depth approach, 2nd year | | 5 |
|
| Master of science in computer science and engineering, professional focus in management, 1st year | | 5 |
|
| Master in Computer science | | 6 |
|
| Master in Mathematical Sciences, professional focus in computer science, 2nd year | | 6 |
|
|
|
| Lecturer : | Quentin Louveaux |
|
Language(s) of instruction :
|
| French language |
|
Organisation and examination :
|
| Teaching in the first semester, review in January |
|
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.
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 and approximation algorithms. Before we wille have considered some classes of important discrete problems that are well solved, namely flow and matching problems. |
|
Learning outcomes of the course :
|
| 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.
|
|
Prerequisites and co-requisites/ Recommended optional programme components :
|
| 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 project counts for 1/3 of the final mark.
A written exam of exercises counts for 2/3 of the final mark. |
|
Work placement(s) :
|
| |
|
Organizational remarks :
|
| The course is given in the first semester.
The schedule is to be determined with the teacher. |
|
Contacts :
|
| |
|
