78780 - Optimization Algorithms 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. Study of the ILP Solver CPLEX for the solution of Linear Programming and Mixed Integer Linear Programming models.

4. Exact algorithms for the solution of NP_Hard problems. "Branch-and-Bound" algorithms: decision trees, relaxation techniques, improvement of the relaxed problems, subgradient optimization technique, dominance criteria, "core problem" technique. Exact algorithms for the effective solution of the Knapsack Problems, the Asymmetric Travelling Salesman Problem, and the Set Covering Problem.

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

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

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

Basic knowledges 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.

C. Barnhart, G. Laporte (editors), Transportation, Handbooks in Operations Research and Management Science, North Holland, 2007.

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.

Computer Laboratory.

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. Utilization of the package CPLEX (optional).

Teaching tools

Slides given to the students during the lessons, and available on the web site of the Course.

Office hours

See the website of Paolo Toth