Programme of Course "Network design"
The course is composed by the following modules: "Network Flows" "Network Optimization"
Code:
Type of course unit:
Master Degree in Computer Science curriculum UBIDIS: Compulsory
Master Degree in Mathematical Engineering curriculum Comune: Elective
Level of course unit:
Semester:
Module Network Optimization: 2° semester
Number of credits:
Teachers:
1. Course Objectives
Module Network Flows: Ability to recognize and formulate network flow problems
Knowledge of basic and advanced network flow algorithms
Ability to design resolution approaches to solve non standard network flow problems
Module Network Optimization: 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.
2. Course Contents and learning outcomes (Dublin Descriptors)
Topics of the course include:
Module Network Flows
 Network Flows Problem: introduction and definitions
 Maximum Flows and the path packing problem. Flows and cuts: MaxFlow/MinCut theorem. Augmenting path algorithms: Ford and Fulkerson algorithm, Edmonds and Karp algorithm. Generic PreflowPush algorithm. Flows with lower bounds.
 Maximum Flows: additional topics and applications. Flows in Unit Capacity Networks. Flows in Bipartite Networks. Network Connectivity.
 Minimum Cuts. Global Minimum Cuts. Node Identification Algorithm. Random Contraction. Applications.
 MinimumCost Flow Problems. Definition and applications. Optimality Conditions. The FordBellman algorithm for the shortest path problem. Primal algorithms: Augmenting Circuit Algorithm for the Min Cost Flow Problem.
 Network Simplex Algorithms. Applications of Min Cost Flows.
Module Network Optimization
 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 branchandbound 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. Branchandcut 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.
On successful completion of this course, the student should
Module Network Flows
 Know and formulate network flow problems
 Model decision problems as network flow problems Use base and advanced algorithms to solve network flow problems
 Ability to identify network flow models scope
 Ability to explain network flows models and algorithms
 Ability to learn stateofart algorithms for network flow problems
Module Network Optimization

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 stateofart algorithms for network optimization problems
3. Course Prerequisites
Module Network Flows: Basic knowledge of:
Discrete Mathematics, Linear Programming, Algorithms and Data Structures, Computational complexity
Module Network Optimization: Basic knowledge of:
Discrete Mathematics, Linear Programming, Algorithms and Data Structures, Computational complexity.
Knowledge of at least one programming language.
4. Teaching methods and language
Module Network Flows: Lectures
Module Network Optimization: Lectures and software training
Language:English
Reference textbooks
Module Network Flows
 Cunningham, Pulleyblank, Schrijver , Combinatorial Optimization.
 Ahuja, Magnanti, Orlin, Network Flows.
Module Network Optimization
 L.A. Wolsey, Integer Programming. Wiley. 1998.
5. Assessment Methods
Module Network Flows: Written text exam
Module Network Optimization: Written text exam and assignment
Course information last updated on: 10 settembre 2015, 10:50