Combinatorial Optimization is a thriving field at the forefront of discrete mathematics and theoretical computer science. Its main focus is the efficient discovery of specific data structures and optimal set of objects into a finite (but large) collection of feasible solutions. 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 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 job-shop scheduling and railway traffic management; algorithms for satisfiability of logic formulae, algorithms for information reconstruction in large datasets, algorithms for classification based on propositional logic, algorithms for inconsistency selections, algorithms for the optimal and robust determination of control parameters of vehicles or spacecrafts.
The group is currently cooperating with the Italian Ministry of Economic Development, the Italian Authority of Telecommunications (AGCOM), Fondazione “Ugo Bordoni” and Istituto Nazionale di Statistica (ISTAT). In the last 10 years, the group has been involved in a large number of national and international projects and has developed methods and algorithms aimed at the optimal design of broadcasting networks. The scientific leadership 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. 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 clustering and imputation of Educational Institutions in the study of educational systems; 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.
