EUSACOU

European South American network on Combinatorial Optimization under Uncertainty

 Partecipanti

Mappa

 Word cloud

Esplora la "nuvola delle parole (Word Cloud) per avere un'idea di massima del progetto.

 Obiettivo del progetto (Objective)

'The purpose of this program is to stimulate research cooperation between Europe and South America in the field of uncertainty in combinatorial optimization. Combinatorial optimization is a lively field in mathematics and computer science. It aims at finding a best solution among a finite or countably infinite number of solutions. In standard optimization techniques, we assume that all the relevant data to the problem are completely known. However, this assumption is not always realistic. In many scenarios, we need to optimize when the data is not fully available and decisions with wide-ranging implications have to be made in the face of incomplete data. In this project, we study methods for dealing with uncertainty in combinatorial optimization. We will study three different models for uncertainty. The first one is online optimization in which decisions have to be made without any knowledge of future information to be released. A second model is stochastic optimization in which the uncertainty is modeled by the assumption that part of the data is given only by probability distributions. The third model for uncertainty is by an algorithmic game theory approach. Here it is assume that the solution is obtained by the interaction of a multitude of autonomous agents, each of which is holding private information. Therefore, there is no centralized control that has access to all relevant input data and that is able to enforce the computed solution as the final outcome. The objectives of this international research staff exchange prgoram are: 1. Intensify th ejoint research in optimization under uncertainty among researchers in Europe and South America 2. Training of junior researchers 3. Disseminate and transfer knowledge obtained during the program among academics in South America and the European Research Area.'

Introduzione (Teaser)

Many complex everyday problems involve finding the best of all possible solutions. An EU-funded project brought together scientists from both sides of the Atlantic Ocean to study effective algorithms for cleverly solving such problems.

Descrizione progetto (Article)

Most optimisation problems in real life do not have accurate estimates of parameters, such as costs and demands. At best, a probability distribution over the parameter values is known. Classical optimisation approaches are not useful in these cases, as the optimal solution found can be very sensitive to the slightest change in problem parameters.

Both Europe and South America possess expertise in mathematical programming and graph-theoretic algorithms dealing with this uncertainty for optimisation problems, representing a golden opportunity to collaborate in the field. This was the aim of the EU-funded project 'European South American network on combinatorial optimization under uncertainty' (EUSACOU).

To achieve its aims, EUSACOU fellows explored three different models for dealing with uncertainty. The first model, called online optimisation, assumes no knowledge of the future, whereas the second model, called stochastic optimisation, makes some guesses on what the future could be like. Finally, the third model involves a multitude of autonomous agents, each of which holds private information with no centralised access.

One application involved scheduling problems in which jobs may be split into parts to be processed simultaneously on more than one skilled machine. Optimisation problems of this kind are encountered when modelling the planning of disaster relief operations. Using newly developed approximation algorithms, EUSACOU fellows analysed the quality of scheduling policies and were able to glean valuable data.

Other uncertainty issues tackled pertained to social networks and to traffic assignment. For modern web search engines, EUSACOU fellows proposed and evaluated a static cache to speedup computation by exploiting results of queries that appeared in the past. Different approaches to populating the cache were examined to ultimately design a query resolution strategy offering substantial memory and time savings.

Junior researchers that received training within the EUSACOU project had the opportunity to share their findings during the closing workshop. The cross-fertilisation of ideas emerging from two continents is an excellent example of academic and research cooperation. This will likely attract talented researchers from abroad to work in Europe and open the European Research Area (ERA) to South America.