00884 - Operation Research

Academic Year 2020/2021

  • Docente: Daniele Vigo
  • Credits: 6
  • SSD: MAT/09
  • Language: Italian
  • Moduli: Daniele Vigo (Modulo 1) Roberto Baldacci (Modulo 2)
  • Teaching Mode: Traditional lectures (Modulo 1) Traditional lectures (Modulo 2)
  • Campus: Cesena
  • Corso: First cycle degree programme (L) in Computer Science and Engineering (cod. 8615)

Learning outcomes

At the end of the course, the student knows the main models and algorithms for linear and integer programming and graph theory.

Course contents

Module 1
a. Mathematical models of optimization problems
Definition of a mathematical model, decision variables, objective function and requirements or constraints. Mathematical modeling techniques.
Examples of mathematical models, taken from systems and networks, data mining, logistics, computational biology and computer applications.


b. Continuous Linear Programming (PLC) and Integer Programming (PLI).

 Mathematical models with continuous variables. Geometric resolution. PLC theory and simplex algorithm
Mathematical models with integer variables. Geometric interpretation. Properties of PLI problems. Relaxation techniques. Cutting-plane algorithms (CP). Branch-and-bound method (B&B). Applications of the B&B technique.


Module 2

Elements of graph theory and its main problems.

 Main definitions of graph theory. Minimum cost spanning trees (SST). Minimal paths (CM). Network flow problems (FR), maximum flow, minimum cost flow. Linear assignment.

Readings/Bibliography

  • Lecture notes and slides by teachers available online

Texts for consultation only

  • Matteo Fischetti, Operations Research Lessons, Project Library.
  • C. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, NY.
  • R.K.Ahuja, T.L.Magnanti, J.B.Orlin, "Network flows: theory, algorithms and applications", Prentice Hall.
  • M. Gondran, M. Minoux, "Graphs and Algorithms", John Wiley.

Teaching methods

Frontal lessons. Numerical exercises on the various algorithms for solving PL, PLI, SST, CM and FR problems.

Implementation of algorithms and models in laboratory through programming languages and use of solvers.

Assessment methods

  • Exercises based on solving SST, CM and FR problems. Exercises on the different illustrated algorithms.
  • The learning assessment takes place through a written test, which has the purpose of examining the acquisition of the knowledge required by the program of both modules of the course.

Teaching tools

Teaching material, lecture notes, slides, exercises and code examples available on the net. Use of programming languages and solvers.

Office hours

See the website of Daniele Vigo

See the website of Roberto Baldacci

SDGs

Industry, innovation and infrastructure

This teaching activity contributes to the achievement of the Sustainable Development Goals of the UN 2030 Agenda.