# Proposal for COLOR 2007 project : GenOpt

DISI : Dipartimento di Informatica e Scienze dell'Informazione - Università di Genova

## Project goal and duration

The goal of the GenOpt project is to design and implement new graph algorithms, especially in the fields of network optimization and graph representation.

The objective is to use advanced techniques in combinatorial optimization and graph theory to improve the existing solutions to these problems, while implementing the resulting algorithms in the Mascopt library developed at Mascotte team.

**The duration of the project is one year.**

## Involved Teams

Mascotte & DISI - Università di Genova

### DISI: Dipartimento di Informatica e Scienze dell'Informazione - Università di Genoa

DISI is the Department of Computer Science of the University of Genoa and was established in 1992, while the University of Genoa is one of the oldest Italian Universities and dates its origin in the Middle-Age. Nearly sixty people are engaged in research, with a teaching staff of about thirty; it supports the teaching activity of the programs in Computer Science: Laurea (undergraduate, three years), Master (postgraduate or near), Laurea Specialistica (postgraduate, two years); since 1993 it hosts a PHD program in Computer Science.

The main research areas are: databases and information systems, image processing, machine learning, artificial intelligence, geometric modeling and computer graphics, software development methods, parallel and distributed systems, programming languages, computational logic, computer algebra; research is performed in collaboration with national and international research centres and universities and industry.

In the first ten years of activity DISI ha established collaborations with over a hundred of research institutes in Europe and US. In the last five years 70% of our fund resources came from collaborations with external institutes and companies: EC projects (IV, V, VI framework; ESPRIT, BRITE, HCM, SCIENCE, CRAFT, IST) and MURST/MIUR, CNR, INFM, Parco Scientifico e Tecnologico Regione Liguria and companies (e.g. TXT e-solutions, Elsag, Marconi, Ferrovie dello Stato).

Name | Short CV |
---|---|

Massimo Ancona |
Massimo Ancona is a professor of DISI - Genoa, where he teaches Implementation of programming languages and Distributed Systems. His present research interests include mobile and wireless computing with focus on open-air real-time applications of smartphones and PDAs in mobile wireless networks, network optimization, graph algorithms and data structure. Other research arguments are: programming languages design and implementation, compilers, reflective programming systems and aspect oriented programming. Massimo Ancona participates to the IST projects "Agamemnon"(IST-2-1A-20805) and "Doc@hand" (IST-2-1A-508015), and recently to "Past" (IST-2-1A-20805) and WardInHand" (IST-1999-10479). M. Ancona is member of the Program Committee of the Track on Programming Languages of the ACM Symposium on Applied Computing. |

