Network Design 2018-2019

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)

Network Flows

• TbD

Network Optimization

• TbD

Tue 11:00-13:00, Thu 11:00 - 13:00

Module Network Flows

• Network Flows Problem: introduction and definitions
• Maximum Flows and the path packing problem. Flows and cuts: Max-Flow/Min-Cut theorem. Augmenting path algorithms: Ford and Fulkerson algorithm, Edmonds and Karp algorithm. Generic Preflow-Push 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.
• Minimum-Cost Flow Problems. Definition and applications. Optimality Conditions. The Ford-Bellman 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 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.
• Heuristics for network problems: local search, tabu search, simulated annealing, MIP based heuristics.

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

• Python Programming
• Google's Python Class

Slides are in Italian. English slides and Network Optimization slides are available on request

• Network Flows, Part 1
• Network Flows, Part 1, pdf format
• Network Flows, Part 2
• Network Flows, Part 2, pdf format

Notebooks

• Survey Design
• Matrix Rounding
• Airline Scheduling

• Jupyter Notebook
• NetworkX
• Gurobi Optimizer