# 91717 - Algorithms for Combinatorial Optimization Problems M

### Course Unit Page

• Teacher Enrico Malaguti

• Learning modules Enrico Malaguti (Modulo 1)
Michele Monaci (Modulo 2)

• Credits 6

• SSD MAT/09

• Teaching Mode Traditional lectures (Modulo 1)

• Language English

• Campus of Bologna

• Degree Programme Second cycle degree programme (LM) in Computer Engineering (cod. 5826)

• Course Timetable from Sep 19, 2022 to Oct 25, 2022

Course Timetable from Nov 07, 2022 to Dec 20, 2022

### SDGs

This teaching activity contributes to the achievement of the Sustainable Development Goals of the UN 2030 Agenda.

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

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.

Lecture notes

## Office hours

See the website of Enrico Malaguti

See the website of Michele Monaci