Operations Research (2014/2015)

Course code
4S00001
Name of lecturer
Romeo Rizzi
Coordinator
Romeo Rizzi
Number of ECTS credits allocated
6
Academic sector
SECS-S/06 - MATHEMATICAL METHODS OF ECONOMICS, FINANCE AND ACTUARIAL SCIENCES
Language of instruction
Italian
Period
II sem. dal Mar 2, 2015 al Jun 12, 2015.

Lesson timetable

II sem.
Day Time Type Place Note
Tuesday 4:30 PM - 6:30 PM lesson Lecture Hall G  
Thursday 11:30 AM - 1: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 and 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