Operational research complements
A.Y. 2020/2021
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.
Lesson period: First semester (In case of multiple editions, please check the period, as it may vary)
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
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
· 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.
Educational website(s)
Professor(s)