72935 - Operations Research M

Academic Year 2013/2014

  • Teaching Mode: Traditional lectures
  • Campus: Bologna
  • Corso: Second cycle degree programme (LM) in Computer Engineering (cod. 0937)

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: S. Martello, Ricerca Operativa, Esculapio (progetto Leonardo), Bologna, 2014.

Slides

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.
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 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

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