This page is not used anymore as a teaching support for the course: Please refer to the suitable team on the MS Teams platform of Università di Roma Tor Vergata.
for the master course ICT and Internet Engineering (6 and 9 credits). Please report me any problem in reading this page. Grazie! Page last updated on Dec. 13, 2021
Lecturer: Andrea Pacifici. Email (or call 067259 7795) and I will be glad to meet you for any question concerning the course. Usually, I am available just after the classes as well.
Course meeting sessions: (Also) in this academic year 2021-22, the lectures will be in the form of reading classes: Students are supposed to read and understand the subjects that will be assigned weekly. Meetings are every Tuesday 9:30 (AM) in room B11 and simultaneously offered online on MS Teams. From Oct. 12, as a result of an agreement with attending students, meetings are only held online on the MS Teams academic platform: I would like to recall that any enrolled student may require lectures to be held in class, any time.
Application: It is important that you visit the delphi website and enroll in the course.
Description: ORMNO is a graduate subject in the theory and practice of linear and network optimization. A first part of the course is devoted to a substantial introduction to mathematical programming and includes model formulations, geometry of linear optimization, duality theory, the simplex method, sensitivity analysis, integer linear programming with the main objective to solve real world problems problems with the aid of computer software, discrete optimization formulations and algorithms. We will focus then on Network flow problems which form a subclass of linear programming problems with several applications in telecom, as well as a number of other domains (transportation, logistics, manufacturing, computer science, project management, finance, etc.) We will address key special cases of network flow problems: the shortest path problem, the maximum flow problem, the minimum cost flow problem, and the multi-commodity flow problem. We will also consider other extensions and relevant applications of network flow problems.
Relevant news are displayed here.
Readings: See the calendar at the bottom of this page.
NEW! Download AMPL here (licence expires on 30/09/2022). You may find installation instruction in this page.
The course page of A.Y. 2016-17 is here. (Pretty same stuff of this one but you may interested in the list of lectures reported in the Calendar section.)
Textbooks and course material
Course requirements and grading
Exams
Links
Homeworks
Calendar
For the first part of the course on linear optimization you may refer to the book `Introduction to Linear Optimization', by Bertsimas and Tsitsiklis, Athena Scientific 1997, ISBN 1-886529-19-1. (If needed, you may view a copy of the book upon request.) `Network flows' are covered by the homonymous extensive book by Ahuja, Magnanti, and Orlin—it should not be hard to download a free (legal) copy of this book. Another useful resource ("Introduction to Linear Optimization" by A. Nemirovski) can be found here.
Throughout the course I will be heavily relying on examples, lecture notes, assigments, and exercises which can be found on the wonderful MIT OpenCourseWare, for instance here and here. I guess you may behave accordingly.
Requirements: the minimum requirement to attend this course is to be familiar with basic concepts of linear algebra and calculus.
Examination consists solely of a written exam for those who take 6 credits. The students who take 9 credits will be also required to work in a project (details to be discussed). There are 6 exam dates per year (please refer to delphi system for details and registration). A few examples of written exams can be found here.
Winter: x Feb. y Feb.
Summer: x Jun. y Jul.
Fall: x Sept. y Sept.
GUROBI - Optimization Software
IBM ILOG CPLEX - Optimization Software
MIT OpenCourseWare a large amount of resources for students and teachers as well (and not only in OR)
Michael Trick's Home Page - news, curiosities and folklore in OR.
INFORMS - web page of the U.S. "International Federation of Operations Research and Management Science"
Project assignments
...
In questa sezione le note delle lezioni online 2020-21 (in Italian).
Note sui progetti d'esame proposti.
13. Tue Dec 14. Minimum cost flow problems. Notation and LP models.
12. Tue Dec 7. Max Flow Min Cut (MFMC) problem: Ford and Fulkerson algorithm (definitions of residual network, augmenting path). "Pathological" cases.
11. Tue Nov 30. Network flows: Max Flow Min Cut (MFMC) problem: Definition, properties, (s,t)-cuts and its capacity, examples. LP formulation for MFMC.
10. Tue Nov 23. Strong duality property. Duality and min-max relations in combinatorial problems.
9. Tue Nov 16. Duality for linear optimization (from Lagrangean relaxation to the dual of a LP) . Weak duality property.
8. Tue Nov 9. Relaxation of an optimization problem. Facility location problems: "weak" and "strong" MIP formulations.
7. Tue Nov 2. Modeling with integer variables. Binary knapsack problem and its linear relaxation. Graphs, networks: Basic definitions. ILP formulation of the minimum (cardinality) vertex cover problem (Reading: Sec.s 2.1, 2.2, 2.3 of the Ahuja Magnanti Orlin book). Uncapacitated Facility Location (UFL): definition.
6. Tue Oct 26. Again on the simplex method: Finding initial BFS (Reading: Bertsimas Sec.s 3.1, 3.5 and you may want to look at 3.4).
5. Tue Oct 19. Basic notions on the simplex method. Changing bases. Examples. (Reading: Bertsimas Sec.s 3.1, 3.5)
4. Tue Oct 12. Geometry of Linear Programming: Polyhedra and their representation (Reading: Bertsimas book, Sections 2.1-2.6).
3. Tue Oct 5. Simplex method: basic (feasible) solutions and their geometric representation [Reading for the next meeting: Geometry of Linear Programming. Bertsimas Sec.s 1.5, 2.1, 2.2, 2.3, 2.5, 2.6).]
2. Tue Sept 28. Modeling of decision problems via linear and integer linear programming. Examples: Scarce resource allocation via LP and max cardinality matching.
1. Classes starts on Thu, September 23, 2021 Administrivia. Introduction to linear optimization. Examples. `Components' of a mathematical program.
Readings: Bertsimas, Chapt. 1: Sec.s 1,2,4,5; Chapt. 2: Sec.s 1, 2.