# METHODS AND MODELS FOR DECISIONS

## Learning outcomes of the course unit

This course is aimed at providing students with the basic techniques and

algorithms of integer programming and combinatorial optimization as

applied to some relevant problems in industrial and operations

engineering. In this course, students will learn how to formulate and

solve integer and combinatorial optimization problems. Students will also

study approaches to interpretation and analysis of solutions.

## Prerequisites

Linear Programming

## Course contents summary

The goal of this course is to introduce optimization problems that fall

within the framework of Integer Programming and Combinatorial

Optimization, and give an overview of classical methods for their analysis

and solution. The major topics are: Network optimization and graph

search. Integer programming (IP) formulations: formulation techniques,

quality of formulations. Well-solved IP problems and total unimodularity.

Relaxations and bounds: Lagrangian relaxation, duality. Some exact and

heuristic solution techniques: Branch-and-Bound, cutting planes, column

generation, local search, etc., depending on time constraints.

Applications and problems discussed in the course include: plant and

facility location models; transportation problems; distribution problems;

the Vehicle Routing problem; the Travelling Salesman Problem;

scheduling problems; input-output models.

## Course contents

1. Elements of Integer Programming and Combinatorial Optimization.

Review on Linear Programming. Integer Linear Programming: formulation

techniques for integer programming problems. Exact algorithms for the

solution of integer programming and combinatorial problems: cutting

plane methods; branch and bound; dynamic programming. Lower and

upper bounds for the optimum: Lagrangian relaxation and Lagrangian

duality. Heuristic methods: greedy techniques, local search techniques,

improvement heuristics, savings algorithm. 2. Applications. Location

problems: plant and facility location models. Distribution problems:

transportation problems; distribution problems; the Vehicle Routing

problem; the Travelling Salesman Problem. Scheduling problems.

## Recommended readings

- L. A. Wolsey, Integer Programming, Wiley-Interscience, New York, 1998.

- F. Maffioli, Elementi di programmazione matematica, seconda edizione, Casa Editrice Ambrosiana, Milano, 2000.

- Ghiani G., Musmanno R., Modelli e metodi per l’organizzazione dei sistemi logistici, Pitagora Editrice, Bologna, 2000.

- F. S. Hillier, G. J. Lieberman, Introduzione alla ricerca operativa, Ottava edizione, McGraw-Hill, Milano, 2006.

## Teaching methods

The theoretical topics of the course are presented during class lectures

and illustrated with significant examples, applications and several

exercises. Homework assignments are proposed during the course, which

are then discussed in recitation sessions during class time.

## Assessment methods and criteria

The final exam consists of a written part, where students are required to

solve some exercises, and of an oral part about the theoretical topics and

the applications discussed during the course.