Portale di Ateneo - En.Unibs.it

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. Basics of computational complexity theory. Algorithms classification: exact, heuristic, approximation algorithms.

3. 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, solution algorithms and applications. Minimum cost path problems: properties,
solution algorithms and applications.

4. Introduction to Arc Routing Problem. Properties. Chinese Postman Problem and its computational complexity. Rural Postman Problem. Computational complexity and special cases. Solution algorithms.

5. 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.

6. 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.

7. 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. Continuos relaxation based
algorithm for the vertex cover problem. greedy algorithms for the 0-1 knapsack problem.