Learning objectives
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 unit content
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.
Full programme
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.
Bibliography
- Course notes.
- 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.
Other information
- - -
2030 agenda goals for sustainable development
