STOCHASTIC METHODS · Stochastic methods for combinatorial optimization
FP6 — Marie Curie Actions (Human Resources and Mobility)
- Duration
- 2004-06-01 → 2005-05-31
- EU contribution
- €31,753
- Participants
- 1
- Scheme
- ERG
Lines connect the coordinator with its partners. CORDIS does not always give exact coordinates for projects before 2014. These points are placed at city or country level.
Results in brief
Final Activity Report Summary - STOCHASTIC METHODS (Stochastic methods for combinatorial optimization)
The aim of the project was to study stochastic methods for combinatorial optimisation problems. The work performed can be divided in two stages: theoretical and practical. A modification of ant algorithm has been made. Convergence of the new algorithm to the global optimum has proved. Some research on application of ant algorithm in Multiple knapsack problem (MKP) is done. We studied two pheromone models: pheromone on the nodes of the graph of the problem and pheromone on the arcs of the graph of the problem. The MKP is a constrain problem and gives a lot of possibilities to construct heuristic information. Various types of heuristic information, static and dynamic, have been constructed. Other interesting problem we worked on is GPS network surveying. We applied several stochastic methods and then analysed the achieved results. GRID computing is a form of distributed computing. The problem that we attacked is tasks scheduling on available computing resources. The algorithm is based on ant method and is applied in dynamical way. The achieved results have presented on several international conferences and have reported on some seminars. They have published on conference proceedings and a book chapter.
Data: CORDIS, © European Union
Project objective
Often the combinatorial optimization problems are very hard and to find an optimal solution can take some months. If some does not necessary need un exact solution an approximation algorithm can be used instead. An approximation algorithms aims to find a good" but not necessary the optimal one, within a realistic computational time. Stochastic algorithms are this kind of algorithms. A wide variety of optimization problems have been studied and can be found in the literature. Although they represent an impr essive diversity of real life decision problems. A procedure that is fast, easy and cheap to develop, understand, implement, execute and maintain and that consistently yield satisfactory solutions, is therefore often seen as the most suitable algorithm in practice. Examples of stochastic algorithms are simulated annealing, evolutionary computation, ant colony optimization, Monte Carlo methods. The problems on which these methods are applied come from real life and industry. The research method will be both practical and theoretical. It is structured along two orthogonal lines, stochastic methods and problems. The stochastic methods are one of the most effective methods to solve hard problems. The project will allow the applicant to reintegrate and to exchang e knowledge's. It will deep her knowledge's about stochastic methods learning different methodologies. It is not negligible that the period of re-integration will be followed by permanent position. The host institution is in the country of the nationality of the applicant and the project will help for the development of this less developed region of Europe."
Original text from CORDIS.
Participants
- INSTITUTE OF PARALLEL PROCESSING · SOFIACoordinatorCity levelBulgaria
Links
Data: CORDIS, © European Union