Trois questions à Francesca Rossi

Francesca Rossi est une des spécialistes en résolution de problèmes de contraintes valuées et avec préférences. Elle est aussi actuellement la présidente de l’ACP. Elle a accepté de se soumettre au jeu des trois questions:

1. You are one of the expert in valued constraints and preferences. What are the successes in this field ? What remains to be done ?

Since the first papers on soft/valued constraints, published in 1995, twelve years have passed, and many results have been obtained. In particular, many formalisms to model several kinds of preferences have been defined, their properties have been studied, and efficient algorithms to solve problems with such preferences have been developed. Examples are max and weighted CSPs, fuzzy constraints, probabilistic constraints, and more generally soft constraints, valued constraints, and CP-nets. The attempt has been to balance the desire of general modelling tools with the need for efficient solvers. This delicate balance has been obtained in several instances, also with the help of new soft global constraints, that have enhanced the efficiency of specific solvers. While soft/valued constraints have shown their convenience in modelling problems with quantitative preferences, CP-nets have tackled problems with qualitative and conditional preferences. Several applications have used one of the existing formalisms to model and solve efficiently real- life problems with some sort of preferences. So, since 1995, the community has grown and worked hard to exploit the power of preferences in constraint problems, and to show its advantages in practice.

However, much remains to be done. First, many kinds of preferences, which often occur in real life, cannot be cast in the existing formalisms. This is the case for bipolar preferences, which allow for the specification of both degrees of desires and degrees of rejection. Also, the many existing formalisms have to be better connected, to allow users to pass from one to the other one. Moreover, preferences often occur together with uncertainty, so these two notions must both be considered and tackled efficiently. In brief, the ultimate goal should be to allow for the specification of many kinds of preferences and uncertainty, and to develop efficient solvers for such problems.

Constraint Programming is a concept and a technology and it has to be open to external influences. In your opinion, what are the most interesting existing (or future) connections between CP and other fields, disciplines or applications ?

Certainly CP should continue the long connection and cross-fertilization with both AI (Artificial Intelligence) and OR (Operation Research). The AI line of work brings new modelling tools, and allows CP to relate to other knowledge representation formalisms, while the OR line brings new efficient solvers. We certainly need both of them. It is CP’s strength to provide both, and to be at the edge between science and engineering, and between basic research and applications.

However, the connection with other disciplines can also be very helpful. One promising connection could be with the discipline of decision theory and social choice (which is also part of OR). This discipline could be very useful in understanding what to do when preferences are specified by several agents, and thus need to be aggregated. On the other hand, constraint-based technology can be useful in this respect, to propagate information between preferences and agents, and thus make aggregation more efficient. Classical results in preference aggregation, which have to do with the possibility or impossibility of the co-existence of certain properties, could be enhanced and updated by considering computational aspects. Other aspects, such as uncertainty, also come naturally in this setting, where lack of information is often coupled with privacy issues.

The collaboration with these disciplines could be very useful for distributed preference aggregation in general. An instance of this scenario can be found in web-based systems, where it is natural to have preferences that come from different sources and sites. It is peculiar that CP technology has not yet fully shown and exploited its power in web-based systems, as it has been done by other dsciplines, such as algorithm theory. This collaboration could be very helpful in this respect.

1. What actions can be done to strenghten the visibility of CP, for example in the EU program FP7 ?

Certainly CP has all the ingredients to sustain both successful basic research actions and significant industrial projects. Both avenues should be followed in FP7 to show the power of CP to the european community. Another important kind of actions are those supporting collaborations, exchanges, and events, such as those in the COST program, that can help building the base for future projects.

The presence in Europe of the only lab in the world devoted to constraint programming (4C, Cork, Ireland), which has been open more than 5 years ago and continues to receive substantial funding from various sources, is already a very good asset for CP, at least in Europe. To have more chances of convincing those who will decide about the EU funds, the role of the Association for Constraint Programming can also be very important. The ACP can do many things to help: it can coordinate and solicit the proposal of actions, it can discuss, coordinate, and league with other associations and international organizations, and it can lobby at the EU level by talking to project officers at international EU meetings.

The ACP started officially in 2005, and since then it has concentrated mainly on giving more support to the community’s internal activities and to young researchers. This is very important to build the foundations of a successful and healthy research community. This has been done, for example, with the start of the CP summer school, the higher support to the doctoral program at the CP conferences, the start of the CP newsletter, and the ACP and CP online web sites. Without stopping this line of work, now the ACP is in the position to help the community also in other ways, such as providing support at the international level, both in Europe and in other continents, for a better recognition of the potential of CP in the funding arena. Personally, I will do what I can to help the ACP grow also in this direction.