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 activity presentation.

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, max-flow, transportation, transhipment, spanning trees, matching, traveling salesman, generalized assignment, vehicle routing and multicommodity 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 [2], [36] and [18].

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 applications.

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 [40].

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 ``heuristic'' techniques.

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].

Other particular flow problems have been studied, among them the

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

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 hypergraph [17].

Other interesting applications on which some research has been done is that of production systems. Namely both the cutting stock problem [27] and the problem of finding, in a manufacturing system, an assemblying plan which allow the production of a given item at minimum `cost' [25], can be formulated and solved by means of hypergraph techniques.

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 [12]. This solver has already been successfully used in different applications, among which we mention: sequential [15] and parallel [4] cost-decomposition approaches for multicommodity flow problems, computation of lower bounds for the

A methodological contribution of this research has been the introduction of a class of generalized Bundle methods that subsumes several known Bundle variants [14].

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 [5]; vehicle scheduling and transportation problems [8,31,28]; logistics and distribution problems [11]; scheduling and sequencing of activities on machines [23]; 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).

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 of structure.

We plan to enhance our Bundle code using the ideas developed in [14]. In particular, we will experiment with different alternatives to the standard quadratic stabilizing term, namely with those resulting in

Among the application areas for which this structure holds, we mention: 1) scheduling problems on parallel machines; 2)

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 networks.

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

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.

- 1
- Bertsekas D.P., S. Pallottino and M.G. Scutellà,
``Polynomial Auction algorithms for shortest paths'',
Computational Optimization and Applications 4(2), 99-125, 1995

- 2
- Simeone B., P.Toth, G.Gallo, F.Maffioli and
S.Pallottino editors, ``Fortran codes for network optimization'', Annals
of Operations Research 13, 1988

- 3
- Cambini R., G. Gallo and M.G. Scutellà, ``Flows on
hypergraphs'', Mathematical Programming 78, 195-217, 1997

- 4
- 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

- 5
- 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,
247-270, 1993

- 6
- 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

- 7
- 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

- 8
- Carraresi P., F. Malucelli and S. Pallottino ``Regional mass
transit assignment with resource constraints'' Transportation Research B
30, 81-98, 1996

- 9
- 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

- 10
- 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

- 11
- Equi L., G. Gallo, S. Marziale and A. Weintraub ``A combined
transportation and scheduling problem'', European Journal of
Operational Research 97, 94-104, 1997

- 12
- Frangioni A. ``Solving Semidefinite Quadratic Problems
Within Nonsmooth Optimization Algorithms'' Computers & O.R.
23, 1099-1118, 1996

- 13
- Frangioni, A., ``On a New Class of Bilevel Programming
Problems and its Use For Reformulating Mixed Integer Problems'',
EJOR 82, p. 615 - 646, 1995

- 14
- Frangioni A. ``Generalized Bundle Methods'' TR
04/98, Dip. di Informatica, Univ. di Pisa (submitted to SIAM
J. on Optimization), 1998

- 15
- Frangioni A. and G. Gallo ``A Bundle type Dual-ascent
Approach to Linear Multicommodity Min Cost Flow Problems'' to appear in
INFORMS JOC, 1999

- 16
- 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

- 17
- 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

- 18
- Gallo G. and M. D. Grigoriadis, eds. ``Netwok Optimization:
Algorithms and Applications'' Mathematical Programming B 78, 1997

- 19
- Gallo G., M.D. Grigoriadis and R.E. Tarjan, ``A fast
parametric maximum flow algorithm'' SIAM Journal on Computing 9,
30-55, 1989

- 20
- Gallo G., F. Licheri and M.G. Scutellà ``The
Hypergraph Simplex Approach: some experimental results'' Ricerca
Operativa 78, 21-54, 1996

- 21
- Gallo G., G. Longo, S. Nguyen and S. Pallottino ``Directed
hypergraphs and applications'' Discrete Applied Mathematics 42,
177-201, 1993

- 22
- Gallo G. and S. Pallottino ``Shortest path methods: a
unifying approach'' Mathematical Programming Study 26, 38-64,
1986

- 23
- Gallo G. and F. Piccinonno ``A 1/4 approximate algorithm for
P2/tree/Cmax'' Discrete Applied Mathematics 72, 85-98, 1997

- 24
- Gallo G. and D. Pretolani ``A new algorithm for the
propositional satisfiability problem'' Discrete Applied Mathematics
60, 159-179, 1995

- 25
- Gallo,G. and M.G. Scutellà ``Minimum Makespan
Assembly Problems'' TR 10/98, Dip. di Informatica, Univ. di Pisa, 1998

- 26
- Gallo G. and M.G. Scutellà ``Directed Hypergraphs as a
Modelling Paradigm'' to appear in Rivista AMASES, 1999

- 27
- 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

- 28
- Malucelli F., M. Nonato and S. Pallottino ``Demand Adaptive
Systems: some
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

- 29
- Nguyen, S. and S. Pallottino, ``Equilibrium traffic
assignment for large scale transit networks'', European Journal of
Operational Research 37, 176-186, 1998

- 30
- Nguyen S., S. Pallottino and M. Gendreau ``Implicit
enumeration of hyperpaths in logit models for transit networks'',
Transportation Science 32, 54-64, 1998

- 31
- 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)

- 32
- Pallottino S. and M.G. Scutellà ``Dual algorithms for
the shortest path tree problem'' Networks 29, 125-133, 1997

- 33
- Pallottino S. and M.G. Scutellà ``Shortest path
algorithms in
transportation models: classical and innovative aspects'' in (P. Marcotte and
S. Nguyen, eds.) Equilibrium and Advanced Transportation
Modelling, Kluwer, 245-281, 1998

- 34
- Scutellà M.G. ``A strongly polynomial algorithm for the
Uniform Balanced Network Flow Problem'' Discrete Applied
Mathematics 81, 123-131, 1998

### Other references

- 35
- Aarts E. and J.K. Lenstra, eds.
Local Search in Combinatorial Optimization, John Wiley & sons,
Chichester, England, 1997

- 36
- Ahuja R.K., T.L. Magnanti and J.B. Orlin
Network Flows: Theory, Algorithms and Applications, Prentice-Hall,
Englewood Cliffs, NJ 1993

- 37
- Dell'Amico M., S. Martello and F. Maffioli, eds.
Annotated Bibliographies in Combinatorial Optimization, Wiley, 1997

- 38
- Glover F., E. Taillard, M. Laguna and D. de Werra, eds.
Tabu Search, Annals of Operations Research 41, Baltzer,
Basel, 1993

- 39
- Goldberg D.E. Genetic Algorithms in Search
Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989

- 40
- Hiriart-Urruty J.-B. and C. Lemaréchal Convex
Analysis and
Minimization Algorithms A Series of Comprehensive Studies in
Mathematics 306, Springer-Verlag, 1993

- 41
- van Laarhoven P.J.M. and E.H.L. Aarts
Simulated Annealing: Theory and Applications,
Reidel, Dordrecht, 1987

- 42
- Yang C.C. Relational Databases, Prentice-Hall, Englewood Cliffs, NJ, 1986