Cover ERCIM News 56

This issue in pdf
(48 pages; 10,6 Mb)

Archive:
Cover ERCIM News 55
previous issue
Number 55
October 2003:
Special theme:
Machine Perception

all previous issues

Next issue:
April 2004

Next Special theme:
Games Techlology

About ERCIM News

Valid HTML 4.01!
spacer
 
< Contents ERCIM News No. 56, January 2004
R&D AND TECHNOLOGY TRANSFER
 

Solving Complex Problems with Advanced Techniques

by Enrique Alba

The area of complex problems and modern solving techniques is one of the multiple research lines in progress at the University of Málaga. It has been addressed in the research projects ‘MALLBA’ and ‘TRACER’.

Complex problems - those that can only be solved in non-polynomial time - are becoming common in all the domains of our lives: telecommunications, economics, bio-informatics, industrial environments etc. In these and other fields of research it is often essential to model and solve optimisation, learning, or searching tasks for applications that do not admit an easy formulation. In fact, it is often the case that the problem at hand is non-differentiable, has a large number of constraints or objectives, does not admit contour conditions, or is ill-defined. Also, most real-life problems show a high degree of inter-parameter linkage (epistasis), many locally optimal solutions (multimodality), and present a high dimension.

All these ideas were included in the recently completed MALLBA project (2000-2003), and are being extended in TRACER (2003-2005), a new set of proposals for dealing with complex problems. The MALLBA project was an effort to develop an integrated library of skeletons for optimisation containing exact, heuristic, and hybrid techniques. One important outcome of the project was the MALLBA library, which is publicly available at http://neo.lcc. uma.es/mallba/easy-mallba. The three target environments considered for solving complex problems are sequential, LAN, and WAN computer platforms. The list of modern techniques we consider in our studies with MALLBA and TRACER includes evolutionary algorithms, simulated annealing, memetic algorithms, ant-colony algorithms, scatter search, and a set of variations on well-known techniques like branch-and-bound, randomised local search, etc.

Software skeletons are somewhat similar to simplified software patterns. In MALLBA, software skeletons for all these algorithms have been built with a common internal and public interface. This permits fast prototyping and transparent access to parallel platforms. MALLBA skeletons distinguish between the concrete problem to be solved and the solver technique. Skeletons are generic templates to be instantiated by the user with the features of the problem. Much work has been put into designing reliable, general algorithms, and a permanent interest exists in using software engineering concepts for correct design. All the knowledge related to the solver method (eg parallel considerations) and its interactions with the problem are implemented by the skeleton and offered to the user.

Skeletons are implemented by a set of required and provided C++ classes that represent an abstraction of the entities participating in the solver method. Provided classes implement internal aspects of the skeleton in a problem-independent way. The most important provided classes are 'Solver' (the algorithm) and 'SetUpParams' (configuration parameters). On the other hand, required classes specify information related to the problem. Each skeleton includes the 'Problem' and 'Solution' required classes that encapsulate the problem-dependent entities needed by the solver method. Depending on the skeleton, other classes may be required.

Therefore, the user of a MALLBA skeleton need only implement the particular features related to the problem. This speeds up considerably the creation of new algorithms with minimum effort, especially if they are built up as combinations of existing skeletons (hybrids). Figure 1 shows an example of design for a simulated annealing algorithm.

Figure 1: UML design of a simulated annealing heuristic in MALLBA.
Figure 1: UML design of a simulated annealing heuristic in MALLBA.

The focus of MALLBA was mainly in creating the software and hardware infrastructure (especially an operative WAN) for later developments, while accounting for parallelism and hybridisation. Many application domains have been addressed within MALLBA, but at the same time, many important issues concerning the problems and the techniques themselves were deferred for TRACER.

