Giorgio Ausiello, Università di Roma "La Sapienza"
Hyperpaths in directed hypergraphs: Properties and algorithms
Abstract: Directed hypergraphs are a natural generalization of digraphs and are a combinatorial model that turns out to be useful in several application domains (databases, logic, artificial intelligence etc.). Although in general the computation of shortest hyperpaths in directed hypergraphs is an NP-hard problem, for suitable cost measures such problem becomes tractable. In this paper, after discussing the structural properties of hyperpaths (with particular attention to the role of cycles in hyperpaths and to canonic form of hyperpaths), we present a taxonomy of hyperpath cost functions and we study the relationships between the classes of cost functions on hyperpaths and the structure of the corresponding optimal hyperpaths. Finally we illustrate for what classes in the taxonomy shortest hyperpaths can be computed in polynomial time.
George Nemhauser, Georgia Tech
Branch-and-Price Guided Search
Abstract: We present an approach for structured integer programs that solves well-chosen restrictions of the problem to produce high-quality solutions quickly. Column generation is used both for automatically generating the restrictions and for producing bounds on the value of an optimal solution. We present computational experience for fixed-charge multi-commodity flow and inventory routing problems.
Christos Papadimitriou, UC Berkeley
Computational Insights and the Theory of Evolution
Abstract: I shall discuss recent work (much of it joint with biologists Adi Livnat and Marcus Feldman) on some central problems in Evolution that was inspired and informed by computational ideas. Considerations about the performance of genetic algorithms led to a novel theory on the role of sex in Evolution based on the concept of mixability. And a natural random process on Boolean functions can help us understand better Waddington’s genetic assimilation phenomenon, in which an acquired trait becomes genetic.
Paolo Toth, Università di Bologna
Models and Algorithms for the Train Unit Assignment Problem
Abstract: Passenger railway systems are highly complex systems requiring the solution of several planning problems
that can be analyzed and solved through the application of mathematical models and optimization techniques,
which generally lead to an improvement in the performance of the system, and also to a reduction in the time
required for solving these problems.
The planning process is generally divided into several phases: Line Planning, Train Timetabling, Train Platforming,
Rolling Stock Circulation and Crew Planning. In this lecture, after a description of the whole planning process and
of its main phases, the Train-Unit Assignment Problem, an important NP-hard problem arising in the Rolling
Stock Circulation phase, is considered in detail.
In the Train-Unit Assignment Problem (TUAV), we are given a set of timetabled trips, each with a required number
of passenger seats, and a set of different train units, each having a cost and consisting of a self-contained train
with an engine and a set of wagons with a given number of available seats. TUAV calls for the minimum cost
assignment of the train units to the trips, possibly combining more than one train unit for a given trip,
so as to fulfil the seat requests.
Two Integer Linear Programming (ILP) formulations of TUAV are presented, and valid inequalities are introduced
for strengthening the corresponding Linear Programming (LP) relaxation. Additional relaxations, based on the
Lagrangian approach and on the solution of a restricted problem associated with a peak period (i.e., with a subset
of simultaneous trips that must be assigned to distinct train units), are considered for the effective computation
of tight lower bounds. Constructive heuristic algorithms, based on the previously considered relaxations, are proposed,
and their solutions are improved by applying local search procedures.
Extensive computational results on real-world instances are reported, showing the effectiveness of the proposed
bounding procedures and heuristic algorithms.