Teaching code

4S00001

Academic staff

Romeo Rizzi,

Coordinator

Romeo Rizzi

Credits

6

Language

Italian

Scientific Disciplinary Sector (SSD)

MAT/09 - OPERATIONS RESEARCH

Period

Secondo semestre dal Mar 7, 2022 al Jun 10, 2022.

Lessons timetable Moodle Seminars 0

Learning outcomes

The student will encounter in concrete the concepts of: problems, models, formulations of operations research, but also of instances, algorithms, reductions and mappings among problems of the computer science field. The course will propose some models of operations research, at least the following: linear programming (LP), integer linear programming (ILP), max-flows and min-cuts, bipartite matchings and node covers, minimum spanning trees, shortest paths, Eulerian paths, and some models resorting on dynamic programming among which some knapsack variants. For all these models/problems, except PLI, the student will learn the solving algorithms, the properties on which they hinge, and how to conduct their execution. However, besides and beyond this, the course aims at building a good and active relationship, practice, and acquaintance, with general mathematical methodologies and techniques (more typical of discrete math and for this reason not yet fully assimilated from our students) and some basic underpinnings of computer science. In particular, we insist on the dialog with problems and with the art/technique of conjecturing, no occasion is lost to spotlight where invariants and monovariants play a role in proofs, algorithms and data structures. We build up confidence with mathematical induction as an active tool for problem solving, and introducing the dialects of induction most voted to efficiency (divide et impera, recursion with memoization, dynamic programming). Some basic principles of informatics are underlined, like coding, algorithms, data structures, recursion as a counterpart of mathematical induction and of computability. (In some editions of the course first scratch introductions to numerability and computability have been offered). Coming to efficiency, our central perspective, the use of asymptotic notation is justified and adopted, the classes P, NP, coNP are introduced, and the concepts of good characterizations, good conjectures and good theorems are illustrated in length and complexity theory is advertised as a lively source of new methodologies in the art of facing problems and enquiry their intrinsic structural properties. Several aspects of the role and importance of the art of reducing one problem to another are discussed and clarified. The life cycle of a good conjecture, the workflow linking good conjectures and algorithms, the production and interpretation of counterexamples as a means of dialog with the problem, and the possible use of them in obtaining NP-completeness proofs, are all discussed, investigated and exemplified in action. Explicit emphasis is constantly given to the role and use of certificates. Meanwhile these transversal and high competences of methodological interest and imprinting are delivered, the students is asked to learn and develop several concrete procedural competences, in particular within LP, and in an algorithmic treatment of graph theory, introduced as a versatile model and an intuitive and expressive language for the formulation of problems. For a complete and detailed list of all these procedural competences delivered and requested, see the past exams and corrections over the various editions of the course. The notions from computational complexity introduced in the course, and the attention to the languages of the certificates, will lead the student to recognize with more awareness the structure of a sound proof. Dealing with instances, problems, models, both from the perspective of algorithms and of models and formulations, will enforce the attitude and competence in casting simple problems from the applications into mathematical models. The knowledge of the paradigmatic results of linear programming theory (duality, complementary slackness, economic interpretation, sensitivity analysis) will provide the student with important tools in obtaining non-trivial insights on the practical problem from the model.

Program

Operations Research offers quantitative methods and models for the optimal management of resources, and optimization of profits, services, strategies, procedures.
This course of Operations Research gets to Mathematical Programming moving from Algorithmics and Computational Complexity.
After revisiting mathematical induction, recursion, divide et impera, with a curiosity driven problem solving approach, we insist on dynamic programming thinking which gets then exemplified in a few classical models of Operations Research and Computational Biology.
With emphasis on method and techniques, we get involved in formulating, encoding and modeling problems, conjecturing about them, reducing one to the other,
and well characterizing them.
The course offers an in-depth introduction to linear programming.
Following the historical path, we introduce graphs as for modeling,
and explore the basic fundamental results in combinatorial optimization and graph theory.

LIST OF TOPICS:

1. Basic Notions
problems
models
algorithms
complexity

2. Introduction to Algorithms and Complexity
analysis of a few algorithms
design techniques (recursion, divide et impera, recursion with memoization, dynamic programming, greedy)
complexity theory (P, NP, co-NP, good characterizations, good conjectures, examples of NP-completeness proofs)

3. Combinatorial Optimization Models
knapsack problems
Problems on sequences
Problems on DAGs

4. Introduction to Graph Theory
graphs and digraphs as models
a few good characterizations (bipartite, Eulerian, acyclic, planar graphs)
a few NP-hard models (Hamiltonian cycles, cliques, colorability)
shortest paths
minimum spanning trees
maximum flows
bipartite matchings

5. Linear Programming (LP)
the LP and the ILP models (definition, motivations, complexity, role)
geometric method and view (feasibility space,
pivot, duality, dual variables, degeneracy, complementary slackness)
standard and canonical form
simplex method
duality theory
complementary slackness
economic interpretation of the dual variables
sensitivity analysis

BOOKS, NOTES AND OTHER DIDACTIC MATERIALS AND RESOURCES:

At the following page you find a list of available materials (books, notes, videos) about topics covered within the course:

http://profs.sci.univr.it/~rrizzi/classes/RO/materiali

If you find out further effective material help us enlarging this list.

Bibliography

Examination Methods

At the end of the course, a written exam (now on the PC) with various types of exercises and questions on the more procedural competences acquired during the course. You can add (in full or in part) to the mark acquired at the exam by conducting projects aiming at improving aspects and/or materials of the course in a broad sense.
The exam is the very same regardless on whether you have attended or not the course. The archives of the past exams, the relative corrections, and the videos of the classes, all can help overcoming the difficulties of the non-attending student. Despite these resources, the more methodological messages of the course remain difficult to acquire without active participation and attendance to the lessons, and this can penalize the student, also at the exam.
Starting with the 2018/19 edition, with the onset of the COVID-19 and the necessity to spend the exams from remote, we have switched to an electronic format for the exam, followed by a brief oral assessment, confrontation and discussion.
We are still working to refine the platform and materials for this new exam, and we are happy to welcome projects that help us in this complex and costly update. One of the next goals here is to integrate the historical archive with the electronic part.
The materials of the previous years (all the texts of the exams and related corrections from 2011 onwards) remain in any case excellent references. Even before the migration to the electronic format we have always seeked transparency. Even before the migration to electronic format, we always sought transparency on the correction procedures and evaluation mechanisms.

Rather: given that everything is constantly evolving and everyone's participation and contribution is so determinant, even for what is the verification of the skills acquired and the work done, we warmly invite each student to register in the Telegram group of the course which, together with other useful links and resources, can be conveniently reached from the course web page:

http://profs.sci.univr.it/~rrizzi/classes/RO/index.html

We underline a peculiarity of the Operations Research course, the only one in discrete mathematics at the bachelor: the approach and spirit with which you should approach the course and the exam, and what to deliver and elaborate in your answers to the exercises, is actually related to some deep methodological messages that we decided to place at the core of the course. The more the student adopts and interprets these approaches, the more he/she will be proactive in the course and in collaborating to any verification, the more enriching the course and the more fun the exam will be. This will be important in getting the most from the course and achieve full satisfaction and recognition at the exam.