73030 - Network Optimization M

Learning outcomes

Introduction to graph theory. Trees, paths, flows in transportation networks, PERT-CPM methods, Hamiltonian circuits, routing problems. Lagrangian and surrogate relaxation. Approximation, heuristic and metaeuristic algorithms.

Course contents

Prerequisites:
It is required that the student has followed the course Operations Research M.

Contents:
1. Fundamentals from Operations Research M

2. Graphs and networks theory
2.1 Introduction
2.2 Terminology

3. Basic problems on graphs
3.1 Shortest spanning tree
3.2 Shortest path problems
3.3 CPM method for project management0

4. Flows in networks
4.1 Maximum flow problems
4.2 Minimum cost flow problems
4.3 Mathematical models for graph and network problems
4.4 Unimodularity conditions

5. Optimal circuits
5.1 Hamiltonian circuits
5.2 Traveling salesman problem
5.3 Vehicle routing problems

6. Relaxations
6.1 Surrogate relaxation
6.2 Lagrangian relaxation and Lagrangian decomposition
6.3 Subgradient optimization
6.4 Reduction techniques

7. Approximation and heuristic algorithms
7.1 Greedy algorithms
7.2 Worst-case performance
7.3 Local search
7.4 Metaheuristic algorithms

Readings/Bibliography

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

Slides (in English)

The textbook contains a number of exercise solutions. Additional exercises in:

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

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 graph or network models are developed. The 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 graph or network model of a system and in solving, through the appropriate algorithms, simple optimization problems. The duration of the written test is approximately one hour.

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