Table 1: Comparison of our TSKTree with JLTS (Jörnsten and Løkketangen) implementation.
M. Josep Blesa - Fatos Xhafa
Departament de LSI
Universitat Politècnica de Catalunya
Campus Nord, Mòdul C6
Jordi Girona, 1-3
08034-Barcelona, Spain.
E-mail: {mjblesa,fatos}@lsi.upc.es
Keywords: k-Cardinality Tree, Tabu
Search, Generic Programming, Reuse, Components.
Classification: 1 year´s work (PhD)
1 Introduction
Generic programming and reuse of components have already proved very important to the software process in general. There is an increasing interest to these topics even from the area of combinatorial optimization, where the researchers tends to use ad hoc implementations for the problems; this interest can be understood from the advantages of the generic programming and reuse of components such as time savings, flexibility, robustness etc. In combinatorial optimization we are oftenly found with methods for sub-optimally solving optimization problems. In this work we concern, the Tabu Search method, a well-known meta-heuristic [2] that has proved successful in sub-optimally solving a whole bunch of optimization problems. The ingredients of such method are the same for any problem to which one would like to apply the method. It is, therefore, quite interesting to have a generic program or a kind of template for Tabu Search from which one could derive instantiations for any problem of interest. This approach have been considered in our recent work [1] where we give a skeleton for the Tabu Search method implemented in C++. Here we show how to obtain an implementation of Tabu Search method for a concrete problem, namely the k-Cardinality Tree based on the generic skeleton for Tabu Search and component reuse.
The k-Cardinality Tree Problem consists in finding, in a given undirected weighted graph, a subtree of minimal weight with k edges, introduced by Hamacher et al. [3] and it is important to both theory and industrial applications (oil field leasing, layouts, partitioning, telecommunications and matrix decomposition.) Among several heuristics applied to the problem, there is also the Tabu Search method applied to k-Cardinality Tree by Jörnsten and Løkketangen [4].
2 Our results
In this work we give a new implementation of the Tabu Search method for the k-Cardinality Tree. One can naturally ask why this new implementation? Our main motivations were, first, to obtain a new implementation with as little effort as possible, and, second, we wanted our implementation be flexible, so we could easily change several parts of the implementation without affecting the implementation as a whole. We remark that the requirement on the flexibility is very important in the context of Tabu Search method since several ingredients of the method can be implemented in different ways. In order to match these requirements, we address an implementation for the problem based on the generic skeleton for the Tabu Search method and component reuse. By instantiating the k-Cardinality Tree, we have observed the easy of use of the skeleton, the flexibility, robustness and considerable savings in time. It is generally believed that an efficient implementation of TS should incorporate as much knowledge of the problem as possible. In spite of this we show that our implementation even though obtained through a generic skeleton, matches the results of the specific implementation (Jörnsten and Løkketangen, 1997).
The Design of the Tabu Search Skeleton was done after a careful review of known implementations for the method. The basic ingredients of the method are introduced into C++ classes according to a logical definition in the context of the Tabu Search method. The basic idea behind the skeleton is to allow the user to instantiate any combinatorial problem of interest by only defining the most important problem-dependent features. Elements related to the inner algorithmic functionality of the method are hidden to the user. The classes forming the skeleton are divided into a public and a private part. The private part contains elements related to the inner functionality of the TS method, and the public part contains elements related to the problem-dependent part. The public part must be completed by the user, so after filling the problem-dependent features, the problem can be solved using the Tabu Search method. The generality of our skeleton runs in two directions: the TS skeleton permits the user to instantiate any problem of interest by simply filling in the public part and the skeleton itself is generic enough to solve any problem if its problem-dependent elements can be described.
Reusable Components. Although the general idea of the Tabu Search algorithm is well known some details remain unstandardized, for instance the intensification and diversification of the search. In the literature both are freely introduced ad hoc to the schema depending on the problem to solved; that leads to subtlety different TS algorithms. Because we wanted a unique generic and powerful enough form of the Tabu Search algorithm, we introduced these functionalities to the basic Tabu Search. The private part of TS skeleton implements the generic Tabu Search algorithm and it is completely reusable for all the instantiations. In a certain sense, the main procedure is the most important reusable component of our approach. Other reusable components are the Statistics (useful statistics), State (information on the state of algorithm), TabuList (efficient use of memory). The instantiation of a concrete problem is done by completing the public part (by implementing what the problem is, how is a solution, what is a move, etc.) Some of these definitions can be reused from other instantiations, e.g. both the k-Cardinality Tree and the Traveling Salesman are represented by an undirected weighted graph, so in this case, the class representing the problem can be reused.
Different implementations for the problem can also be generated by varying some definitions and structures from an already implemented version e.g. by changing the Tabu List structure, the intensification and/or the diversification strategy etc. The user has to just redefine a couple of methods in a class. So we have two levels of re-usability: in the method itself and in the instantiations. The re-usability of the method is due to the standardization of the Tabu Search algorithm. The second level refers to the instantiations already done.
Experimental Results. Table 1 resumes some of results obtained by our TSKtree instantiation with the ones obtained by the implementation of [4]. The instance name gxx-4-yy means graphs of xx vertices and yy indicates the index of the instance (we generated and proved different instances of the same configuration).
Table 1: Comparison of our TSKTree with JLTS (Jörnsten and
Løkketangen) implementation.
3 Conclusions
We present a C++ implementation of Tabu Search method for the Minimum k-Cardinality Tree problem. Tabu Search method is a well known heuristic for sub-optimally solving optimization problems. This method is also applicable to Minimum k-Cardinality Tree -an important problem to both theory and industrial applications. Our implementation is based on generic programming and re-usability of several components for Tabu Search method. We have compared our program with other ad hoc implementations for the problem and have observed a good performance of our implementation. Moreover, our implementation represents time savings, flexibility and robustness mainly due to the component reuse.
Acknowledgment
We thank the Barcelona Team of Mallba Project for support while conducting this research. We are grateful to A. Løkketangen, M. Ehrgott and H. Hamacher for providing us with their benchmarks and executable codes for k-Cardinality Tree.
Research partially supported by the ALCOM-FT (IST-99-14186) and CICYT Proj. TIC1999-0754-C03.