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 spoken Italian in order to follow the lectures.

MODULE 1: Silvano Martello

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 Sensitivity analysis

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

6.7 Software and freeware

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

MODULE 2: Valentina Cacchiani

Discrete Simulation: introduction to discrete simulation, static and dynamic description of a system, temporary and permanent entities, events and event notices. Exercizes on modeling realistic systems.

Readings/Bibliography

MODULE 1

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

Slides (in English)

The textbook contains several exercise solutions. For additional ones:

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

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

 

MODULE 2

Slides available on Insegnamenti OnLine.

For additional simulation exercises:

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

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

The assessment method consists of a written test (that includes both modules), followed, in case of positive outcome, from an oral test.

The written test is in Italian; the solution can be provided in Italian or English. The oral test can be taken in Italian or English.

The written test lasts approximately two hours and consists of an exercise on MODULE 1 (definition of a mathematical model of a system and solution, through the appropriate algorithms, of simple optimization problems), which is given a score of 15 points, and an exercise on MODULE 2 (definition of a simulation model of a system) which is given a score of 15 points. The two exercises must be solved in the same written test.

When the test is handed in for the first time, a 3 point bonus is added to the mark. Therefore, the written test mark is given by:

score of the written test on Module 1 + score on the written test on Module 2 + bonus (the first time only).

Marked tests are only available on the settled date (usually coinciding with that of the next oral test).

The candidates who obtain a positive mark in the written test must have an oral test on the theoretical contents of Module 1. 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).

The students who decline to record the obtained overall mark must repeat both the written and the oral test.

ONLINE ASSESSMENT

In case the assessment is done online, please check the instructions in section "News".

Teaching tools

Applets and freeware

Office hours

See the website of Silvano Martello

See the website of Valentina Cacchiani