The course aims at covering main exact and heuristic methods for key combinatorial optimization problems. Analyzed techniques include problem-specific methods and general approaches.
Introduction to Combinatorial Optimization. Polynomial network flow
problems. Node and Arc Routing Problems. Exact algorithms (Branch-and-Bound, Cutting Planes, Branch-and-Cut). Heuristic and meta-heuristic algorithms (Tabu Search, Variable Neighborhood Search, Adaptive Large Neighborhood Search, Kernel Search). Application of studied solution methods to node routing and arc routing problems. Approximation algorithms and worst case analysis. Introduction to Bilevel Optimization.
1.Introduction to combinatorial optimization (CO) problems.
Definition of combinatorial problem. Models, properties and applications of the OC problems. Alternative formulations for OC problems. Strong formulations and linear relaxation. Examples of alternative
formulations for the Minimum Spanning Tree and the Perfect Matching Problem.
2. Polynomial network flows problems.
Network flows: basic definitions. Total Unimodularity. Max Flow Problem: model and properties. Theorem of max-flow min-cut. Ford-Fulkerson's algorithm. Applications. Minimum cost flow problem: properties.
3. Introduction to Arc and Node Routing Problem. Properties and differences. Necessary and sufficient condition for unicursality. Chinese Postman Problem and its computational complexity. Rural Postman Problem. Computational complexity and special cases. Solution algorithms.
4. Heuristic and meta-heuristic algorithms.
Constructive algorithms and Improvement algorithms. Local Search methods. 2-opt and 3-opt algorithms. Greedy algorithms. Meta-heuristic methods: Tabu Search, Variable Neighborhood Search, Adaptive Large Neighborhood Search and Kernel Search. Main properties of the methods. Application of the methods to node routing and arc routing problems.
5. Exact Algorithms. Polyhedral theory and algorithms. Branch-and-Bound method: properties and drawbacks. Valid inequalities and separation algorithm. Cutting Planes's algorithm. Gomory's cut and Dantzig's cut. General purpose cuts and specific cuts: examples. Classes of valid inequalites and exact and heuristic separation algorithms. Application of the method to the Traveling Salesman Problem and to an Index Selection Problem.
6. Approximation algorithms.
Properties and main features of the approximation algorithms. Worst case analysis. The tree Algorithm for the Traveling Salesman Problem. A greedy algorithm for the maximum independent set problem. Next Fit algorithm for the bin packing problem. Continuous relaxation based
algorithm for the vertex cover problem. greedy algorithms for the 0-1 knapsack problem.
7. Bilevel Optimization.Problem definition and properties. Problem classes. Solution methodologies.
D. BERTSIMAS, J.N. TSITSIKLIS, Introduction to Linear Optimization, Athena Scientific, Belmont, Massachusetts 1997.
G. AUSIELLO, P. CRESCENZI, G. GAMBOSI, V. KANN, A. MARCHETTISPACCAMELA, M. PROTASI, Complexity and Approximation, Springer
Verlag 1999.
C.PAPADIMITRIOU, K.STEIGLITZ, Combinatorial Optimization, Prentice
Hall, 1982.
M. GAREY, D. JOHNSON, Computers and Intractability: a Guide to the
Theory of NP-Completeness, Freeman, 1979.
Theoretical lectures and exercises.
Discussion and solution of real case problems and scientific articles. Handout of a project to be developed in groups encompassing students with different backgrounds. The activity aims at improving the use of acquired knowledge, in addition to communication and critical judgment skills.
Final exam consists in a written examination and in an oral one mainly consisting in the discussion of the results obtained in the project assigned at the beginning of the course. Each group will be also assigned a scientific paper related to optimization models and algorithms that students will analyze and present in class. Class discussion of the main difficulties encountered by the groups is also scheduled. Each student is required to take a short presentation
of the activity carried out in the group with the purpose of verifying his/her autonomy of judgment and learning skills.
All slides of the course encompassing theoretical lessons and exercises for self-study are available on the E-learning site (ESSE3).