Vittoria Gianuzzi |
Vittoria Gianuzzi is Associate Professor at DISI, Research Consultant of the CNR IMATI (Istituto per la Matematica Applicata e Tecnologie Informatiche) of Genoa and Director of the Genoa Unit of CINI (Consorzio Interuniversitario Nazionale per l'Informatica). Her research interests include programming languages, software fault tolerance, system tools for parallel programming on NoWs, and performance evaluation for heterogeneous computing systems for parallel applications, GRID computing and Mobile Wireless computing. She was involved as member in a number of national and international projects supported by the MURST, CNR, NATO, and EU, and research responsible for national CNR projects. She is author of more than 100 scientific publications from 1975, she has, in co-operation with colleagues, a copyright for a software system and was member of program committee and reviewer of journals and conferences. |

Gianluca Quercini |
Gianluca Quercini took his degree in computer science in 2005 at Disi (Dipartimento di Informatica e Scienze dell'Informazione, University of Genoa), with a thesis on textual data entry in PDAs. From June to December 2005 he worked at Disi as a researcher on the following topic : "Research and development of interfaces on 3G Mobile Devices and their Use in Focus-Aware Applications". This activity was mainly performed in the ICT European Project Agamemnon. Since January 2006 is a PhD Student at Disi, under the supervision of professor Massimo Ancona. His research interests are graph drawing, graph clustering and information visualization. |

### Mascotte - joint team INRIA Sophia - Antipolis, CNRS I3S and University of Nice - Sophia Antipolis

Mascotte is a joint team between Inria and the laboratory I3S (Informatique Signaux et Systèmes Sophia Antipolis) which itself belongs to Cnrs (Centre National de la Recherche Scientifique) and Unsa (University of Nice - Sophia Antipolis). Furthermore Mascotte is strongly associated with the center of research and development of France Telecom at Sophia-Antipolis via the CRC CORSO (the first Contrat de Recherche Collaborative Inria with France Telecom).

Its research fields are Simulation, Algorithmic, Discrete Mathematics and Combinatorial optimization with applications to telecommunication, global computing and transportation networks.

In particular, Mascotte has developed in the last four years both theoretical and applied tools for the design of heterogeneous networks or networks using various technologies like wavelength division multiplexing (WDM), synchronous digital hierarchy (SDH), Asynchronous Transfer Mode (ATM), fixed, mobile or satellite wireless networks, ...

Name | Short CV |
---|---|

Bruce Reed |
Bruce Reed is currently Research Director at CNRS in the project Mascotte (join project between I3S and INRIA Sophia-Antipolis. He has also been Research Chair in Graph Theory at Mac Gill's University (Montreal). He has written more than 120 papers in Graph theory mainly in journals and also 5 books. He is internationally recognized in coloring problems and probabilistic methods. He is member of the editorial board of Journal of Combinatorial Theory and has been involved in many program committees. |

Michel Syska |
Michel Syska is Maître de Conférences at University of Nice. He received the PhD degree in computer science from the University of Nice - Sophia Antipolis in 1992. His research interests are : network design, routing and grooming algorithms, distributed algorithms. He was recently strongly involved in the following projects: RNRT PORTO, Design and Optimization of WDM Optical Networks (1999 - 2001), IST CRESCCO, Critical Resource Sharing for Cooperation in Complex Systems (2002-2005) and IST AEOLUS, Algorithmic Principles for Building Efficient Overlay Computers since 2005 (member of the technical committee). He is also leading the Mascopt project (Java library for graph and network optimization). |

## Design and implementation of graph algorithms

In this project we would like to share the expertise of the two teams on specific graph or network design algorithms. We would also take advantage of the existing Mascopt library in order to implement the results of common research.

On one hand, we have already initiated collaboration on network design problems, for example with the internship of Paolo Pastorelli (master student from Genoa) in Mascotte from June to November 2006. Another master student is going to come in Mascotte in the cadre of the Leonardo Project Itisform. Here the problem is to study new strategies for traffic grooming in multi-layer networks.

On the other hand, Gianluca Quercini, PhD student in Genoa has started working with Bruce Reed on the subject of data visualization and graph clustering and drawing.

On both hands we want to study new algorithms and implement them with Mascopt. The objective is twofold : first, we want to test the practical efficiency of the algorithm by running experimentation with real data. Second, we want to improve the distribution of Mascopt by adding more "ready to use" classes in the interface of the library.

In the following we describe more precisely the Mascopt library and the problems we would like to work with.

### Implementing Graph Algorithms with Mascopt

Mascopt is a free Java library developed within Mascotte team and distributed under the terms of the LGPL license which is dedicated to graph and network processing. Mascopt includes a collection of Java interfaces and classes that implement fundamental data structures and algorithms.

The main objective of Mascopt (Mascotte Optimization) project is to ease software development in the field of network optimization. Examples of problems include routing, grooming, survivability, and virtual network design. Mascopt help implementing a solution to such problems by providing a data model of the network and the demands, classes to handle data and ready to use implementation of existing algorithms or linear programs (e.g. shortest paths or integral multicommodity flow). A new release of Mascopt has been developed since 2005 in order to allow Mascopt users to program to an interface, not an implementation. Indeed, basic Mascopt users may simply use the existing API, but more advanced users may like to use different implementations of some features. The applications already written will not be affected, they will not have to be rewritten but will have different choices of internal implementation. This may lead to better performances for specific issues. The Mascopt interface was defined in collaboration with Ricardo Correa (Universidade Federal do Ceara, Brazil) to make it compatible with the Parego library implementation to start with. The interface also enables the transparent use of different solvers when writing linear programs.

Mascopt was intensively used within Mascotte industrial cooperation programs for experimentation and validation purposes: with Alcatel Space Technologies on the design of fault-tolerant on-board network satellites, on the optimization of the access layer and planning of satellite communication and with France Telecom on the design of telecommunication backbone networks.

The last version of Mascopt will be publicly available on gforge.inria.fr in January 2007 (user documentation in progress).

### Network Design : Traffic Routing and Grooming

Optical networks using WDM are widely deployed in carrier networks. One important problem is the design and planning of such networks. Given a traffic matrix of demands between all node pairs, and given capacity constraints on the links, the problem is to find the best traffic routing that minimizes the cost of the network. The dominant cost when building the network appears to be the cost of the equipment of the nodes: optical crossconnects (OXC s), optical add/drop multiplexers (OADM s) or add/drop multiplexers (ADM s) that play the interface between the optical and electronical network. Traffic grooming is the optimization problem that aims to reduce that cost.

In this project we want to study the influence of routing algorithms over the performance of grooming. Indeed, the physical paths assigned to the demands are usually computed in the first step of the optimization process. Hence the set of paths used as an input of the grooming problem may not lead to an optimal solution of the general problem (routing and grooming). However, the optimization process may be done in several steps over subsets of demands (for instance by sorting them according to their sizes) and the physical paths could have been fixed by the manager of the network on some geographical or protection purposes.

In this project we will explore different strategies for routing that may improve the grooming process. We will try to use linear programming decomposition techniques but also heuristics.

### Data Visualization and Graph Clustering and Drawing: Issues and Applications

Graphs are among the most studied and used mathematical tools to visualize data and their relationships. The increasing number of applications exploiting their descriptive power makes graph representation a key issue in modern graph theory and computer science. Beside classical applications, particularly exciting and challenging are relatively new fields, such as virtual reality and information visualization. Virtual reality introduces new representations of relationships, based on a metaphor of the real world, requiring approaches that are different from traditional graph drawing. Moreover, in information visualization a huge quantity of information has to be visualized and some knowledge should be extracted from them; therefore data representation has to be not only pleasant, but also meaningful.

Some examples are cartograms, where the area of each region represents a particular statistical value (such as population) associated to it, and communication networks, that are traditionally difficult to manage and update, especially when they are very large.

Graph drawing has been dealing with graph representation for almost thirty years, proposing many solutions and newer issues to be tackled. Works in graph drawing pay a major attention on aesthetic criteria, that, however, are very useful as a good drawing is the first condition for a representation to be functional. The aim of this project is to investigate new directions in graph representation, starting from a technique, rectangular dualization, that has not been well exploited yet for this purpose.

## Workplan

As stated before, we already have initiated some collaboration. More precisely, the plan is the following:

- Gianluca Quercini will visit Mascotte (internship) to work with Bruce Reeds on graph representation. Bruce Reed will use his expertise in graph tree-width and probabilistic methods.
- Massimo Ancona, Vittoria Gianuzzi and Michel Syska will define directions for research for internship students in network optimization
- Michel Syska will supervise the implementation of algorithms in the Mascopt library
- All the listed people will meet and organize seminars in Genoa and Sophia as well

## Cost summary

Title | Cost |
---|---|

6600 euros | 6 months Internship student from DISI in Mascotte (Egide cost) |

5800 euros | 4 months internship student from french Master in Mascotte |

5000 euros | 10 short visits between DISI and Mascotte |

2995 euros | 1 ILOG CPLEX academic license |

20395 euros |
Total |