Home » Gruppi Di Ricerca » 18326
Combinatorial Optimization

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.




© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma