Geographically Distributed Environments:
Combinatorial Optimization Library

TIC1999-0754-C03



Combinatorial optimization problems arise in various fields such as control theory, operational research, biology and computer science. Exact methods like divide and conquer, branch and bound and dynamic programming have been traditionally used to solve these problems, however, the computational requirements of these methods may be prohibitive. As an alternative, heuristic methods usually provide good solutions in reasonable running times. Local search, spectral techniques and evolutionary algorithms are well known heuristic methods.

A key feature of all the previously mentioned methods is their genericity: they can be easily adapted to solve different problems because they can be described as search skeletons, which are general optimization procedures. In this case, the quality of the obtained solutions depends both on the running time and on the amount of problem-dependent knowledge inserted into the algorithm (hybridization).

Parallel computing systems offer a way to provide the large computing power necessary for handling the increasing complexity of combinatorial optimization problems. Parallelism also plays an important role in developing hybrid algorithms. Clusters of existing commodity workstations are a low-cost hardware alternative to run parallel programs although, in this case, issues as heterogeneity and work load appear.

Application frameworks are a way to reduce the development difficulties by focusing on the reuse of parallel code. Several frameworks offering parallel implementations for generic optimization techniques such as simulated annealing, branch and bound, or genetic algorithms have been proposed (see, e.g. parSA, PGAPack, PPBB, PICO). In these frameworks, the user just describes the elements defining her problem and then instantiates the procedures that parameterize the selected generic method. In the parallel case, these frameworks contribute to reduce the gap between users and parallel architectures, because they hide the implementation details and allow executing parallel programs by just writing sequential code.

Some existing frameworks, such as Local++ , its successor EasyLocal++, Abacus and Bob++, provide sequential and parallel generic implementations for several exact, heuristic and hybrid methods, but lack features to integrate them.

The MALLBA project is an effort to develop, in an integrated way, a library of skeletons for combinatorial optimization (including exact, heuristic and hybrid methods) that can deal with parallelism in a user-friendly and, at the same time, efficient manner. Its three target environments are sequential computers, LANs of workstations and WANs. The main features of MALLBA are:

  • Integration of all the skeletons under the same design principles.

  • Facility to switch from sequential to parallel optimization engines. By providing sequential implementations users obtain parallel implementations.

  • Cooperation between engines makes possible to provide more powerful hybrid engines.

  • Ready to use on commodity machines: Clusters of PCs under Linux are currently supported.

  • Flexible and extensible software architecture. New skeletons can easily be added, alternative communication layers can be used, etc.


In MALLBA, each resolution method is encapsulated into a skeleton. At present, the following skeletons for exact techniques are available: Divide and Conquer (DC), Branch and Bound (BnB) and Dynamic Programming (DP). Also the following skeletons for heuristic techniques are available: Hill Climbing, Metropolis, Simulated Annealing (SA), Tabu Search (TS) and Genetic Algorithms (GA). Moreover hybrid techniques have been implemented combining the previous skeletons, e.g., GA+TS, GA+SA, BnB+SA.


Goals

The goal of this project is to design, to implement and to evaluate a library of algorithmic skeletons for solving combinatorial optimisation problems. A skeleton is a generic tool that allows to define a concrete optimisation problem by creating instances of the general optimisation method that it implements. Three methods for solving problems of this area will be supported: exact methods, heuristic methods and hybrid methods. The library will offer three different implementations: sequential, locally distributed (LAN) and geographically distributed (WAN). The geographic platform that will be used to develop and evaluate this library will include the three heterogeneous networks of personal computers located at the three participant sites: Barcelona, La Laguna (Tenerife Island) and Málaga.

The library will offer to the users a unique interface for every algorithmic skeleton, independently from the platform. The final user will just chose one of the three methods of resolution and he will particularize the skeleton with the features that define his problem, but without taking care of those aspects related to the method itself or to platform-dependent implementation (e.g, users do not need to have any knowledge about parallelism, but they will obtain all the benefits of distributed computation -- LAN and WAN -- just from their sequential instantiations of skeletons).

The WAN computation will allow to solve problems in a geographically distributed environment. That represents and important computation power because computers that are in other sites (not only in our own local network) can be used to compute part of a problem. This remote computers could be accessed because of the platform provided by Internet.

The different resolution methods that we plan to cover in this project are divided into the three participant sites: the research team from La Laguna works on the Exact methods, the team from Málaga works on Hybrid methods and the research team from Barcelona works on Heuristic methods. The initial schedule for the three years of the project was done according to the different implementations of the library: the sequential implementation at the first year, the locally distributed (LAN) implementation at the second year, and the geographically distributed (WAN) implementation is planned for the third year.


Relations with other projects and companies

ALGGEN

The Algorithmic and Genetics Group of the LSI Department (UPC) is dedicated to research and teaching in the area of Computational Biology and BioInformatics. The research projects are developed jointly in collaboration with "in lab" research groups in genetics of other centers. The aim is the design of software tools that allow them to work "in silico" and also the development of software tools to analyse the genome “in silico'' in collaboration with "in lab" research groups in genetics.

The Internet site (http://www.lsi.upc.es/~alggen) is the virtual laboratory and contains the tools that have being designed both for teach and research purposes. The on-line BioInformatics tools provided at the Internet site run over the machines of the MALLBA cluster and they allow to solve any problem introduced at the web page. Until now ALGGEN have collaborative projects with:


GRAFCAN

Cartográfica de Canarias (http://www.grafcan.rcanaria.es). We are working on the problems that they exposed to the Consejería de Medio Ambiente of the Canary government about the study and protection of local species. The Islands are divided into a grid of 500 m2 squares and the richness and expenses of each square are well known by biologists. An assignment is wanted that maximizes the number of protected species constrained to the money available.


ICID

Instituto Canario de Investigación y Desarrollo (http://www.rcanaria.es/icid). We have collaborated together to measure network features among the canary islands (see http://nereida.deioc.ull.es/~cicyt/analisis_de_rendimiento).


IAC

Instituto Astrofísico de Canarias (http://www.iac.es). The tool developed for the two polarimeters Stokes of the solar telescope from the observatories of Tenerife and La Palma is being adapted, in order to allow the computation of every point in the beowulf associated to this project.


TECNATOM, S.A.

This company wants to use the MALLBA library to solve their combinatorial optimisation problems. They have helped to measure the parameters of the WAN connection with the Universidad de Málaga, in order to obtain statistics of this area of the network.


AUREN

This company is interested in using the Genetic Algorithms developed in the MALLBA project to solve vehicle routing problems. The aim of the work performed is to decide the routes that vehicles must follow taking into account some load and time constraints. This kind of problems can be modelled and solved in the context of the MALLBA project. This work has been described as a PROFIT proposal.



People interested in MALLBA

The version 1.0 of the MALLBA library is not public yet, but some research groups from some foreign Universities have shown to be interested on it. They knew about the library because of the Internet site but also because of the research articles we have presented on conferences and invited talks. The aim is to obtain some feedback from them in order to check the real usefulness of the library. Before getting in touch with these customers we were the only users of the library and that is not good for a real evaluation of the product.

Customers have to fill up a license agreement before getting any code of the library. The purpose of this license is to enable the use of MALLBA code for academic, research, development and demonstration purposes only. It is not permitted the use of MALLBA for any commercial or military purpose. Other constraints for the right use of the MALLBA code are specified in this license, such as the responsibility of using MALLBA library personally and the obligation of referencing it where it is used. The license form can be found in the web page of the project. We are waiting now for seven more possible customers to send us back the license agreement.


mallbalsi.upc.es