Network optimization
- Unit Coordinator: Fabrizio Rossi
- ECTS Credits: 6
- Semester: 2
- Year: 1
- Campus: University of L'Aquila
- Language: English
- Aims:
- 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.
- 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 aune 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.
- Reading list:
L.A. Wolsey, Integer Programming. Wiley. 1998.
