Operational research complements

A.Y. 2020/2021
6
Max ECTS
48
Overall hours
SSD
MAT/09
Language
English
Learning objectives
The course aims at presenting some algorithmic techniques in Operations Research, for solving mixed-integer linear programming as well as non-linear programming problems.
Expected learning outcomes
Knowledge about algorithms to solve NP-hard optimization problems.
Course syllabus and organization

Single session

Responsible
Lesson period
First semester
Live lectures will be recorded and made available on-line. Some lectures could be pre-recorded; in this case the lectures scheduled according to the timetable will be used for revising and possibly clarifying the content of the video-lectures.
Course syllabus
1. Integer and mixed-integer linear programming.
· Linear programming (recall).
· Geometric interpretation of (M)ILP, polyhedral theory.
· Cutting planes.

2. Implicit enumeration algorithms
· Branch-and-bound, branch-and-cut.
· Balas' algorithm for 0-1 ILP
· Dynamic programming

3. Lagrangean relaxation

4. Column generation, branch-and-price

5. Non-linear programming
· Unconstrained optimization
· Constrained optimization
Prerequisites for admission
Computer programming, Algorithms and data-structures, Operations research.
Teaching methods
Lectures.
Teaching Resources
· G. Nemhauser, L. Wolsey, "Integer and Combinatorial Optimization", Wiley 1999.
Assessment methods and Criteria
A project and an oral exam. The project consists of coding an optimization algorithm for a combinatorial problem and testing its performances. The oral exam encompasses the whole course program.
MAT/09 - OPERATIONS RESEARCH - University credits: 6
Lessons: 48 hours
Professor: Righini Giovanni
Educational website(s)
Professor(s)