73030 - Network Optimization M

Academic Year 2020/2021

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

Learning outcomes

The course introduces the student to graph and network problems and to the main algorithmic techniqes in this area. At the end of the course the student has the ability to model industrial problems that can be described through graphs and networks, and has competence on the main methods for their solution.

Course contents

Prerequisites:
It is required that the student has followed the course Operations Research M or an equivalent course on Operations Research.

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

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

Teaching tools

CRT projector

Blackboard

Application and freeware

Office hours

See the website of Silvano Martello