34878 - Operations research M

Learning outcomes

The course provides advanced theoretical and algorithmic methodologies for the solution of decision problems that arise, in organizational 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 solution either by applying the appropriate optimization algorithm or by implementing a simulation program.

Course 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. Graph theory problems
7.1 Shortest spanning tree
7.2 Shortest paths
7.3 Maximum flows
7.4 Mathematical programming and unimodularity conditions
7.5 CPM
7.6 Hamiltonian circuits and traveling salesman problem
7.7 Vehicle routing problems

8. Complexity theory
8.1 Recognition version
8.2 P and NP classes
8.3 NP-complete problems
8.4 Dynamic programming
8.5 Strong NP-completeness

9. Relaxations
9.1 Relaxation by constraint elimination; continuous relaxation
9.2 Surrogate relaxation
9.3 Lagrangian relaxation
9.4 Relaxation by decomposition
9.5 Subgradient optimization
9.6 Dominance relationships among relaxations
9.7 Reduction methods

10. Approximation and Heuristic Algorithms
10.1 Approximation algorithms and approximation schemes
10.2 Heuristic algorithms
10.3 Metaheuristic algorithms

11 Discrete Simulation
11.1 Generation of pseudo-random numbers
11.2 Main components of a simulation model
11.3 Simulation languages
11.4 Temporary and permanent entities
11.5 Events and event notices
11.6 Experiments

Readings/Bibliography

Textbook: S. Martello, Ricerca Operativa per la Laurea Magistrale, Esculapio (progetto Leonardo), Bologna, 2011.

Slides (in English)

The textbook contains 21 exercises. For additional exercises:

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

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 the laboratory 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 2h30'. 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 testis preserved (within its validity window).

Teaching tools

CRT projector

Blackboard

Applets and freeware

Links to further information

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

Office hours

See the website of Silvano Martello