Operations Research and Discrete Optimization

Research focus

The Peer review has evaluated this group as Excellent

The main research focus of the group is on the study and the solution of linear and nonlinear discrete optimization problems, with an emphasis on problems related to graphs and networks. Most of the recent work is motivated by practical and relevant applications but simplifications or abstractions of the resulting problems are also investigated from a theoretical point of view. The areas of application span from telecommunications and transportation to health care management. The main methodologies include: mathematical programming; the design and analysis of exact, approximate and heuristic algorithms; computational complexity and graph theory. Considerable attention is devoted to optimization in telecommunication networks. This research line strongly benefits from the tight collaboration with the Networking group of DEI. Wired network design. Although network design is a well-studied topic, the ever changing technology leads to new and challenging optimization problems. Our emphasis is not only on classical issues related to link configuration (topology, link capacity,…) but also on node configuration and dimensioning. These problems arise in traditional transport networks as well as in optical networks, where node switching capabilities may substantially affect the network efficiency. They also occur in IP networks adopting MPLS protocol, where statistical multiplexing allows to better exploit the link capacities. Since in many settings (e.g. Virtual Private Networks) only partial traffic demand information is available, we started investigating network design problems under traffic uncertainty. Wireless network design. A central task is to decide where to locate antennas and how to configure them in order to cover a given service area, while taking into account the peculiarities of the radio interface. Our focus is on new generation wireless systems which are pervasive and where interference plays a critical role. In particular, we have considered third generation (UMTS) cellular networks and Wireless Local Area Networks (WLANs). For UMTS networks we aim at a good trade-off between minimizing cost and maximizing coverage. For WLANs a relevant objective is to maximize the network efficiency. Many of these network design problems give rise to interesting variants of classical discrete optimization problems, such as multi-commodity flows and set covering, which are investigated from the theoretical, algorithmic and applied point of views. In the field of transportation, an ongoing project is devoted to a new type of flexible collective transportation system. The purpose is to combine the advantages of fully flexible transportation systems such as Dial-a-Ride with those of traditional fixed-line systems. Due to stochastic demand, both the design and management phases lead to new and challenging combinatorial optimization problems. We also address other optimal routing problems arising in freight transportation and in waste collection and recycling. Our optimization algorithms exploit the problem structure and are used by freight and garbage collection companies. As far as graph and combinatorial problems are concerned, the focus is on complexity and algorithmic issues. For instance, we investigate the problems of finding minimum fundamental cycle and cut bases in a graph, minimum cuts with cardinality constraint, and maximum cuts with 274 limited unbalance. Inverse combinatorial optimization problems related to matroids are also studied. Another line of research is devoted to discrete optimization problems related to infeasible linear systems. In particular, we investigate structural, algorithmic and applied aspects of the Maximum Feasible Subsystem (MaxFS) problem: given an infeasible linear system, find a maximum feasible subsystem. Weighted and unweighted versions of MaxFS have a wide range of applications in areas such as computational biology, data mining and machine learning, image and signal processing, radiation therapy, and telecommunications. In 2006 the group began coordinating a project on planning and operating a health emergency service in collaboration with other Italian researchers and the local emergency call center. This project involves interesting aspects of data analysis, facility location, on-line algorithms, scheduling, rostering and workforce management, simulation and game theory. Part of the above research activities were conducted in collaboration with colleagues from several international institutions, including: Bilkent University, Turkey, Cornell University, USA, Zuse- Zentrum für Informationstechnik Berlin (ZIB), Germany, Linköpings Universitet, Sweden, Universidade Federal do Rio de Janeiro, Brasil, Universidad de La Laguna, Spain, Université de Montreal - Centre de Recherche sur les Transports, Canada, University of Kaiserslautern, Germany, University of Oxford, UK. The research projects are partially funded by public agencies as well as several public and private companies.

Departments

Dipartimento di Elettronica e Informazione (DEI)

Professors

Francesco Maffioli (full professor)
Federico Malucelli (full professor)
Edoardo Amaldi (associate professor)
Giuliana Carello (assistant professor)