Geographically Distributed Environments: A Combinatorial Optimization Library

CICYT Sub-project TIC99-0754-C03-03 (Hybrid Methods)

MA-LL-BA

This is the most updated web site for the sub-project TIC99-0754-C03-03 developed at the University of Málaga (UMA) inside the core project MALLBA.

MALLBA is a CICYT funded project made up of three subprojects located in research groups developing their work at the University of Málaga (UMA), the University of La Laguna (ULL) and the University Politechnique of Cataluņa (UPC) (MAlaga+La Laguna+BArcelona=MALLBA). They are all in SPAIN; the last link (UPC) holds the information of the whole project statements.

The main goal of the MALLBA project is to develop generic optimization software skeletons that run in sequential, LAN and WAN environments. There are lots of added value sub-goals to this general statement:

The major achievements in this sub-project are defined in the development of hybrid and parallel algorithm skeletons. The goal of our sub-project can be roughly stated as designing and implementing combination of heuristic and exact algorithm skeletons to achieve more efficient and accurate optimization procedures.

The project is scheduled to offer annual results in terms of new skeletons in the three above mentioned environments: sequential, local area network and wide area network. The main outcomes of every year will be new releases of the mallba library in each evnvironment, although many other related stuff will also be developed in order to understand and ease the work of the project. Some examples of such a work will be a common communication module to program the parallel skeletons, measurements to model the connectivity of our three research centers, preliminary numerical results to guide the implementations, and a benchmark of problems solved with the developed instances. Herein we summarize the results of our sub-project on heuristic algorithms.

YEAR 2000 (first project year)

This year the goal is to provide sequential skeletons as well as to forecast and create stuff to sustent the developments of the second year.To achieve these goals we have studied the requirements of a skeleton system in order to support hybrid methods combining heuristic and exact procedures in a general way (working document on hybrids).

The general conclusion of this analysis is that the skeletons to be hybridized needs a public interface to access and to modify their search state, in order to merge two or more algorithms in the bybrid version. A second result in this study is the necessity of allowing slicing of the algorithms in that they must allow separate execution of atomic search operations, in order a hybrid algorithm could take advantage of this facility to merge the execution steps of several skeletons to yield a new(hopefully more efficient) hybrid algorithm.

Then, we deeply studied the different alternatives to implement a basic communication module to be used in the next phase (working document on middleware of May 30 2000). This study showed MPI as the best choice for our project due to its efficiency, standardization and goo perspectives of future releases. Other message passing librarie such as PVM, LEGION, and other different paradigms such as OpenMP or BSP were considered but judged unsuitable for our goals. Using Java-RMI, Globus or CORBA is, at this point, still under consideration. Also, it is planned to support LEDA objects in the communication module.

YEAR 2001 (second project year)

This second year is devoted to implementing LAN skeletons of hybrid algorithms.

First of all, we have made a revision of the communication module services (revised document on middleware January 30 2001). Here, we first introduced NetStream, a C++ library implemented on MPI whose major achievement is to be quite easy to use and that represents a point to future enhacements for the LAN and WAN phases of the MALLBA project. Although LEDA objects were initially considered, they were definitely left out in new versions coming after NetStream v1.0.

At present, NetStream v1.6 is available, allowing users to send many basic types, both raw and packed, and providing methods to create group of processes in order to model the third phase of WAN (linked clusters) utilization. The basic interface, examples of use and performance evaluation graphs are showed in the precedent link to provide a self-contained information about this library. An HTML on-line version explaining NetStream v1.6 can be reached by clicking here.

As to the main goal of developing hybrid LAN skeletons we already made some progress and have almost finished the work for this year (click here to get a summary of results in Spanish):

We have addressed several optimization problems. Some of them are pure combinatorial optimization tasks, such as the maximum cut problem in graphs. Some others are applications of such class of problems, like assigning communication frequencies to cellular phone links, designing error correcting codes for optimal transmission of information through a noisy communication network or solving lab problems to assess the functionalities of the developed skeletons.

