Course Details for A.Y. 2016/2017

The information on this page refer to the academic year 2016/2017. Therefore, several links are not available and data may be incomplete. To read the current information on the course, if it is still available, go to the university course catalogue . To read information relating other academic years, use the list at the bottom of this page.

A. Year:

2016/2017

Name:

Network Optimization / Network Optimization

Type:

Module

Main course:

Network Design / Network design

Basic information

Code:

DT0060

Sector:

MAT/09

Credits:

: Master Degree in Computer Science 6 CFU (c)

Term:

2^nd semester

Degree(s):

Master Degree in Computer Science 1^st anno curriculum SEAS Compulsory

Language:

English

Teacher(s):

Fabrizio Rossi

Same as:

Network optimisation
Network Optimization
Network Optimization

Course Objectives

Ability to recognize and model network optimization problems as Integer Linear Programming problems. Knowledge of fundamental algorithmic techniques for solving large scale Integer Linear Programming problems. Knowledge of commercial and open source Integer Linear Programming solvers.

Course Content

Formulations of Integer and Binary Programs: The Assignment Problem; The Stable Set Problem; Set Covering, Packing and Partitioning; Minimum Spanning Tree; Traveling Salesperson Problem (TSP); Formulations of logical conditions.
Mixed Integer Formulations: Modeling Fixed Costs; Uncapacitated Facility Location; Uncapacitated Lot Sizing; Discrete Alternatives; Disjunctive Formulations.
Optimality, Relaxation and Bounds. Geometry of R^n: Linear and affine spaces; Polyhedra: dimension, representations, valid inequalities, faces, vertices and facets; Alternative (extended) formulations; Good and Ideal formulations.
LP based branch-and-bound algorithm: Preprocessing, Branching strategies, Node and variable selection strategies, Primal heuristics.
Cutting Planes algorithms. Valid inequalities. Automatic Reformulation: Gomory's Fractional Cutting Plane Algorithm. Strong valid inequalities: Cover inequalities, lifted cover inequalities; Clique inequalities; Subtour inequalities. Branch-and-cut algorithm.
Software tools for Mixed Integer Programming
Lagrangian Duality: Lagrangian relaxation; Lagrangian heuristics.
Network Problems: formulations and algorithms. Constrained Spanning Tree Problems; Constrained Shortest Path Problem; Multicommodity Flows; Symmetric and Asymmetric Traveling Salesman Problem; Vehicle Routing Problem Steiner Tree Problem; Network Design. Local Search Tabu search and Simulated Annealing MIP based heuristics
Heuristics for network problems: local search, tabu search, simulated annealing, MIP based heuristics.

Learning Outcomes (Dublin Descriptors)

On successful completion of this course, the student should

Know and define single objective network optimization problems
Use and design exact or heuristic algorithms to solve single objective network optimization problems
Ability to judge models and methods to tackle network optimization problems
Ability to explain the models, the algorithms and the computational complexity needed to solve network optimization problems
Ability to learn state-of-art algorithms for network optimization problems

Prerequisites and Learning Activities

Basic knowledge of: Discrete Mathematics, Linear Programming, Algorithms and Data Structures, Computational complexity. Knowledge of at least one programming language.

Assessment Methods and Criteria

Written text exam and assignment

Textbooks

L.A. Wolsey, Integer Programming , Wiley. 1998.

Internet Resources

Homepage:

http://www.di.univaq.it/rossi/networkdesign.html

Course page updates

This course page is available (with possible updates) also for the following academic years:

To read the current information on this course, if it is still available, go to the university course catalogue .

Course information last updated on: 10 settembre 2015, 10:40