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
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
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)