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 DIAG 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 heuris- tic algorithms for stable set and set covering; algorithms for coloring and frequency as- signment problems; decomposition algorithms and reformulations for wireless network design problem; fixed network design and survival network design; algorithms for job- shop scheduling and railway traffic management; algorithms for satisfiability of logic formulae, algorithms for information reconstruction in large datasets, algorithms for clas- sification besed on propositional logic, algorithms for inconsistency selections.
The group is currently cooperating with the University of Maastricht, University of Oslo, Universita` di Roma Tor Vergata, Universita` dell’Aquila, Universita` di Lecce, Po- litecnico di Milano, Universita´ del Sannio, Istituto Nazionale di Statistica (Istat), Texas Tech University, ZIB Berlin.
The group has been involved in a large number of na- tional and international projects. In the last 10 years the group has developed methods and algorithms aimed at the optimal design of broadcasting networks. The scientific leader- ship gained in this field has motivated a stable cooperation with the Italian Authority for Telecommunication and the decisive contribution of the group to the design of the national (analog and digital) TV and radio plans.
The current key members of the group have published more than 100 journal papers, several book chapters, and two books. Moreover they are or have been editors of some of the main journals in the field of Operations Research and Optimization. Recently the group received a prestigious international award from the Association of European Op- erational Research Societies (EPA 2009). 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; railway traffic control and optimization on single-track networks.