Academic Year 2019-2020
OPERATIONS RESEARCH
Teachers:
Giuseppe Lancia
Giuseppe Lancia
Total Course Credits: 6
Teaching Period: First Period
Teaching Language: Inglese
Prerequisites. Basic notions of discrete mathematics, graph theory, linear algebra, algorithms and programming
Teaching Methods. Lecturing at the board. Occasionally, use of the computer to exemplify some optimization software packages
Verification of Learning. Written exam with both multiple-choice questions and problems. The problems are mostly about the formulation of a mathematical model (variables, constraints and objective function) for solving a practical optimization question described in the text. Other problems may ask to apply an algorithm studied in class to a given instance data.
More Information. none
OBJECTIVES
The goal of the course is to teach the main techniques for modeling and solving optimization problems, trying to distinguish between easy (i.e., polynomial) problems and hard problems (i.e., NP-hard). For the former ones, the student should be able to recognize a suitable approach from the literature and apply the corresponding standard algotithm, perhaps adapting it to the specific case. For the latter ones, the student should be able to write an integer LP model, introducing variables and constraints, to be then solved by using a standard software for this type of models.
CONTENTS
The course illustrates the main modeling techniques for solving optimization problems, both tractable than computationally hard. The course introduces mathematical programming techniques, based on linear programming (LP) with both real and integer variables. The geometry of LP is studied (polyhedra), duality, branch-and-bound and cutting planes, totally unimodular matrices. The main notions of computational complexity are recalled. Some standard optimization problems on graphs are discussed such as minimum and maximum path, the maximum matching problem, the assignment, the minimum spanning tree, the maximum flow, the minimum and maximum cut in a graph, the traling salesman problem, the minimum vertex cover, the independent set. For polynomial problems, the solving algorithms from the literature are described. Furthermore, alternative approaches based on (integer) LP are also discussed.
TEXTS
Lecture notes. “Ottimizzazione” by P. Serafini (Zanichelli). “Lezioni di Ricerca Operativa” by M. Fischetti (Libreria Progetto)