Some of the publications of these, and other related stuff, made by our group in Málaga are these:

  1. E. Alba, A.J. Nebro, J.M. Troya, Heterogeneous Computing and Parallel Genetic Algorithms, Journal of Parallel and Distributed Computing, 2001 (to appear)
  2. E. Alba, Parallel Evolutionary Algorithms Can Achieve Super-Linear Performance, Information Processing Letters, 2001 (en prensa)
  3. E. Alba, J.M. Troya, Gaining New Fields of Application for OOP: the Parallel Evolutionary Algorithm Case, The Journal of Object-Oriented Programming, 2001 (to appear)
  4. E. Alba, J.M. Troya, Improving Flexibility and Efficiency by Adding Parallelism to Genetic Algorithms, Statistics and Computing, 2001 (to appear)
  5. E. Alba, J.M. Troya, Analyzing Synchronous and Asynchronous Parallel Distributed Genetic Algorithms, Future Generation Computer Systems, 17(4):451-465, January 2001
  6. Alba, S. Khuri, Applying Evolutionary Algorithms to Combinatorial Optimization Problems, Alexandrov V.N., Dongara J.J., Juliano B.A., Renner R.S., Tan C.J.K. (eds.), Proceedings of the International Conference on Computational Science (ICCS'01), LNCS vol. 2074, Part II, Springer-Verlag, Berlin, Heidelberg, pp. 689-700, 2001
  7. C. Cotta, E. Alba, R. Sagarna, P. Larrañaga, Adjusting Weights in Artificial Neural Networks using Evolutionary Algorithms, P. Larrañaga, J.A. Lozano (eds.) Estimation of Distribution Algorithms. A New Tool for Evolutionary Computation, chapter 18, pp. 357-373, Kluwer Academic Publishers, 2001
  8. C. Cotta, J.M. Troya, Analyzing Directed Acyclic Graph Recombination, Computational Intelligence: Theory and Applications, B. Reusch (ed.), Lecture Notes in Computer Science 2206, pp. 739-748, Springer-Verlag Berlin, 2001
  9. R.E. Berretta, C. Cotta, P. Moscato, Forma Analysis and New Heuristic Ideas for the Number Partitioning Problem, Metaheuristics International Conference, pp. 337-341, Oporto, 2001
  10. C. Cotta, J.M. Troya, A Comparison of Several Evolutionary Heuristics for the Frequency Assignment Problem, Connectionist Models of Neurons, Learning Processes, and Artificial Intelligence, J. Mira, A. Prieto (eds.), Lecture Notes in Computer Science 2084, pp. 709-716, Springer-Verlag Berlin, 2001
  11. M. Díaz, B. Rubio, E. Soler, J.M Troya, DIP: a Pattern-based Approach for Task and Data Parallelism Integration. The 16th ACM Symposium on Applied Computing (SAC'2001). Special Track on Coordination Models, Languages and Applications. Las Vegas, Nevada (USA), Marzo 2001.
  12. M. Díaz, B. Rubio, E. Soler, J.M Troya, Integrating Task and Data Parallelism by means of Coordination Patterns. The 6th International Workshop on High-level Parallel Programming Models and Supportive Environments (HIPS'2001). LNCS vol. 2026, Springer-Verlag, pp. 16-27. San Francisco, California (USA), Abril 2001.
  13. M. Díaz, B. Rubio, E. Soler, J.M Troya, A Pattern-based Language to Coordinate HPF tasks, Primeras Jornadas sobre Lenguajes de Programación (PROLE'2001). En prensa. Almagro (Ciudad Real), Noviembre 2001.
  14. M. Díaz, B. Rubio, E. Soler, J.M Troya, A Border-based Coordination Language for Integrating Task and Data Parallelism, Journal of Parallel and Distributed Computing, 2001 (to appear).

 

YEAR 2002 (third and final project year)

Since we are at present finishing the next (LAN) release of the MALLBA library, the main activity consists in sticking the sub-projects results together and to anticipate the needs of the final year. The foreseen activies are those:

 

This site has been developed and mantained by Enrique Alba

Noviembre 16, 2001