Pisa - Dipartimento di Informatica - Research Evaluation Exercise 1999
The research project contains several different modules, each
characterized by the application area and the type of methodology
involved. The following table illustrates the relations among the
different application and methodology sectors.
Although to fully understand the motivation and rationale of the
different researches one has to start from the application areas, in
the following, for the sake of the clarity and of the conciseness, we
shall use the methodologies as a guidance criterion for the group's
Network models and algorithms have played a fundamental role in the
development of Operations Research and Management Science since the
initial times of these disciplines. Network optimization lies in the
middle of the great divide which separates the two major types of
optimization problems, continuous and discrete, and has benefitted
from the advancements in both areas, while, at the same time, it has
largely contributed to such advances.
Network problems such as shortest paths, assignment,
transportation, transhipment, spanning trees,
salesman, generalized assignment, vehicle routing and
flows constitute the most common classes of practical optimization
problems in the area. In spite of the large body of research done in
the past, there is still a huge amount of research going on in the
quest of always faster algorithms capable of tackling the growing size
and the complexity of real life applications. This fact is proved by
the large number of articles on network optimization which appear
every month in leading scientific journals such as Mathematical
Programming, Networks, Informs Journal on Computing and
Operations Research. To get an idea of the state of the art in
this sector one can refer to some recent books and special journal
issues such as ,  and .
Many problems can be found in different application areas, which,
although featuring an underlying graph structure, cannot be
represented as graph problems without losing some of their peculiar
characteristics. This fact has led recently to the introduction of a
generalization of graphs, the directed hypergraphs, which include as
particular cases other well known generalizations such as labelled
graphs and And-Or graphs. Directed hypergraphs are a powerful tool
not only in modelling but also in solving several relevant problems in
areas such as linear production problems, flexible manufacturing
systems, propositional logic, relational databases, and public
transportation systems [42,21,26].
Minimizing a convex function which does not possess continuous
derivatives is a rather difficult task which is required in many
One traditional approach is the subgradient method. Of quite simple
implementation, it suffers from a number of important drawbacks, among
which the inability of providing a primal optimal solution together
with the dual optimal solution, and its slow convergence rate.
The other fundamental class of algorithms for nondifferentiable
optimization stems from the cutting plane method, and it is
based on the idea of constructing a model of the function, to be
progressively refined as the algorithm proceeds, which at each step is
used to determine the new point(s) in which to evaluate the function.
More efficient than the standard subgradient method, this approach is
at present widely investigated. Examples of algorithms of this type
can be found in .
Combinatorial optimization is concerned with optimal decisions in
the case of discrete alternatives. In the last two decades, an
enormous effort has been made to model real-life problems and to
solve them through Combinatorial Optimization.
Almost all the practically relevant combinatorial
optimization problems belong to the class of the difficult (NP-hard)
problems, which, in addition to the large size of real life
applications, makes their exact solution usually rather unpractical.
That explains the huge number of papers and books dealing with
Local search is the main algorithmic paradigm underlying the heuristic
approaches to solve combinatorial optimization problems. In a local
search method one moves from the current solution to a neighboring
one, trying to improve the objective function, until a ``good'' local
optimal solution is found.
Lying in the interface between mathematics, computer science and
operations research, the research on local search has originated a
large body of literature. Methods such as ``Simulated annealing'',
``Tabu search'', ``Genetic algorithms'', which belong to this class,
are currently used to solve optimization problems arising in a large
variety of applications [41,39,38,35,37].
A traditional research
subject for the
group , the activity in this area, in the last years, has
focused on ``auction'' and ``dual-ascent'' methods. A new auction
algorithm running in strongly polynomial time has been introduced,
whose practical efficiency has been extensively tested; parallel
implementations are currently being studied . A new
family of dual-ascent methods, called Hanging algorithms, has been
proposed . More recently, the interest has been drawn on
dynamic networks, i.e. networks where the distances are
functions of the time; the search of shortest paths on these networks
is particularly relevant in transportation planning .
Efficient serial and
to solve large scale minimum cost multicommodity flow problems
have been studied and have served as a test bed for the developement
of general codes for nondifferentiable optimization [15,4]. This research has been motivated by a certain number of
relevant application: transportation and routing problems
, timetabling in freight transportation,
crew scheduling  and network design
Other particular flow problems have been studied, among them the
balanced flow problem, i.e. a problem where an
``equitable distribution'' of the flow is wanted .
The research developed in this area has been aimed both to the
sistematic analysis of the hypergraph theoretic properties and to
particular classes of hypergraph optimization problems [21,26].
A Simplex-like algorithm for the capacitated minimum cost
hyperflow problem, based on the characterization of the basis
structures in terms of spanning hypertrees, has been proposed and
widely tested [3,20].
The analysis of the demand in transit systems has been one of the
first applications to motivate the research on directed hypergraphs:
in fact, the passengers' behaviour in a transit network can be better
modelled making use of hyperpaths in directed hypergraphs rather than
using paths in standard graphs. Furthermore, the use of directed
hypergraph to model the transit network has proven crucial in
extending to the public transportation setting the equilibrium models
developed for the analysis of private transportation [29,30].
Another important application, which actually has contributed to
originate the research on directed hypergraphs, is the ``satisfiability
problem''. A satisfiability problem can be formulated as the problem
of finding a hyperpath between two nodes in a directed hypergraph
[5,24], while the problem of finding the minimum number of
clauses to be deleted in order to make a formula satisfiable can be
formulated as the problem of finding a minimum cutset in a directed
Other interesting applications on which some research has been done is
that of production systems. Namely both the cutting stock problem
 and the problem of finding, in a manufacturing system, an
