91717 - Algorithms for Combinatorial Optimization Problems M

Learning outcomes

At the end of the course, the students are able to analyze the computational complexity and to define the Mixed Integer Linear Programming (MILP) models of the Combinatorial Optimization problems. The students are able to obtain tight relaxations of the MILP models, and to design exact enumerative algorithms (based on the branch-and-bound, branch-and-cut and branch-and-price approaches) for determining the optimal solution of the Combinatorial Optimization problems. The students are also able to solve the MILP models by using the software package CPLEX.

Course contents

The main goals of the Course are the definition of the mathematical models and the design of the most effective exact algorithms for the solution of NP-Hard Combinatorial Optimization problems. The experimental evaluation of the proposed models and algorithms will be also analyzed.

The program of the Course consists of the following topics:

1. Classification of the optimization problems.

2. Definition of the Mathematical Models, and analysis of the computational complexity of important combinatorial optimization problems.

3. Exact algorithms for the solution of NP_Hard problems. "Branch-and-Bound" algorithms: decision trees, relaxation techniques. Exact algorithms for the effective solution of the Knapsack Problems, the Asymmetric Travelling Salesman Problem, and the Set Covering Problem.

4. "Branch-and-Cut" algorithms: addition of valid constraints for the strengthening of the relaxed problems, separation procedures for the solution of models with a large number of constraints. Exact algorithms for the effective solution of the Asymmetric Travelling Salesman Problem.

5. "Branch-and-Price" algorithms: column generation procedures for the solution of models with a large number of decisional variables. Exact algorithms for the effective solution of the Bin Packing Problem and of the Vertex Coloring Problem.

6. Experimental evaluation of the computational performance of the proposed models and algorithms.

Basic knowledge of Computer Science and Operations Research courses are required.

Readings/Bibliography

S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, J. Wiley, 1990.

G. Gutin, A. Punnen (editors), The Traveling Salesman Problem and Its Variations, Kluwer, 2002.

Wiley Encyclopedia in Operations Research and Management Science, Wiley, 2011.

P. Toth, D. Vigo (editors), Vehicle Routing: Problems, Methods and Applications, MOS-SIAM Series on Optimization, 2014.

Teaching methods

Lessons and Exercises.

Assessment methods

Written examinations concerning the definition of mathematical models, the analysis of the computational complexity, the definition of relaxed problems, and the design of exact algorithms for the solution of NP-Hard combinatorial optimization problems.

Teaching tools

Lecture notes

Office hours

See the website of Enrico Malaguti

See the website of Michele Monaci