# Operations Research (2015/2016)

Course code
4S00001
Name of lecturer
Romeo Rizzi
Coordinator
Romeo Rizzi
Number of ECTS credits allocated
6
MAT/09 - OPERATIONS RESEARCH
Language of instruction
Italian
Period
II semestre dal Mar 1, 2016 al Jun 10, 2016.

#### Lesson timetable

II semestre
Day Time Type Place Note
Tuesday 2:30 PM - 6:30 PM lesson Lecture Hall G from Mar 1, 2016  to Mar 7, 2016
Tuesday 2:30 PM - 6:30 PM lesson Lecture Hall G from Mar 15, 2016  to Jun 10, 2016
Thursday 4:30 PM - 6:30 PM lesson Lecture Hall G

#### Learning outcomes

This course aims to introduce the student to some basic models and to the main methodologies in the optimization field, with a particular attention to dynamic programming, combinatorial optimization, graphs, linear programming. Complexity theory is introduced and used as a tool advertising its methodological impact. The role of (integer) linear programming within the OR community is illustrated.

#### Syllabus

Basic notions: models and algorithms, computational complexity, recursion and induction, invariants and monovariants, graphs, convex sets, polyhedra and cones.

Some of the models in Dynamic Programming: maximum increasing subsequence, maximum common subsequence, knapsack models.

Some of the models in graphs: Eulerian ed Hamiltonian paths and cycles, planar graphs and their duals, bipartite graphs, shortest paths, minimum spanning trees, max flow/min cut, maximum matching.

Linear programming: mathematical formulation of linear programming problems; equivalent forms, standard form; mathematical structure, geometry of linear programming, properties.
The simplex algorithm: vertices and basic solutions; optimality conditions; tableau method, auxiliary problem, two-phases method.
Duality theory: the fundamental duality theorem of linear programming, the dual simplex algorithm; economic interpretation; sensitivity analysis.
Integer linear programming: the cutting plane method; the branch and bound.
Network optimization: the minimum spanning tree problem, the shortest path problem, the maximum flow problem.

A more detailed program as intended, the day-by-day program of the last edition of the course, and the ongoing program of the current edition are available at the web-page of the course:

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

#### Assessment methods and criteria

Written final examination.

Past exams with answers can be found at the web-page of the course:
http://profs.sci.univr.it/~rrizzi/classes/RO/index.html