Department of Computer Science
and Electronics,
Politecnico di
APPLICATIONS OF DISCRETE
OPTIMIZATION:
Routing problems and some
general ideas for approximation algorithms
Summer Semester 2006
(2.5 credits for Master, 5 credits
for PHD)
Lecturers: Luca Maria
Gambardella and Monaldo Mastrolilli
IDSIA, Istituto Dalle Molle di studi
sull’Intelligenza Artificiale,
www.idsia.ch/~luca, www.idsia.ch/~monaldo
Exam: Wednsday 28th June
Master students: 16:30 - 18:00, room D.0.1
PhD students: 14:30-18:30, room D.2.2
Aim and Scope
The course is
divided in two parts. The first part concerns with routing problems while the
second part is dedicated to approximation algorithms.
The first part,
lectured by Luca Maria Gambardella, is based on the consideration that many
practical distribution problems requires to find a set of routes minimising the number of traveled kilometers, the number of
used vehicles, the cost of the fleet while satisfying customer demand and
constraints. There are different stages and different models for these
distribution problems starting from the traditional traveling salesman problem,
moving to problems with precedence constraints and finally to vehicle routing
problems. There are three major considerations that are important when we try
to solve these problems. First of all, they are inherently combinatorial, and
exact algorithms fail when the dimension of the problem (number of customers
and orders) reaches a reasonable size. Secondly, the problem can be extended
and made more complex in many ways, for instance, adding more than one depot,
considering more than one vehicle type, accounting for stochastic customer
demand (the exact requested quantity is known only at delivery time),
considering time windows during which the customers must be served, taking into
account vehicle accessibility restrictions (some customers cannot be served by
some vehicles). Finally, the problem can become very different when we consider
on-line distribution, that is, we accept delivery orders for lorries
which are en route. There, geolocation of customers
and vehicles, online data transfer among lorries and
the base station, have an impact as great as the solution strategy. At the end
there are real industrial applications where all these constraints are present
in an operative environment and human planners use optimization software to
solve distribution problems.
The second part,
lectured by Monaldo Mastrolilli,
considers approximation algorithms for NP-hard optimization problems. An
r-approximation algorithm is a polynomial time algorithm that has been proven
to return a solution within r-times the optimal value. The job of a potential
algorithm designer, faced with a NP-hard problem, could certainly be simplified
if one could give a standard set of recipes for coming up with the algorithmic
idea. The focus of this part of the course is on methodology to design
approximation algorithms. In particular some fairly general techniques will be
presented: namely, we first present the Local
Ratio technique and then the main tools and the standard approaches for the
construction of Polynomial Time Approximation
Schemes.
Contents
The first part of the course resents solution techniques for traveling
salesman problems, sequential ordering problems and vehicle routing problems.
We present mathematical formulation, branch-and-bound and branch-and-cut
techniques associated to different approach to compute lower bound for these
problems, some based on the related assignment problem and other based on tree
relaxation. Next constructive methods like nearest neighbor, double ended,
multiple fragment, Christofides, Clarke-Wright, space
filling curve and composite methods (routing + clustering) are investigated and
explained. Next part is dedicated to deeply investigate meta
heuristics algorithms like simulated annealing, tabu
search, genetic algorithms, ant colony optimization in relation with local
search techniques such as 2opt, 3opt, Lin-Kernighan, sop-3-exchange, customers
relocation, crossover, customers exchange, path exchange. At the end we present
some industrial applications where these techniques have been successfully
applied to daily solve distribution problems.
The second part of the course introduces Local Ratio technique as
a methodology for the design and analysis of algorithms for a broad range of
optimization problems. The technique is remarkably simple and elegant, and yet
can be applied to several classical and fundamental problems (including
covering problems, packing problems, and scheduling problems). The local ratio
technique uses elementary math and requires combinatorial insight into the structure
and properties of the problem at hand. Many applications of these ideas are
provided during the course together with the analysis of the associated
approximation algorithms.
Polynomial Time Approximation
Schemes (PTAS) are approximation algorithms that return in polynomial time
solutions that can be arbitrarily close to the optimum. We present a tutorial
that provides an introduction into the area of PTAS. Several approaches are
explained in great detail and illustrated in many examples and exercises.
Some applications of the presented techniques:
References
Course Materials
Timetable
| Date | Time | Room | Lecturer |
| Tuesday, 14th March | 16:30 - 18:15 | D.2.6 | Gambardella |
| Wednesday, 15th March | 16:30 - 18:15 | D.2.1 | Gambardella |
| Tuesday, 21sh March | 16:30 - 18:15 | D.2.6 | Gambardella |
| Wednesday, 22nd March | 16:30 - 18:15 | D.2.1 | Gambardella |
| Tuesday, 28th March | 16:30 - 18:15 | D.2.6 | Gambardella |
| Wednesday, 29th March | 16:30 - 18:15 | D.2.1 | Gambardella |
| Tuesday, 4th April | 16:30 - 18:15 | D.2.6 | Mastrolilli |
| Wednesday, 5th April | 16:30 - 18:15 | D.2.1 | Mastrolilli |
| Tuesday, 11th April | 16:30 - 18:15 | D.2.6 | Mastrolilli |
| Wednesday, 12th April | 16:30 - 18:15 | D.2.1 | Mastrolilli |
| Wednesday, 19th April | 16:30 - 18:15 | D.2.1 | Mastrolilli |
Lecturers
Luca Maria Gambardella is Director at IDSIA, Istituto Dalle Molle di
Studi sull’Intelligenza Artificiale, Lugano, Professor of Algorithms at SUPSI,
lecturer of Application of Discrete Optimization at Milan Polytechnics and
lecturer of the Artificial Intelligence module in the Knowledge Management
course at Informatics Faculty at the University of Lugano. IDSIA is a research
institute of both SUPSI (University of Applied Science of Southern Switzerland,
Department of Technology and Innovation) and USI (University of Lugano).
His experience and his background cover different aspects, from management to
research, including the preparation and the negotiation of many research
projects, the direction of a research institute, the involvement in AntOptima
the spin-off company of IDSIA other than the realization of successful and
effective algorithms:
His current research interest and his major publications include Ant Colony
Optimization and meta-heuristics for global optimization, learning and planning
for complex collective systems, simulation and scheduling for logistic and
routing problems. He has invented several meta-heuristics algorithms that can be
applied to a wide class of combinatorial optimization problems. In some of these
domains, such as the quadratic assignment [Gambardella, Taillard, Dorigo,1999],
the sequential ordering [Gambardella & Dorigo 2000], the vehicle routing with
time window [Gambardella, Taillard, Agazzi 1999] and the flexible job shop
scheduling problems [Mastrolilli & Gambardella 2000] these approximation
algorithms are among the best currently worldwide available and for many
benchmark instances new best known solutions have been computed.
Monaldo Mastrolilli is a senior researcher at IDSIA and lecturer of
Operations Research at SUPSI. In 1997 he graduated with honours in Computer
Science Engineering at Politecnico di Milano (Italy), and won the Third prize of
the general category in the Whizzkids'97 competition on combinatorial
optimization, designed by the Technical University of Eindhoven. He joined IDSIA
as a PhD student in 1998. In 2002 he received a summa cum laude Ph.D. degree in
Computer Science at University of Kiel (Germany). Since 2004 he holds a
permanent position as senior researcher at IDSIA. His main scientific interest
is in approximation algorithms for NP-hard problems. He is the author of more
than 30 papers published in leading international scientific journals (like
Journal of Algorithms, Discrete Applied Mathematics, European Journal of
Operational Research, etc…) and conferences (like ESA, AAAI, LATIN, ISAAC, SWAT,
etc…). He is the Head of Optimization Department of AntOptima for which he
supervised and worked on several industrial projects.