Operational Research Complements
A.Y. 2022/2023
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
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-1ILP
· Dynamic programming
3. Lagrangean relaxation
4. Column generation, branch-and-price
· 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-1ILP
· Dynamic programming
3. Lagrangean relaxation
4. Column generation, branch-and-price
Prerequisites for admission
Operations research. Algorithms and data-structures.
Teaching methods
Lectures.
Teaching Resources
· G. Nemhauser, L. Wolsey, "Integer and Combinatorial Optimization", Wiley 1999.
Assessment methods and Criteria
The exam consists of a project or a seminar and in an oral exam.
The project requires to design an optimization algorithm for an NP-hard problem, to code it in a programming language (chosen by the student) and to test it on some instances. The seminar requires to illustrate and to discuss a scientific paper. The oral exam encompasses the whole program of the course. Before starting the project or the seminar a short written exam is required to test whether the student is sufficiently well-prepared.
The project requires to design an optimization algorithm for an NP-hard problem, to code it in a programming language (chosen by the student) and to test it on some instances. The seminar requires to illustrate and to discuss a scientific paper. The oral exam encompasses the whole program of the course. Before starting the project or the seminar a short written exam is required to test whether the student is sufficiently well-prepared.
Professor(s)