34878 - Operations research M

Learning outcomes

(Inserita nella sezione in Inglese in quanto la sezione in Italiano non risulta modificabile per un errore di sistema)

Il corso integra le conoscenze acquisite nel corso 'Fondamenti di Ricerca Operativa L-A' (che ne costituisce propedeuticita' indispensabile), introducendo teorie e metodologie algoritmiche avanzate per la soluzione di problemi decisionali che si presentano, in ambito sociale ed industriale, quando si debbono gestire e coordinare in modo ottimale attivita' e risorse disponibili in quantita' limitata.
Gli studenti acquisiranno la capacita' di:
1. rappresentare, mediante modelli di programmazione lineare, di teoria dei grafi e di simulazione numerica, casi reali in cui si presentano problemi di ottimizzazione;
2. determinare la soluzione del problema, a seconda dei casi mediante l'opportuno algoritmo di ottimizzazione o mediante l'implementazione di un programma di simulazione.

 
The course advances the knowledge acquired in the course 'Fundamentals of Operations Research L-A', which is a necessary requirement. It provides advanced theoretic and algorithmic methodologies for the solution of decision problems that appear, in social and industrial activities, when limited resources have to be optimally managed.
The students will acquire the capability of:
1. representing, through linear programming, graph theory and simulation models, real cases in which optimization problems are involved;
2. determining the optimal solution either by applying the appropriate optimization algorithm or by implementing a simulation program.

 

Course contents

1. DISCRETE EVENT SIMULATION:
1.1 probability theory: random variables;
1.2 generation of pseudo-random numbers, inverse transformation;
1.3 static and dynamic description of a system;
1.4 event scheduling;
1.5 flow-charts for simulation programs;
1.6 SIMSCRIPT II.5 .
2. LINEAR PROGRAMMING:
2.1 main properties of convex programming;
2.2 linear programming and the simplex algorithm (recapitulation);
2.3 duality: dual problem, complementary slackness;
2.4 dual simplex algorithm;
2.5 primal-dual algorithm.
3. INTEGERE LINEAR PROGRAMMING:
3.1 unimodularity;
3.2 cutting planes: Gomory cuts;
3.3 branch-and-bound;
3.4 mixed integer linear programming, binary programming;
3.5 0-1 knapsack problem;
3.6 branch-and-cut (hints)
4 GRAPH PROBLEMS:
4.1 graph theory (recapitulation);
4.2 relationships between shortest paths, flows and linear programming;
4.3 unimodularity of the incidence matrix;
4.4 Hamiltonian circuits: an enumeration algoritm. 
5 COMPLEXITY THEORY:
5.1 classes P and NP; NP-complete problems;
5.2 complexity of the main combinatorial optimization problems;
5.3 dynamic programming;
5.4 strongly NP-complete problems.
6. BRANCH-AND-BOUND ALGORITHMS:
6.1 branching schemes;
6.2 continuous, Lagrangian and surrogate relaxation;
6.3 applications to the 0-1 multiple knapsack problem;
6.4 reduction procedures;
6.5 approximation algorithms: computational experiments, probabilistic analysis, worst-case behavior;
6.6 metaheuristic algorithms.
7. PROBLEMS AND METHODS IN COMBINATORIAL OPTIMIZATION:
7.1 Matching problems;
7.2 Linear sum assignment problem;
7.3 Other linear assignment problems;
7.4 Quadratic assignment problems
7.5 Metaeuristic techniques;
7.6 Packing problems;
7.7 Transportation problems.

 

Readings/Bibliography

S. Martello, 'Ricerca Operativa LS',
Esculapio (progetto Leonardo), Bologna, 2009 edition.

The book contains:
1. transparencies used for the lectures;
2. exercises.
 
The book is not mandatory for the students who regularly attend lectures and class exercises.

The teacher will provide additional material.
 
Further readings:
 
S. Martello, D. Vigo, 'Esercizi di Simulazione Numerica', Esculapio (progetto Leonardo), Bologna, 2001.
S. Martello, D. Vigo, 'Esercizi di Ricerca Operativa',
Esculapio (progetto Leonardo), Bologna, 2003.
C. Papadimitriou, K. Steiglitz, 'Combinatorial Optimization', Prentice Hall, 1982.
S. Martello, P. Toth, 'Knapsack Problems: Algorithms and Computer Implementations',
Wiley, 1990 (free download at http://www.or.deis.unibo.it/knapsack.html )

R. Burkard, M. Dell'Amico, S. Martello, 'Assignment Problems', SIAM, Philadelphia, 2009 (see www.assignmentproblems.com) .

Teaching methods

Teaching methods: The course consists of lectures, class exercises and laboratory.
The lectures discuss the theoretical and algorithmic aspects of the various arguments.
In class exercises, industrial cases  are introduced, and the corresponding mathematical or simulation models are developed. The mathematical models are solved through the algorithms developed in the lectures. In laboratory classes
(which are optional and free) the students can use commercial software for linear programming and integer linear programming, and the simulation language SIMSCRIPT II.5 .

Assessment methods

Written test, followed, in case of positive outcome, from an oral test. The written test consists in writing the simulation model of a system and in solving, through the appropriate algorithms, simple optimization problems. The duration of the written test is approximately two hours. The candidates who obtain a positive mark in the written test must have an oral test on the the theoretical contents of the course. Let k be the examination session in which a positive mark in the written test has been obtained: the oral test must be taken within examination session k+2. The overall mark is given by:

2/3 (written mark) + 1/3 (oral mark),

rounded up.

For the students who fail the oral test, the mark obtianed in the written test is preserved (within its validity window) .

Teaching tools

Overhead projector

CRT projector

Links to further information

http://www.or.deis.unibo.it/staff_pages/martello/cvitae.html

Office hours

See the website of Silvano Martello