Network Design 20152016
Network Design (Progetto di Reti) is a 12 CFU integrated course made of two modules: Network Flows (formerly Progetto e Ottimizzazione di Reti) and Network Optimization (formerly Ottimizzazione Combinatoria 2)
Schedule
Network Flows
 Tuesday 14.0016.00 Room A.1.2 (Alan Turing Building)
 Thursday 11.0013.00 Room A.1.3 (Alan Turing Building)
Network Optimization
 Tuesday 11.0013.00 Room A.1.3 (Alan Turing Building)
 Wednesday 9.0013.00 Room A.1.3 (Alan Turing Building)
Office Hours
Wednesday 11:00  13:00
From February, 23thCourse Contents
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.
 Heuristics for network problems: local search, tabu search, simulated annealing, MIP based heuristics.
Textbooks
Reference books
 L.A. Wolsey, Integer Programming, Wiley, 1998.
 Cook, Cunningham, Pulleyblank, Schrijver , Combinatorial Optimization, Wiley,1998.
 Ahuja, Magnanti, Orlin, Network Flows, Prentice Hall, 1993.
Further readings
Slides and Notebooks
Slides are in Italian. English slides and Network Optimization slides are available on request
Notebooks
Software
 A recent Linux distribution (all of the notebooks have been tested in Xubuntu 14.04.4)
 Jupyter Notebook
 NetworkX
 GLPK (GNU Linear Programming Kit)
 puLP: An LP modeler in Python
Setting up the working environment
After a fresh install of Xubuntu 14.04.4, you can setup the working environment by installing the following packages:

sudo aptget install pythonpip
pip upgrade
sudo H pip install pip U
Python development libraries
sudo aptget install pythondev

sudo H pip install jupyter

sudo H pip install networkx
GLPK: GNU Linear Programming Kit
sudo aptget install glpkutils

sudo H pip install pulp

sudo aptget install pythonpygraphviz

sudo pip install tabulate