Course Unit Profile

<--- Back to Course Diagram

Basic Information

Course Unit Title: OPERATIONS RESEARCH

Course Unit Code: 029AA

Level of course unit

First Cycle (Laurea) Degree Programme in Computer Science

Year of study

Second year

Semester when the course is delivered

First semester

Number of ECTS credits allocated: 6

Name of Lecturer(s):

Prof.: Massimo Pappalardo
Email: massimo.pappalardo@unipi.it

Prof.: Giandomenico Mastroeni
Email: giandomenico.mastroeni@unipi.it

Language of instruction

Italian

General Information

Learning outcomes

The course will introduce the student to the main tools and techniques of Operations Research, the discipline of formulating and solving mathematical models corresponding to finding the "best possible" solutions to decision problems. At the end of the course the student will have a basic knowledge of the main issues arising when creating a mathematical model that need be practically solved in "reasonable" time, which is usually a nontrivial task in that most optimization problem are inherently "hard". In particular the student will know the mathematical foundations and the most relevant implementation details (complexity, data structures, ...) of the solution algorithms for two important classes of "easy" problems (network flows and linear programming); furthermore, she/he will be able to construct formulations using the most useful formalism in practice, that of Integer Linear Programming.




Course contents

The course will cover the following material:
- Linear Programs:
= definitions, geometrical and algebraic properties
= duality theory
= the primal and dual simplex algorithm
- Network Flow problems and algorithms:
= Maximum Flows
= Min-Cost Flows
- Integer Linear Programs:
= Cutting plane methods
= "Branch and Bound"




Specific Information

Prerequisites, co-requisites, as a prerequisite for further study

Prerequisites

None.

Co-requisites

None.

Prerequisite for

None.

Mode of delivery

Delivery

face to face

Attendance

Advised

Teaching methods

Learning activities

Recommended or required reading

Pappalardo M., Passacantando M., “Ricerca Operativa”, Pisa University Press, 2012.

Assessment methods and criteria

Assessment methods

Further information

The written exam usually consists in solving exercises covering all the material of the course, and in particular (but not exclusively) the algorithmic aspects. A sufficient (or almost so) written exam is a prerequisite to the oral exam; it is only waived for student successfully passing the two in-course tests. The oral exam will in any case cover all the theoretical and algorithmic material of the course.

Assessment criteria

The written and oral exam aim at verifying that the student has understood the main algorithmic techniques presented during the course, their theoretical foundations, and she/he is capable of formulating mathematical models of simple fragments of reality with at least a basic understanding of the impact of the modeling choices on the difficulty of the resulting optimization problem.

Work placement

No

<--- Back to Course Diagram