Learning objectives
This course is aimed at providing students with the basic concepts, 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 relevant classes of integer and combinatorial optimization problems. Students will also study approaches to interpretation and analysis of solutions.
Prerequisites
Basic knowledge of 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
- L. A. Wolsey, Integer Programming, Wiley-Interscience,1998.
- 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
- - -
