Complements of Operating Research
A.Y. 2024/2025
Learning objectives
The course aims to broaden the foundations of mathematical programming. The problems of nonlinear optimization will be addressed and the techniques to face linear and integer linear programming problems will be deepened.
Expected learning outcomes
Ability to choose the most suitable tools to solve non-linear optimization problems. Ability to apply decomposition techniques to deal with integer linear programming problems, skills related to the techniques used by commercial solvers.
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-1LP. Dynamic programming.
3. Lagrangean relaxation
4. Column generation, branch-and-price
2. Implicit enumeration algorithms. Branch-and-bound, branch-and-cut.. Balas' algorithm for 0-1LP. Dynamic programming.
3. Lagrangean relaxation
4. Column generation, branch-and-price
Prerequisites for admission
Operations research
Teaching methods
Lectures.
Teaching Resources
G. Nemhauser, L. Wolsey, "Integer and Combinatorial Optimization", Wiley 1999.
Assessment methods and Criteria
The exam consists of three steps.
1. A short written exam to verify that the student has got the necessary knowledge
to enter the next steps.
2a. A project in which the student is required to design an optimization algorithm for a combinatorial optimization problem agreed with the teacher,
to code it in a programmming language selected by the student and to evaluate it experimentally.
2b. As an alternative to the project, the second step can consist of a seminar of 20-30 minutes on a paper agreed with the teacher.
3. In all cases, the exam is concluded by an oral exam on the topics not covered by the project or seminar.
1. A short written exam to verify that the student has got the necessary knowledge
to enter the next steps.
2a. A project in which the student is required to design an optimization algorithm for a combinatorial optimization problem agreed with the teacher,
to code it in a programmming language selected by the student and to evaluate it experimentally.
2b. As an alternative to the project, the second step can consist of a seminar of 20-30 minutes on a paper agreed with the teacher.
3. In all cases, the exam is concluded by an oral exam on the topics not covered by the project or seminar.
MAT/09 - OPERATIONS RESEARCH - University credits: 6
Lessons: 48 hours
Professor:
Righini Giovanni
Shifts:
Turno
Professor:
Righini GiovanniProfessor(s)