Basic knowledge of linear programming and the simplex algorithm
- 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
The contribution of this Teaching Unit to the development and command of the skills and learning outcomes of the programme(s) can be accessed at the end of this sheet, in the section entitled “Programmes/courses offering this Teaching Unit”.
- Formulation of combinatorial optimization and integer programming problems.
- Finding bounds on the optimal value and using them to prove optimality
- Recognizing and solving certain easy problems - network flows, trees, matching and assignment problems
- Introduction to the distinction between easy and hard problems: NP-hardness
- Intelligent enumeration - the branch-and-bound algorithm
- Lagrangian relaxation
- Introduction to cutting plane algorithms
- Heuristic methods to find good solutions quickly
An exercise session is held approximately every two weeks. One or several home exercises on a software (Matlab or other) will be proposed as well.
Integer Programming, L.A. Wolsey, Wiley, New York 1998.