assemblying plan which allow the production of a given item at minimum
`cost' , can be formulated and solved by means of
Motivated by some applications involving multicommodity flow problems,
the research work in this area has started with the implementation of
a generic code for (constrained) nondifferential optimization, based
on the ``traditional'' penalty Bundle approach . This
solver has already been successfully used in different applications,
among which we mention: sequential  and parallel
 cost-decomposition approaches for multicommodity flow
problems, computation of lower bounds for the capacitated
fixed-charge multicommodity flow problem [9,10],
Lagrangean heuristic approaches to crew scheduling problems  and computation of lower bounds for the capacitated minimum
spanning tree problem .
A methodological contribution of this research has been the
introduction of a class of generalized Bundle methods that subsumes
several known Bundle variants .
A relevant research sector is the one concerned with the heuristic
solution of hard combinatorial optimization and decision problems. In
particular, expertise and skills in obtaining both theoretical and
algorithmic results, and solving real life applications, have been
developed by the group in the following areas: crew scheduling
problems ; vehicle scheduling and transportation problems
[8,31,28]; logistics and distribution problems
; scheduling and sequencing of activities on machines
; cutting stock and assembly problems [27,25].
In most of the above mentioned problems the outline of the approach
followed can be described as follows: 1) analyse the problem structure
and find a good formulation; 2) relax the problem or decompose it in
easier subproblem; 3) solve the relaxation (nondifferentiable
optimization methods find application here); 4) use the
solution of the relaxation as a starting point for some heuristic
algorithm (local search methods are typical tools in this phase).
The research on
shortest paths shall
continue, focusing on special classes of problems, motivated by
applications in the area of transportation management: constrained
shortest paths and shortest paths with time windows.
Constrained shortest paths arise in the column generation
approach to crew scheduling problems. We have just started the
re-engineering of a package for crew scheduling, based on relaxation
and column generation, which is currently used in several Italian
public transportation companies, and which has been originated with
past research activity of the group. The goal is to improve its
effectiveness, making it able to get better solutions at a lower
computational cost. To obtain these results, the research will be
focused on the column generation procedure and henceforth on the
design of fast constrained shortest path algorithms. Being the
constrained problems we are dealing with of the NP-hard type,
heuristic algorithms will be studied.
Shortest paths with time windows play a fundamental role in
algorithms for ``weak demand'' transportation systems, such as
``dial-a-ride'' systems. Again, this is a difficult problem, and
heuristic techniques will be used for its solution.
which is now being
carried on concerns the management of the vehicle depots in a medium
size Italian public transportation company. A mathematical
programming model has been formulated which contains as a subproblem a
``generalized assignment'' problem. Algorithms for this problem shall
The rostering problem, that is
the problem of assigning a given set of duties to the personnel within
a given planning horizon, can be formulated as path covering problem
on a multilayered graph. This is a typical problem which appears to
be well suitable for the``multiexchange'' heuristic algorithms
described in the next ``Heuristics'' section, and will be studied in
We plan to analyze the use of hypergraph models and algorithms for
special classes of minimum makespan assemblying problems. That
implies the implementation of the heuristic algorithm mentioned in
the previous section and its use on test problems with different types
We plan to enhance our Bundle code using the ideas developed in
. In particular, we will experiment with different
alternatives to the standard quadratic stabilizing term, namely with
those resulting in linear programming subproblems. We expect
considerable performance's improvements, that should make it possible
to approach very-large-scale nondifferentiable optimization problems.
We plan to use the enhanced Bundle code to improve upon the results
previously obtained, and to develop new Lagrangean-based approaches
for several new problems.
In many different classes of combinatorial optimization problems
arising in practical applications, a feasible solution can be
characterized as a partition of a set of objects into a set of
subsets, such that for each subset a certain class of properties hold.
In many cases, the optimal solution is such that the structural
relations among the elements within a single subset result from a
nested optimisation problem.
Among the application areas for which this structure holds, we
mention: 1) scheduling problems on parallel machines; 2)
service center location and dimensioning; 3) delivery
problems; 4) routing problems; 5) transportation
problems; 6) vehicle and crew scheduling problems.
For this class of problems, the quality of a solution varies depending
on the specific partition as well as on the possibility of efficiently
optimising within the single subset belonging to the partition.
The aim of the research is to investigate and develop
``multiexchange'' local search methods which exploit the particular
structure of the solutions mentioned above. The main idea is to map
the set of feasible exchanges of a given partition on a graph, the
``exchange graph'' hereafter. The nodes of the exchange graph
represent the subsets of the partition while the arcs model possible
exchanges of elements within pairs of subsets, with the arc cost being
an estimate of the variation of the objective function due to that
particular exchange. Then, to find a better neighboring solution we
look for a cycle or path of minimum cost (possibly negative cost) on
the exchange graph. In view of that, in the short term, we shall
focus on the development of efficient algorithms for the detection of
negative paths and cycles on graph will be an useful instrument.
Different optimization problems on dynamic networks will be studied.
This research is motivated by the activity on transportation planning.
The design of fast minimum cost multicommodity flow algorithms will
mantain its interest and relevance in the future, mainly in view of
applications to the design and analysis of mass transportation
A global approach to find an assemblying plan which minimizes some
given criterion will be investigated. It shall be based on hypergraph
models and on decomposition techniques; from the algorithmic point of
view it will rely on the know-how that the group has gained in the
research on nondifferential optimization.
We envisage the development of Bundle method variants that are still
not subsumed by our current theoretical framework, as well as the
extension of our approach to more general problems such as
variational inequality problems.
The long term goals are to develop an algorithmic paradigm based on
the ``multiexchange'' approach, and to study its applicability to a
large set of combinatorial problems of practical interest.
To do that, we intend first to analyse the classes of problems which share
the structural property described above; in particular, we plan to
investigate vehicle scheduling problems and scheduling problems on
parallel machines. Then, the ``multiexchange'' algorithmic paradigm
will be specialized to solve the studied problems.
Born in Palermo, July 27, 1942. `Laurea' in Electronic Engineering,
University of Palermo, 1967. Current position: Professor of
Operations Research. Teaching: Operations Research,
Combinatorial Optimization, Networks, Simulation. Research
interests: Network optimization, Combinatorial optimization,
Transportation models, Satisfiability, Scheduling. Most
relevant papers: , ,,
Born in Rome, September 26, 1945. `Laurea' in Mathematics, University
of Rome, 1969. Current position: Professor of Operations
Research. Teaching: Operations Research, Combinatorial
Optimization, Networks. Research interests: Network
optimization, Combinatorial optimization, Transportation models,
Directed hypergraphs. Most relevant papers: ,
,, , .
Born in Sesto ed Uniti (CR), December 23, 1961. `Laurea' in Computer
Science, University of Pisa, 1985. Ph.D. in Computer Science,
University of Pisa, 1990. Current position: Associate
Professor of Operations Research. Teaching: Operations
Research, Combinatorial Optimization, Networks. Research
interests: Networks and Flows, Directed hypergraphs and hyperflows,
Heuristics. Most relevant papers: , ,
, , .
Born in Portoferraio (LI), Italy, April 2, 1968. `Laurea' in Computer
Science, University of Pisa, 1992. Ph.D. in Computer Science,
University of Pisa, 1996. Current position: Research
Associate. Teaching: Mathematical Programming, Combinatorial
Optimization. Research interests: NonDifferentiable
Optimization, Multicommodity Flows, Combinatorial Optimization.
Most relevant papers: , ,,
Born in Oratino (CB), Italy, May 30, 1968. `Laurea' in Computer
Science, University of Pisa, 1993. Ph.D. in Applied Mathematics,
University of Florence, 1998. Current position: Post-doc.
Research interests: Combinatorial Optimization. Multicriteria
Decison-aid. Data Envelopment Analysis. Heuristics.
Most relevant papers: .
Ravindra K. Ahuja, Theodor G. Crainic, Federico Malucelli, Maddalena
Nonato, Sang Nguyen, Daniele Pretolani, Andres Weintraub.
Network optimization, Network flows, Dircted hypergraphs,
NonDifferentiable optimization, Heuristics, Transportation models,
Crew scheduling, Production systems
- Bertsekas D.P., S. Pallottino and M.G. Scutellà,
``Polynomial Auction algorithms for shortest paths'',
Computational Optimization and Applications 4(2), 99-125, 1995
- Simeone B., P.Toth, G.Gallo, F.Maffioli and
S.Pallottino editors, ``Fortran codes for network optimization'', Annals
of Operations Research 13, 1988
- Cambini R., G. Gallo and M.G. Scutellà, ``Flows on
hypergraphs'', Mathematical Programming 78, 195-217, 1997
- Cappanera P. and A. Frangioni, ``Symmetric and Asymmetric
Parallelization of a Cost-Decomposition Algorithm for Multi-Commodity Flow
Problems'', TR 36/96, Dip. di Informatica, Univ. di Pisa (submitted
to INFORMS J.on Computing), 1996
- Carraresi P., G. Gallo and G. Rago: ``A hypergraph model
for constraint logic programming and applications to bus drivers'
scheduling'' Annals on Mathematics and Artificial Intelligence 8,
- Carraresi P., F. Farinaccio and F. Malucelli:
``Testing Optimality for Quadratic 0-1 Problems'', TR 11/95,
Dip. di Informatica, Univ. di Pisa (to appear on
Mathematical Programming), 1999
- Carraresi P., A. Frangioni and M. Nonato ``Applying Bundle
Methods to Optimization of Polyhedral Functions: An Applications-Oriented
Development'' Ricerca Operativa 74, 5-49, 1996
- Carraresi P., F. Malucelli and S. Pallottino ``Regional mass
transit assignment with resource constraints'' Transportation Research B
30, 81-98, 1996
- Crainic T.G., A. Frangioni and B. Gendron ``Bundle-based
Relaxation Methods for Multicommodity Capacitated Fixed Charge Network
Design Problems'' to appear on Discrete Applied Mathematics, 1999
- Crainic T.G., A. Frangioni and B. Gendron
``Multicommodity Capacitated Network Design'' to appear in (B. Sanso and
P. Soriano, eds.) Telecommunications Network Planning,
Kluwer Academics Publishers, 1999
- Equi L., G. Gallo, S. Marziale and A. Weintraub ``A combined
transportation and scheduling problem'', European Journal of
Operational Research 97, 94-104, 1997
- Frangioni A. ``Solving Semidefinite Quadratic Problems
Within Nonsmooth Optimization Algorithms'' Computers & O.R.
23, 1099-1118, 1996
- Frangioni, A., ``On a New Class of Bilevel Programming
Problems and its Use For Reformulating Mixed Integer Problems'',
EJOR 82, p. 615 - 646, 1995
- Frangioni A. ``Generalized Bundle Methods'' TR
04/98, Dip. di Informatica, Univ. di Pisa (submitted to SIAM
J. on Optimization), 1998
- Frangioni A. and G. Gallo ``A Bundle type Dual-ascent
Approach to Linear Multicommodity Min Cost Flow Problems'' to appear in
INFORMS JOC, 1999
- Frangioni A., D. Pretolani and M.G. Scutellà ``Fast Lower
Bounds for the Capacitated Minimum Spanning Tree Problem'' TR 05/99,
Dip. di Informatica, Univ. di Pisa (submitted to Networks), 1999
- Gallo G., C. Gentile, D. Pretolani and G. Rago ``Max
Horn Sat and the Minimum Cut Problem on Directed Hypergraphs''
Mathematical Programming 80, 213-237, 1998
- Gallo G. and M. D. Grigoriadis, eds. ``Netwok Optimization:
Algorithms and Applications'' Mathematical Programming B 78, 1997
- Gallo G., M.D. Grigoriadis and R.E. Tarjan, ``A fast
parametric maximum flow algorithm'' SIAM Journal on Computing 9,
- Gallo G., F. Licheri and M.G. Scutellà ``The
Hypergraph Simplex Approach: some experimental results'' Ricerca
Operativa 78, 21-54, 1996
- Gallo G., G. Longo, S. Nguyen and S. Pallottino ``Directed
hypergraphs and applications'' Discrete Applied Mathematics 42,
- Gallo G. and S. Pallottino ``Shortest path methods: a
unifying approach'' Mathematical Programming Study 26, 38-64,
- Gallo G. and F. Piccinonno ``A 1/4 approximate algorithm for
P2/tree/Cmax'' Discrete Applied Mathematics 72, 85-98, 1997
- Gallo G. and D. Pretolani ``A new algorithm for the
propositional satisfiability problem'' Discrete Applied Mathematics
60, 159-179, 1995
- Gallo,G. and M.G. Scutellà ``Minimum Makespan
Assembly Problems'' TR 10/98, Dip. di Informatica, Univ. di Pisa, 1998
- Gallo G. and M.G. Scutellà ``Directed Hypergraphs as a
Modelling Paradigm'' to appear in Rivista AMASES, 1999
- Gambale M., M. Nonato and M.G. Scutellà ``The
Cutting Stock Problem: a new model based on hypergraph flows''
Ricerca Operativa 74, 73-97, 1995
- Malucelli F., M. Nonato and S. Pallottino ``Demand Adaptive
proposals on flexible transit'' to appear in (T.A. Ciriani, S. Gliozzi, E.L.
Johnson and R. Tadei, eds.), Operations Research in Industry, McMillan
Press, London, 1999
- Nguyen, S. and S. Pallottino, ``Equilibrium traffic
assignment for large scale transit networks'', European Journal of
Operational Research 37, 176-186, 1998
- Nguyen S., S. Pallottino and M. Gendreau ``Implicit
enumeration of hyperpaths in logit models for transit networks'',
Transportation Science 32, 54-64, 1998
- Nguyen S., S. Pallottino and F. Malucelli ``A modeling
framework for the passenger assignment on a transport network with
time-tables'' TR 13/98, Dip. di Informatica, Univ. di Pisa, 1998
(submitted to Transportation Science)
- Pallottino S. and M.G. Scutellà ``Dual algorithms for
the shortest path tree problem'' Networks 29, 125-133, 1997
- Pallottino S. and M.G. Scutellà ``Shortest path
transportation models: classical and innovative aspects'' in (P. Marcotte and
S. Nguyen, eds.) Equilibrium and Advanced Transportation
Modelling, Kluwer, 245-281, 1998
- Scutellà M.G. ``A strongly polynomial algorithm for the
Uniform Balanced Network Flow Problem'' Discrete Applied
Mathematics 81, 123-131, 1998
- Aarts E. and J.K. Lenstra, eds.
Local Search in Combinatorial Optimization, John Wiley & sons,
Chichester, England, 1997
- Ahuja R.K., T.L. Magnanti and J.B. Orlin
Network Flows: Theory, Algorithms and Applications, Prentice-Hall,
Englewood Cliffs, NJ 1993
- Dell'Amico M., S. Martello and F. Maffioli, eds.
Annotated Bibliographies in Combinatorial Optimization, Wiley, 1997
- Glover F., E. Taillard, M. Laguna and D. de Werra, eds.
Tabu Search, Annals of Operations Research 41, Baltzer,
- Goldberg D.E. Genetic Algorithms in Search
Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989
- Hiriart-Urruty J.-B. and C. Lemaréchal Convex
Minimization Algorithms A Series of Comprehensive Studies in
Mathematics 306, Springer-Verlag, 1993
- van Laarhoven P.J.M. and E.H.L. Aarts
Simulated Annealing: Theory and Applications,
Reidel, Dordrecht, 1987
- Yang C.C. Relational Databases, Prentice-Hall,
Englewood Cliffs, NJ, 1986