Blesa, M.; Hernàndez, L.; Xhafa, F. IEEE International Conference on Parallel and Distributes Systems p. 23-28 DOI: 10.1109/ICPADS.2001.934797 Data de presentació: 2001-06 Presentació treball a congrés
Problems arising in different areas such as numerical methods,
simulation or optimization can be efficiently solved by parallel super-computing. However, it is not always possible to buy and maintain parallel super-computers. A geographically distributed network of PC clusters is an interesting low-cost alternative. The possibility of connecting different clusters of PCs through Internet opens a new approach to distributed and massive computing. The MALLBA project tackles the resolution of combinatorial optimization problems using algorithmic skeletons implemented in CPP under this approach. MALLBA offers three families of generic resolution methods: exact, heuristic and hybrid. Moreover, for each resolution method it offers three implementations: sequential, LAN and WAN. This paper surveys the current state of the MALLBA project.
In this paper we present two parallel skeletons for Tabu Search method -- a well known meta-heuristic for approximately solving combinatorial optimization problems. Our parallel skeletons are designed and
implemented using the generic parallel programming paradigm. The first
skeleton is based on independent runs model with search strategies
while the second is a master-slave model with neighborhood
partition. Our starting point to obtain these skeletons was the design
and implementation of a sequential skeleton that was used later as
basis for the two parallel skeletons. Both skeletons provide the user
with the followings: (a) permit to obtain parallel implementations of
tabu search method for concrete combinatorial optimization problems
from existing sequential implementations; (b) there is no need for the
user to know neither parallel programming nor communication libraries;
(c) the parallel implementation for a concrete problem is obtained
automatically from the existing sequential implementation of the
problem. The skeletons are implemented in C++ using MPI as a
communication library and offer several properties such as a
genericity, flexibility, component reuse, robustness and time savings,
mainly due to the generic and object oriented programming
paradigms. We have instantiated the two skeletons for the 0-1
Multidimensional Knapsack problem and report extensive experimental
In this paper we present a memetic algorithm for the minimum weighted
k-cardinality tree subgraph problem.
This problem consists in finding, in a given undirected weighted graph
G=(V,E,W), a tree T of k edges having
minimal total weight among all of k-trees that are subgraphs of G. This
problem was first described by Hamacher,
Jornsten, and Maffioli (1991) who also proved to be strongly NP-hard.
Given this observation, researchers have
focused on heuristic and metaheuristic algorithms to find suboptimal
feasible solutions for the problem, as a good way
to cope with most practical setting applications.
To our knowledge, no memetic algorithm (MA) has yet been reported for
this problem. It is known that some MAs have
a good synergy with Tabu Search when they use it as individual steps
for diversification and local optimization by the agents.
As a consequence, one of our main motivations was to obtain a new
implementation of an MA to the problem using an
existing implementation of Tabu Search to the problem (Blesa and Xhafa,
2000). We are currently implementing the