72935 - Operations Research M

Learning outcomes

Mathematical models, linear programming, simplex algorithm, duality. Integer linear programming, cutting planes, branch-and-bound. Complexity. Dynamic programming. Discrete simulation.

Course contents

Prerequisites:
It is required that the student understands written English in order to follow the course slides.

Contents:
1. The scientific method: systems, models, methodologies

2. Mathematical Programming
2.1 Optimization problems
2.2 Convex sets and functions
2.3 Convex programming

3. Linear programming
3.1 General, canonical and standard forms
3.2 Bases e basic solutions
3.3 Convex polytopes

4. Simplex algorithm
4.1 Moving among basic solutions
4.2 Tableau and pivoting
4.3 Optimality criterion
4.4 Simplex algorithm
4.5 Two-phase method
4.6 Geometrical aspects

5. Duality
5.1 Dual of a linear programming problem
5.2 Duality properties
5.3 Farkas' lemma
5.4 Complementary slackness
5.5 Dual simplex algorithm
5.6 Primal-dual algorithm

6. Integer linear programming
6.1 Unimodularity
6.2 Cutting-plane algorithms and Gomory cuts
6.3 Branch-and-bound algorithm
6.4 Exploration strategies
6.5 0-1 knapsack problem
6.6 Branch-and-cut algorithms

7. Complexity theory
7.1 Recognition version
7.2 P and NP classes
7.3 NP-complete problems
7.4 Dynamic programming
7.5 Strong NP-completeness

8 Discrete Simulation
8.1 Generation of pseudo-random numbers
8.2 Main components of a simulation model
8.3 Simulation languages
8.4 Temporary and permanent entities
8.5 Events and event notices
8.6 Experiments

Readings/Bibliography

Textbook: Libro di testo: S. Martello, Ricerca Operativa, Esculapio (progetto Leonardo), Bologna, 2014.

Slides (in English)

The textbook contains a number of exercise solutions. For additional ones:

S. Martello, D. Vigo, Esercizi di Ricerca Operativa, Esculapio (progetto Leonardo), Bologna, 2003.
S. Martello, D. Vigo, Esercizi di Simulazione Numerica, Esculapio (progetto Leonardo), Bologna, 2001.

Further readings:

C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.

S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990 (free download)

 

R. Burkard, M. Dell'Amico, S. Martello, Assignment Problems - Revised reprint, SIAM, Philadelphia, 2012.

Teaching methods

The course consists of lectures and class exercises.
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.

Assessment methods

Written test, followed, in case of positive outcome, from an oral test.

The written test consists in writing the simulation or mathematical 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 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 obtained in the written test is preserved (within its validity window).

Teaching tools

Applet and freeware

Office hours

See the website of Valentina Cacchiani

See the website of Silvano Martello