In the new TRACER project (http://tracer.lcc.uma.es) therefore, powerful and robust algorithms are being developed in close connection with the Internet. Again, in all our research we pay close attention to efficiency and to the software design aspects of the algorithms. This project represents a joint effort of five groups in Spain, coordinated from the University of Málaga and devoted to proposing solutions and algorithms (in C++ and also in Java) that outperform existing cutting-edge optimisation techniques. We are working on two fronts: achieving results having the best-so-far accuracy for the considered problems, and developing algorithms for these that show the best-so-far numerical efficiency. At the end of the project we expect to provide the research community with leading algorithms and accurate results, thereby enhancing scientific knowledge on optimisation. Some successful case studies include the following:

  • Computing optimal routes for the vehicle-routing problem (vehicular technology). VRP is an important NP-hard problem for which we are able to design minimum cost routes for a fleet of vehicles with a cellular evolutionary algorithm. In this algorithm, tentative solutions evolve in overlapped neighbourhoods connected in a 2-D grid topology. Using local searching in each iteration (specifically 2-opt plus l–interchange algorithms) has been the key step in outperforming other algorithms in wall-clock time and accuracy. Real-life instances taken from the city of Málaga have been solved to optimality quite efficiently (see Figure 2 left). In Figure 2 (centre) we show a partial solution covering 85.6% of the area. The colour codes indicate whether a given location is covered by 0, 1, 2, 3 or 4 antennae. An optimum solution will have all the area (100%) covered by exactly one single antenna (colour code 1).
  • Designing optimal error-correcting codes (information theory) showing the highest minimum Hamming distance between codewords (see an example in Figure 2, right). For this problem, distributed evolutionary algorithms and a new local search algorithm inspired by the repulsion of charged particles have been used. The numerical effort of our algorithms makes it possible for the first time to obtain solutions for large instances of this problem, in which at present the optimum can only be said to belong to a certain range of values.
  • The optimal location of antennae (telecommunications) is another hot topic of research, since UMTS, mobile, and wireless platforms need a new set of networks for their development over the whole of Europe. We have proposed distributed algorithms able to compute solutions covering 100% of the area with a minimum set of strategically located antennae. While in the past this problem required around forty machines working for many hours to reach a solution, our algorithms can now provide us with optimum solutions in a few minutes using between one and eight CPUs. In fact, we are extending these algorithms to other hard problems suggested by well-known telecommunication companies in Europe, in which a physical model of wave propagation plus detailed information of the geographical area is included.
  • Optimisation in continuous domains is an additional line in our research. This kind of problem frequently requires very different algorithms to those found in combinatorial optimisation. We have recently proposed a parallel hypercubic evolutionary algorithm dealing with heterogeneous operations including concepts from fuzzy logic to solve continuous problems: systems of linear equations, computing filters for sound waves, polynomial fitting (Chebyshev), and training neural networks among others.
  • The new and exciting field of grid computing is also being addressed to solve some of the most difficult problems. Condor and Globus are two of the most successful technologies we have been using, just as XML and SOAP have been studied for some cases. Concretely, we have developed a new grid algorithm to compute the exact Pareto front of several hard multi-objective problems by using Condor in a grid with more than 100 computers in our department (http://neo.lcc.uma.es/Software/ESaM). At present, we are extending the grid to other sites in Spain and Europe.
Figure 2
Figure 2: Example of a real VRP in Málaga, location of antennae (left, centre) and error-correcting codes.

We are also working on other topics like bio-informatics or dynamical optimisation (DOP). However, besides working on the algorithmic aspect, we are aware of communities of users demanding solutions for their own problems. This is why we plan to release a public Internet service that will help researchers to solve complex problems by feeding them (written in Java, C++, and other languages) into a client/server system and then selecting one solver from an assorted set of algorithms to obtain a solution with a short round-trip time and low effort. Any kind of comment, idea, or collaboration is welcome.

Link:
http://neo.lcc.uma.es

Please contact:
Enrique Alba, University of Malaga/SpaRCIM
Tel: +34 952 132803
E-mail: eat@lcc.uma.es
 

spacer