• 091886 - GRAPH OPTIMIZATION

The course deals with some important network and graph optimization problems arising in several fields of application such as telecommunication, transportation and logistics. The course presents the optimization models for the different classes of problems and describes the main methods that have been proposed to tackle them.

Introduction. Brief review of mathematical programming models for graph and network optimization problems (paths, trees, minimum cost flow, maximum flow, travelling salesman problem, knapsack problem). Brief review of the Branch-and-Bound method and basic Cutting Plane method (Gomory cuts). 

Assignment and transportation problems. Models and algorithms for arborescence, assignment problems, matching problems, transportation problems.

Flow routing and Fixed Charge Network Design problems. Classification: splittable vs unsplittable flow, single vs multiple paths, multicommodity flows, node and arc fixed costs. Connectivity. Arc-based and path-based ILP models.

Column generation method. Dual problem and complementary conditions, pricing problem. Basic idea of Branch-and-price method.

Heuristic methods.  Greedy algorithm.  Local Search. Metaheuristics: tabu search, simulated annealing, variable neighborhood search. Very large scale neighborhood and ILP based neighborhood. Examples of application of heuristic methods.

Location problems. Classification: set covering and set partitioning, p-center and p-median problems, uncapacitated and capacitated facility location problems, single source and multiple source; location and flows: hub location. Comparison of different formulations. Valid inequalities for location problems (cover inequalities). Valid inequalities for network design and connectivity requirements. Basic idea of Branch-and-cut method. 

Lagrangian relaxation. General framework and its application to facility location problems. Application of Lagrangian relaxation to network design problems.

Scheduling problems. Introduction to scheduling problems. Classification: single machine scheduling with different objective functions (total weighted completion time, makespan, lateness, tardiness), parallel machines scheduling problems, flow shop, job shop. Models and algorithms for scheduling problems.

The aim of the course is to provide students with a classification of optimization problems related to networks and other applications. Further, the course aims at providing the students with the knowledge of a wide range of optimization methods. The students will learn to model optimization problems arising in real life applications, to represent them as particular case of well known optimization problems, and to deal with them applying both exact and heuristic approaches. Beside theoretical knowledge, the course will provide practical experience in developing and applying the optimization techniques. During lab sessions, the students will be asked to apply their knowledge to deal with problems.

The exam is a written test. Homeworks will be proposed on the practical part (lab).