Combinatorial Optimization
Research Lines:
• Polyhedral Combinatorics
• Graph theory and Optimization
• Data Mining and Classification
• Portfolio Optimization
• Telecommunication Network Design
• Computational Biology and Polymer Sequencing
• Satisfiability in Propositional Logic
• Information Reconstruction
• Robust Optimization
• Scheduling and Job-shop Scheduling
Members:
Renato Bruni, Antonio Sassano (leader).
PhD students:
Alessandra Reale.
Combinatorial Optimization searches for an optimal set of objects into a finite (but large) collection of sets. Graph Theory, Integer Programming and Polyhedral Combinatorics are the key methodological tools in this area.
The activity of the Combinatorial Optimization Group at DIS dates back to the early ’90s and has been focused both on the theoretical properties of combinatorial structures and the use of sophisticated algorithmic tools to solve real-life problems. In particular, major research has been carried out on the following subjects: polyhedral properties of set covering, stable set and p-median problems; perfect graph theory, exact and heuristic algorithms for stable set and set covering; algorithms for coloring and frequency assignment problems; decomposition algorithms and reformulations for wireless network design problem; fixed network design and survival network design; algorithms for jobshop scheduling and railway traffic management; algorithms for satisfiability of logic formulae, algorithms for information reconstruction in large datasets, algorithms for classification besed on propositional logic, algorithms for inconsistency selections.
The group is currently cooperating with the University of Maastricht, University of Oslo, Università di Roma Tor Vergata, Università dell’Aquila, Università di Lecce, Politecnico di Milano, Università del Sannio, Italian National Statistic Office (Istat), Texas Tech University, ZIB Berlin. The group has been involved in a large number of national and international projects.
The scientific leadership gained in the field of optimal design of broadcasting networks has motivated a stable cooperation with the Italian Authority for Research Telecommunication and the decisive contribution of the group to the design of the national (analog and digital) TV and radio plans.
The expertise gained in the fields of data mining and machine learning also lead to a more than decennial research collaboration with the Italian National Statistic Office (Istat) on themes of information reconstruction. This researches lead to the development of new methodologies for the treatment of data for the 2001 Census of Italian Population, the 2010 Census of Italian Agriculture, the 2011 Census of Italian Population.
In addition to further development of on-going research project, our future activities involve the study of optimization algorithms to rescue or prevent financial crises and for portfolio management; algorithms for weighted matching and stable set problems; polyhedral properties of the stable set polyhedron and of interval and staircase matrices; optimization techniques for classification problems in machine learning; purely combinatorial approaches to wireless network design.
Projects:
APICE - Algoritmi per la Pianificazione Integrata e Controllo di reti wireless Eterogenee, progetto MIUR n. 2878. January 2008 - April 2010 MIUR
Metodi di ottimizzazione su larga scala nelle telecomunicazioni, progetto PRIN 2008, n. 2008LLYXFS. March 2010 - March 2012 MIUR
Modelli Robusti di Ottimizzazione Lineare e Intera per Problemi di Data Mining, Progetto di Ricerca di Ateneo "Sapienza". December 2013 - May 2015
Tecniche di Data Mining efficienti, robuste e basate sull’ottimizzazione per la risoluzione di problemi di Classificazione e Selezione di Investimenti, Progetto di Ricerca di Ateneo "Sapienza". December 2014 - May 2016