Generic parallel implementations for Tabu Search

Generic Parallel Implementations for Tabu Search Maria J. Blesa, Jordi Petit, Fatos Xhafa Report LSI–05–50–R 16th November 2005 2 Generic Parallel Implementations for Tabu Search∗ Maria Blesa†Jordi Petit Fatos Xhafa albcom Research group Departament de Llenguatges i Sistemes Inform`atics Universitat Polit`ecnica de Catalunya Ω building Campus Nord, E-08034 Barcelona, Spain {mjblesa,jpetit,fatos}@lsi.upc.edu Abstract Tabu Search (TS) is a meta-heuristic for solving combinatorial optimization problems. A review of existing implementations for TS reveals that, on the one hand, these implementations are ad hoc and, on the other hand, most of them run in a sequential setting. Indeed, the reported parallel implementations are few as compared to the sequential implementations. Due to increase in computing resources, especially in LAN environments, it is quite desirable to obtain parallel implementations of TS for solving problems arising in fields others than computer science, such as biology, control theory, etc., in which researchers and practitioners are less familiar with parallel programming. In this work we present a generic implementation of TS able to be run in sequential and parallel settings. The key point in our approach is the design and implementation in C++ of an algorithmic skeleton for TS embedding its main flow as well as several parallel implementations for the method. This is achieved through a separation of concerns: elements related to TS are provided by the skeleton, whereas the problem-dependent elements are expected to be provided by the user according to a fixed interface using purely sequential constructs. Thus, the skeleton has a unique interface but is expected to have many instantiations for concrete problems, all of them being able to run in a straightforward way using different parallel implementations. In order to assess the effectiveness of our approach, we have applied it to several NP-hard combinatorial optimization problems. We have considered developing time, flexibility and easiness of use, quality of solutions and computation efficiency. We have observed that our approach allows fast developing of problem instantiations. Moreover, the skeleton allows the user to configure and implement in different ways internal methods related to TS. Furthermore, the results obtained by our generic parallel implementations are efficient and report good quality results compared to the ones reported by ad hoc implementations. We exemplify our approach through the application to the 0–1 Multidimensional Knapsack problem. The experimental results obtained for standard benchmarks of this problem show that, in spite of the genericity and flexibility of our implementation, the resulting program provides high quality solutions very close to the optimal ones. Keywords. Combinatorial Optimization, Algorithmic skeletons, Tabu Search, 0 −1 Multidimensional Knapsack. ∗Work partially supported by the Spanish MCYT project TIC2002-04498-C05-02 (TRACER). At the time while research was conducted, M. Blesa was also supported by the Catalan Research Council of the Generalitat de Catalunya under grant no. 2001FI-00659. Preliminary versions of some parts of this work were presented at europar’02 ([1], Section 4), icpads’01 and ppam’01 ([4, 5], Sections 4 and 5). Those versions included introductory ideas and experiments on some of the models presented here. This paper extends the contents of those papers both in proposing new models, and in including more experimental results. Moreover, this work unifies all the set of generic parallel models thus providing a complete survey/overview for the reader. †Corresponding author 1 1 Introduction and motivation Many interesting combinatorial optimization problems are known to be NP-hard [19] and hence unlikely to be solvable within a reasonable amount of time. Heuristic methods have proved to be a good alternative to cope in practice with such problems [7]. One such method is Tabu Search (TS) introduced by F. Glover [21, 22]. TS has been applied to many combinatorial optimization problems such as scheduling [26, 41, 14, 32], graph problems [24, 6], resource allocations [35, 37], and layout problems [36, 17, 25] among others. After a careful revision of such implementations, we have observed that researchers and practitioners have applied TS to their problems through ad hoc implementations. This approach has, at least, two drawbacks. First, one has to implement the meta-heuristic from scratch for any new problem of interest and, second, even small changes in the code are not trivially introduced since this would require the modification of different parts of the implementation. These drawbacks are even more patent when trying to obtain parallel implementations. Some researchers have investigated how to parallelize TS. In one hand, parallelism permits practitioners to use more resources to obtain better solutions in reasonable computing time, and in the other, the experience shows that parallel versions of heuristics tend to yield more robust implementations than the sequential ones, in the sense that they perform well in most instances of the problem [12]. A taxonomy of parallel TS strategies is presented in [12] and, for meta-heuristics in a general context, fundamental ideas to design parallel strategies are found in [11]. Those ideas are applicable to a wide range of problems, yet the existing parallel implementations of TS for different problems [38, 16, 31] remain ad hoc. So, while it is almost clear how to exploit parallelism in TS in a generic way, practitioners tend to re-implement from the scratch the whole heuristic and its parallelization using specific knowledge of the problem at hand. The Generic Programming (GP) paradigm is a way to cope with these limitations. GP has turned out to be very useful to parallel programming [15, 13, 34, 20, 39, 23] in a manner that it allows good expressibility, reuse, and robustness yet maintaining efficiency. Combinatorial optimization is an area of applicability of this paradigm. Indeed, in combinatorial optimization we are often encountered with algorithms for sub-optimally solving a large number of optimization problems which apply in a similar manner to most of the problems they aim to solve. For instance, the main flow of TS applies similarly to any problem, and therefore it is quite interesting to have ageneric program or a skeleton for TS from which one could derive instantiations for any problem of interest. Moreover, it would be interesting to endow such a skeleton with capabilities to run in parallel setting. Furthermore, after years of research and development, parallel programming remains a difficult and specialized task. Yet, due to the increase in computing resources, especially in LAN environments, it is quite desirable to obtain reusable parallel implementations of meta-heuristics in general, and TS in particular, for solving problems arising in fields others than computer science, where researchers and practitioners are less familiar with parallel programming. Our main objective in this work is to present a generic implementation of TS that allows in a easy and flexible way to obtain sequential and parallel programs for different problems. To this end, in this paper we present the design, the implementation and the evaluation of an algorithmic skeleton for TS. Our skeleton is the result of an abstraction process leading to the separation of two concerns: elements proper to TS are provided by the skeleton, whereas the problem-dependent elements are expected to be provided by the user. The link between them is achieved through a fixed interface. The main flow of TS and different ways to parallelize it are implemented by the skeleton since, in a generic way, they are proper to the method. On the other hand, problem-dependent elements are specified by the skeleton. Their interface, as well as the user’s own instantiation of them, are described using purely sequential constructs. Thus, the skeleton has a unique interface but is expected to have many instantiations for concrete problems. Moreover, several parallel implementations are provided by the skeleton. We consider here the following parallel implementations for the TS skeleton: Independent Runs, Independent Runs with Autonomous Search Strategies, Master-Slave and Master-Slave with Neighborhood Partition. In order to assess the effectiveness of our approach, we have applied it to several NP-hard com- 2 Impl. n ... Impl. 1 Skeleton’s Interface Instantiation Skeleton Concrete problem Figure 1: Structure of an skeleton binatorial optimization problems: 0–1 Multidimensional Knapsack, k−Cardinality Tree, Max SAT, Max CUT, Resource Constrained Scheduling, Quadratic Assignment and Traveling Salesman. In this paper, we exemplify the approach through the application to 0–1 Multidimensional Knapsack problem. We consider developing time, flexibility and easiness of use, quality of solutions and computation efficiency. The paper is organized as follows. In Section 2 we give some preliminaries on basic concepts from combinatorial optimization and in Section 3 we overview the TS meta-heuristic. The TS skeleton is presented in Section 4 and the parallel models used in the skeleton are given in Section 5. The application of our approach to the 0–1 Multidimensional Knapsack problem is shown in Section 6. We end the paper in Section 7 with some conclusions. 2 Preliminaries on combinatorial optimization problems To describe more in detail how TS works, we need to introduce some definitions and notations concerning combinatorial optimization problems in general. A combinatorial optimization problem is defined as follows. Definition 1. A combinatorial optimization problem Π is a four-tuple (I,S, c, goal) where: –Iis the set of instances, –S(x) is the set of feasible solutions associated to any instance x∈ I, –cis a cost function that maps feasible solutions s∈ S(x) of a given instance xto values cx(s), referred to as the cost of the solution, –a goal: find a feasible solution that optimizes (maximizes, minimizes) the cost function. Given an instance xof a problem Π, the set S(x) of all feasible solutions is called the solution space. Solving a combinatorial optimization problem means to find a solution s∗∈ S(x) such that s∗has the best cost with respect to the cost function, i.e., cx(s∗)≤cx(s), for all sin S(x), in the minimization case and cx(s∗)≥cx(s), for all sin S(x), in the maximization case. Such a solution is called optimal for the given instance xof the problem Π. Hereafter, to simplify notation, we will refer only to the minimization case and denote by Sthe set of feasible solutions S(x). For many important combinatorial optimization problems, finding the optimal solution is computationally hard since the solution space of such problems is very big (grows exponentially in instance size). However, in many fields sub-optimal solutions, i.e. solutions whose cost is close to the optimum, might be satisfactory. Sub-optimal solutions are usually the best among a subset of feasible solutions, and are referred to as locally optimal solutions, in contrast to optimal solutions that are called globally optimal solutions. A simple way to visualize the property of locally versus globally optimal solutions is through the graphical representation of the landscape of the problem (see Fig. 2). In such a graphical representation we can see different valleys corresponding to locally minimal solutions and at least one of them could also be a globally minimal solution. 3 Figure 2: Different landscapes of continuous functions In order to formally define locally minimal solutions, a neighborhood structure is introduced, which allows to view locally minimal solutions as those which fulfill the minimization criterion at least with respect to their neighborhood. Definition 2. Aneighborhood structure is a function N:S → 2Sthat assigns to every solution s∈ S a set of solutions N(s)⊆ S.N(s) is called the neighborhood of sand the solutions s0∈ N(s) are called neighbors of s. Then, a locally minimal solution is defined as follows. Definition 3. A solution ˆs∈ S is a local minimum with respect to a neighborhood structure N if the cost function is minimized for ˆs, i.e., if for all sin N(ˆs) it holds that c(ˆs)≤c(s). Note that for a given problem many different neighborhood structures can be defined. Usually, the definition of the neighborhood takes into account the combinatorial structure of solutions. In this sense, we can see the neighbors of a solution as those solutions that differ slightly from the given solution. These small changes are usually known as local perturbations and are interpreted as movements. Definition 4. Amovement m:S → S is a mapping from one solution s∈ S to another solution s0∈ S. Note that having the definition of a movement mwe can define a neighborhood structure as follows: N(s) = {s0|s0∈ S, m(s) = s0}. Local search methods use movements to explore the solution space by iteratively jumping from a feasible solution to another one. Depending on how the neighborhood is defined and which additional strategies are used to guide the search, different families of local search methods can be defined. For an overview of local search methods see [29]. 3 The Tabu Search meta-heuristic Heuristic methods have turned out to be a standard approach in combinatorial optimization. Dealing in practice with real size problems makes the use of such methods the de facto choice. Tabu Search (TS) was formally introduced by F. Glover [21, 22]. As it happens with other heuristics such as Simulated Annealing, Genetic and Evolutionary Algorithms, TS has a clear link with real life experiences and behaviors. Indeed, TS adopts the traditional usage of the “tabu” word meaning prohibition imposed by social custom as a protective measure. This adoption has the following senses: (a) Some actions must be tabu since allowing them might be risky; (b) Some actions might be allowed in spite of being tabu; (c) Tabu actions are memorized, i.e., the search should keep track of the trajectories followed in the solution space and learn from the experience so that the search could be effective; and (d) The search should also benefit from exploring new promising regions of solutions space. TS method tries to incorporate all these observations through different mechanisms in a way that allows an effective search that together with its flexibility can beat many classical memoryless methods and obtain a remarkable efficiency on several problems. 4 High level description. TS starts from an initial solution and proceeds iteratively from a solution sto another one s0∈ N∗(s), where N∗(s) denotes a reduced neighborhood, N∗(s)⊆ N(s). The search proceeds until a termination condition is met. There are different ways to define the reduced neighborhood N∗(s), for instance, by labelling the recently visited solutions as tabu and storing them in a tabu list L. This constitutes the short term memory or recency. Then, in a given iteration, N∗(s) is computed as N(s)\L. Note that by forbidding solutions that are already visited, N∗(s) contributes to avoid cycling, though there is no guarantee that cycling will not occur. In order to maintain the tabu list in a reasonable size, the tabu status of solutions in Lis canceled after a certain number of iterations. It is important to note here that although we speak of a list of tabu solutions, a tabu solution refers to the tabu movement that leads to that solution. The tabu status of a movement is canceled also in exceptional conditions, known as aspiration criteria. Based on its historical memory, the algorithm may decide to activate appropriately two mechanisms: intensification and diversification. The intensification is intended to explore more thoroughly the immediate neighborhoods of the current solution. It may happen, however, that during the search the algorithm gets stuck into a local optimum while there might still be interesting regions of solution space to be explored. In such a case the algorithm activates the diversification mechanism. See Fig. 3 for an intuitive idea of the effect of these two mechanisms. We proceed now to explain in more detail the main entities used in the TS meta-heuristic and then give its main flow. The initial solution. This is the starting point of the search and is usually constructed either at random or by a greedy procedure. The neighborhood/movement. The definition of the reduced neighborhood N∗(s) of a solution sis crucial. Such a definition is done through the entity movement that is usually defined and implemented in terms of attributes of a solution. TS has to define and manage efficiently the movement entity and functionalities related to it such as “apply a movement to a solution”, “compute the inverse movement”, “give tabu status to a movement”, etc. Note that there can be multiple types of movements whose application leads to neighborhoods dynamically changing and covering different regions of the solution space. Memory types and tabu criteria. TS maintains historical information of the exploration process through a short term memory and a long term memory. –A short term memory or recency is used to maintain information on recently visited solutions, usually by storing values of pre-selected attributes of such solutions and labelling them as tabu. One way of doing this is by considering as pre-selected attributes those forming the movement, hence, such a movement is labelled tabu and cannot be applied, unless it satisfies certain conditions. Note, however, that a movement might include attributes that are not pre-selected, so it will be labelled tabu if it contains some tabu attribute. Using the tabu attributes and tabu movements the algorithm reduces the neighborhood: solutions that contain tabu attributes or combinations of them in form of movements do not belong to N∗(s). –A long term memory or frequency is used to maintain historical information on the exploration process. The objective now is to identify elements that are common to good solutions. This is done either by storing attributes appearing frequently in good solutions or by recording complete solutions (elite solutions), say, solutions whose cost is below a threshold. The long term memory is used to activate the intensification and diversification strategies. The intensification. The purpose of this procedure is to explore in depth certain regions of the solution space if there were evidence that such regions may contain good solutions. To this end, the procedure tries to insert good attributes to the newly generated solutions. This is done by 5 objective function solution space ˆs1 intensify objective function solution space ˆs ˆ s0 s0 diversify LS Figure 3: Intensification (left) and diversification (right) effects. generating movements with attributes from those recorded in the frequency or from elite solutions and applying them through the standard movement mechanism. Another way to accomplish this is through rewarding attributes of the solution that are in the frequency and thus “forcing” these attributes to appear in the newly generated solutions. The diversification. This procedure is intended as a mechanism to escape from local optima and to ensure that the algorithm will explore new regions of the solution space. Again, this is done using the frequency but now the attributes not frequently used are chosen. As in the case of intensification, it can also be done by penalizing attributes of the solution that are in the frequency and thus “forcing” these attributes to not appear in the newly generated solutions. We refer to this kind of diversification as “soft” diversification since it allows to move the search to neighborhoods close to the current one. Another (more abrupt) way to diversify is to re-launch the search at a new point in the solution space; we refer to this kind of diversification as “hard” diversification. The aspiration criteria. This is a set of conditions to verify whether the tabu status of a movement can be canceled allowing thus its application. One such example is the improve-best aspiration criteria: if applying the tabu movement to the current solution leads to a better solution than the best one so far, then the tabu status of the movement is canceled. The stopping condition. At each iteration, the stopping condition is evaluated. Usually, the stopping condition is a compound of different conditions: some of them related to TS, such as “during the exploration process, an empty N∗(s) is found”, some others are related to pragmatical issues such as “the total number of iterations or the execution time is completed.” We conclude this section presenting the main procedure of TS in Algorithm 1. We can easily observe that the main procedure yields to the concept of the generic algorithm since it applies independently of the problem being solved; knowledge specific to the problem is needed only in implementing methods and entities used as black boxes in the main procedure. 4 The Tabu Search Skeleton We present now the TS skeleton for the TS meta-heuristic described in the previous section. 4.1 Design of skeletons for generic algorithms Our design for the TS skeleton follows the mallba approach described in [1]. This approach has been successfully used in the design of several other generic algorithms for combinatorial optimization such as Divide and Conquer, Dynamic Programming, Simulated Annealing, Memetic Algorithms and others [27]. 6 Algorithm 1 : Pseudo code for Tabu Search Input: A problem instance and setup parameters Output: A sub-optimal solution ˆs Compute an initial solution s∈ S and ˆs←s. Reset the tabu and aspiration conditions. while not stopping condition do Generate a subset N∗(s)⊆ N (s) of solutions such that, either none of the tabu conditions is violated or the aspiration criteria holds. Choose the best s0∈ N ∗(s) with respect to the cost function c. s←s0. if c(s0)< c(ˆs)then ˆs←s0. end if Update the recency and frequency. if intensification condition then Perform intensification procedure. end if if diversification condition then Perform diversification procedure. end if end while Return ˆs. Algorithmic skeletons were formally introduced by M. Cole [9]. His idea was to capture common patterns of parallel computation, such as divide and conquer or pipelining, in higher-order functions. These patterns can then be instantiated by the programmer to suit a particular algorithm. The approach has the advantage of restricting parallelism to a small, easily isolated part of the program. The basic idea behind this is to not require the user to know any issue regarding parallelism. Rather, it is the implementation written by the skeleton developer that is aware of the possible ways to parallelize the execution. In fact, the same skeleton can be used for different architectures: it is only necessary to change the implementation of the skeleton in order to change the program’s behavior, its instantiation itself is unchanged. In the mallba approach, skeletons are targeted towards combinatorial optimization methods rather than towards basic parallel patterns. Also, rather than using functional languages, the skeleton’s interface and its instantiation are described with purely sequential C++ constructs. The parallel constructs are hidden in the different implementations of the skeleton. This organization allows the user to instantiate any problem of his choice by only defining the concrete problemdependent features that depend on the problem he has in mind using a widely available object oriented language. Abstract elements related to the inner algorithmic functionality of the method and its parallelization are hidden to him. In order to design a skeleton for a given generic algorithm, one must first identify its basic abstract entities and functionalities. Then, one must describe their corresponding abstractions into C++ elements: classes and functions. These elements can be classified according to their “availability”: Elements implementing inner functionalities of the generic algorithm (e.g. its main flow) are completely provided by the skeleton, whereas elements whose behavior is problem specific are required to be implemented by the user. Therefore, we classify these elements into two groups: provided and required. –Provided elements: Provided classes and functions implement the generic algorithm itself. These may include the solvers that fix the main flow of execution as well as helper classes needed to get the state of the process or to setup some of its parameters. –Required elements: Required classes and functions represent the entities and functionalities involved in the generic algorithm whose implementation depends on the specific problem 7 each slave processor explores the neighborhood by its own and comes up with its best movement. Clearly, the task of exploring the neighborhood in parallel makes sense as far as the neighborhood exploration is not deterministic. This model is achieved in the skeleton through the perform_one_phase() method defined in the Solver class and the chose_best_move() method required in the skeleton. The master processor runs the main flow of TS through the perform_one_phase() method and each slave processor executes, upon receiving the current solution (actually the current movement to be applied to the solution), the chose_best_move() method. Note that in this implementation we exploit a fine grain parallelism. Master Slave with Neighborhood Partition. The Master Slave with Neighborhood Partition model (MSNP) is derived from the MS model by specifying the type of the task accomplished by the slave processors. In contrast to the MS, in this model each processor explores just a portion of the neighborhood. Thus, through this model, we can reduce the time needed to perform a complete neighborhood exploration. Note that in this case the neighborhood exploration can be deterministic. This model is managed in the skeleton through the perform_one_phase() method defined in the Solver class and choose_best_move_from_partition() method required in the skeleton. The master processor runs the main flow of TS through the perform_one_phase() method and each slave processor executes, upon receiving the current solution (actually the current movement to be applied to the solution) and its partition, the choose_best_move_from_partition() method. As for the partition the master processor uses the size() and operator[] methods defined in the Solution class in order to partition the solution into as many (roughly equally) parts Si as slave processors there are, and sends them to the slave processors. Then, the i-th slave processor uses Sito explore the portion of the neighborhood through movements constructed with attributes from Siand Saccording to the implementation of the choose_best_move_from_partition() method. Other implementation issues. Our design has paid special attention to the independence of the implementation from the chosen communication library as well as the efficiency of the implementation. To do so, we have implemented high level primitives for sending/receiving that are used as black boxes by the skeleton. Thus, the skeleton implementation will not be affected if we use, say, PVM instead of MPI except for we have to implement the primitives for the desired communication library. The current implementation is done using MPI. Regarding the efficiency of the implementations, we have tried to minimize the communication time, especially in the MS models. More precisely, in the implementation of the IRAS model, instead of using the generate_strategy() method by the coordinator processor to generate and send strategies to the slaves, each slave runs the method in order to generate its own strategy. This is possible due to the non-deterministic implementation of the method. Indeed, the initial solution is computed by set_initial() method of the class solution and then is perturbed using the perturb_randomly() method while the rest of tabu search parameters are randomly chosen in intervals of values specified by parameters given by the user. In the case of MS implementations, the efficiency of communications between the master processor and the slaves is even more crucial since the task performed by the slaves, that is, the neighborhood exploration is very frequent. To reduce the communication time, the master processor sends to the slave processors the initial solution and for the rest of phases just sends them the best resulting movement. This yields in increase of efficiency since solutions can be huge structures (e.g., a tree of thousands of edges) while movements contain few information (e.g., two edges to be swapped). 6 Case example: the 0–1 Multidimensional Knapsack We have applied our approach to several combinatorial optimization problems as to assess its effectiveness. We exemplify the approach through the application to the 0–1 Multidimensional 14 Knapsack (0–1mknp) through which we also show that our approach allows a fast developing as well as transparent access for the user to parallel executions. We present some experimental results both on sequential and parallel settings. 6.1 Problem statement The 0–1mknp problem consists in selecting a subset of ngiven items in such a way that the total profit of the selected items is maximized while knapsack constraints are satisfied. More formally, the problem can be stated as max n P j=1 cj·xj subject to n P j=1 Ai,j ·xj≤bi, i = 1,...,m xj∈ {0,1}, j = 1,...,n (1) where cj∈N,Ai,j ∈Nand bj∈N. Each cjis the profit associated to the item j. The components xjare decision variables: xj= 1 if the item jis selected and xj= 0 otherwise. Each of the m knapsack constraints Pn j=1 Ai,j ·xj≤bi, i = 1,...,m, specifies a dimension of the knapsack. The special case of the 0–1mknp with m= 1 is the classical knapsack problem. 6.2 Instantiating the TS skeleton for the 0–1 MKNP problem In this section, we exemplify how the TS skeleton can be instantiated for solving the 0–1mknp problem. We will highlight the main steps in the instantiation of the TS skeleton from the point of view of a final user. As introduced in Sec. 4, when instantiating the TS skeleton for a concrete problem the user has to complete the interface (in the .hh file) by defining the data types that implements the main entities represented in the required classes. Then, methods of the required classes must be implemented (in the .req.cc file) according to the chosen representation. We explain the main data structures and some of the most relevant methods of each required class in the proposed instantiation. See Appendix A for more details. Instantiating the Problem required class. We choose a representation for the benefits, for the capacities and for the constraint matrix. The former are implemented by two arrays of integers, while the latter is implemented by a two-dimensional array. Since the 0–1mknp is a maximization problem, the direction() method returns maximization. Instantiating the Solution required class. A feasible solution is represented by an array contents of binary values (the type of the solution components), in which the i-th position indicates if the i-th item is included in the knapsack or not (what the operator[] returns).1An initial feasible solution can be constructed in many different ways; for instance, in a greedy way by trying to insert into the knapsack as many items as possible with as greater benefits as possible. The cost associated to a solution is the sum of the benefits of the items included in the knapsack. This evaluation will be done many times during the search process; thus, it is desirable to have a faster way of evaluating a solution. Since every intermediate solution in the search process is obtained by the application of a movement to the previous solution, the corresponding cost can also be computed incrementally more efficiently by considering how the cost variates when applying the movement. The delta() method does this. The apply() method is implemented by marking in the movement which items have to be dropped from the knapsack, and those to be added. On the other hand, the unapply() method implements how the previous solution can be recovered from the current one. 1Moreover, every solution keeps a reference to the Problem class, because information concerning the constraints, capacities and benefits of the items is needed. 15 The best solutions found during the search process are used as a long-term memory and kept in the class TabuStorage. The items of the best solutions are used in the intensification and diversification processes (see Sec. 3). By rewarding an item j, its original benefit cjis increased and the item will be more attractive to be kept as part of future solutions. In this way, the item is less susceptible to be chosen as a candidate to be dropped from the knapsack when moving through the neighborhoods. Similarly, we can reinforce this effect by also making less attractive (decreasing the benefit) those items which were rarely belonging to good solutions. Soft diversification is done by studying the history of the items in the last explored solutions via the information in the history array (in the TabuStorage class) and the history_rep setup parameter. With this information, the rep value is calculated and used as a threshold for deciding whether an item has been very frequently used or not. Those items which are in the current solution and belonged more than rep times to the last visited solutions, are dropped from the current solution. Furthermore, those items which appeared in the last visited solution less than rep times, are incorporated to the current solution (if no capacity constraint is violated). The soft diversification process is implemented in the penalize() method. After nb_diversifications iterations, the soft diversification finishes. Note that the item benefits are not modified, so the unpenalize() method does not need implementation. The strong diversification is implemented in the escape() method. A new initial solution is constructed similarly as in the initial_solution() method but randomly deciding, for each item, whether it is included or not in the knapsack.2The search process is re-launched from this new starting point. Instantiating the Movement required class. A movement is defined as a set of items that are dropped from the current contents of the knapsack, together with a set of new items to be added. The items to be dropped are selected according to the saturation of the different dimensions of the knapsack. The items with the lowest benefit of the most saturated dimensions are candidates to be dropped. A candidate should not be tabu, because intuitively that would mean that it was inserted recently. The items to be added are selected according to the benefit they would produce. Those with greater benefit and not belonging to the current knapsack configuration are candidates to be added. The capacities of the knapsack must also be controlled and updated accordingly. Such a movement can be represented with an array of integers (each integer is the index of an item in the knapsack) and two integer values indicating the number of items to be dropped and the number of items to be added. To construct this type of movements and their further management, we use the methods in the class and, for the sake of efficiency and modularity of the instantiation, we introduce two additional ones: the can_apply() method and the belong() method. Note that this is possible in our skeleton since these methods are used only in this required class and the rest of the classes do not need to be aware of them. The can_apply() method, which keeps track of the fact that a given item has to be added/dropped in the movement, is implemented by always filling the array first with the items that have to be dropped (at the nb_drop lowest positions of the array), and then the items that have to be added (at the nb_add last positions of the array). On the other side, the belong() method checks if a given item has already been considered in the movement. In this instantiation, the generate() and invert() methods do not need to be implemented, since the movement is generated item by item through consecutive applications of the can_apply() method. Instantiating the TabuStorage required class. In order to deal efficiently with the historic information of the search process, we use the following data structures: –A tabu list tl implemented as an array of size n. The j-th component stores the number of iteration where the j-th item is made tabu. This is used in the whole search process since it represents the short-term memory. 2This indeterminism reduces significantly the probability that the new search path starts with the same initial solution as the one produced by the greedy procedure implemented in method initial_solution(). 16 –Ahistory array of size nin which the j-th component stores the number of iterations that the j-th item has been included in the knapsack. This is used in the soft diversification. –Abest_solutions array maintaining the nb_best_sols solutions of best benefits found so far. This information is used in the intensification. This additional treatment of the history of the search process is aimed to provide good intensification and diversification effects, but it requires some extra parameters in the TabuStorage class. An example is the parameter nb_best_sols mentioned above, which specifies the maximum number of best solutions to store and becomes the dimension of the array best_solutions. Another parameter, namely history_rep, is included to decide whether an item has been incorporated many times or not into the solutions during the search. In addition to these parameters, other internal structures are needed to store and compute secondary data (e.g., item_frequencies). The management of the tabu movements is simple. When a movement is made tabu, each of its items is included in the tabu list with a “time-stamp” recording the last time that this item was considered (added or dropped). The information in history also has to be properly updated any time a movement is made tabu. The update_best_sols() internal method checks whether the solution obtained by applying the movement that is actually made tabu, has to be stored in best_solutions. A movement is tabu (see is_tabu() method) if any of its items have been in the tabu list during more than tabu_size iterations. The items in the movement to be added are checked first. Exploring the neighborhood. With the aim of testing the flexibility of our approach, we have tried two different strategies for the exploration of the neighborhood. This can be done just by providing two different implementations for the (required) choose_best_move() method. (a) In the direct exploration of the neighborhood, the set of items to be dropped from the knapsack is selected first, and then, the space left by the dropped items is used to add new items. The selection of the items to be dropped is described in Algorithm 2 (see Appendix A.5). To check the capacity constraints, the algorithm uses a vector br0(which initially is a copy of br) that contains the variations in the capacity due to the items that are added and dropped. At every iteration, the algorithm determines in which dimension the knapsack is saturated the most (i.e., the argument i∗minimizing the remaining capacity br0[i].) Then, in this dimension, the item with the worst relation between its benefit and its cost will be candidate to be dropped, provided it is not tabu. In case all the items in the knapsack are tabu, an item is selected according to the aspiration criteria. However, if the knapsack becomes empty, the search is interrupted and the number of items is set to one; thus, at least one item will always be removed from the knapsack. The selection of the items to be added is done iteratively according to Algorithm 3 (see Appendix A.5). The candidate items to be considered cannot be already included in the current configuration of the knapsack and cannot be tabu. From those candidates the algorithm will choose, at each iteration, the item providing the higher benefit that does not violate the capacity constraints. When an item l∗is chosen to be added to the movement, the vector br0is updated by decreasing the free capacity at each dimension according to the cost of the item at that dimension. In case the element l∗is tabu, the aspiration criteria decides whether the item is added or not. (b) The combinatorial exploration of the neighborhood allows to explore the neighborhood in order and more exhaustively. It differs from the direct exploration in two main points: first, the movements only imply a change in the state of one or two items of the knapsack, and second, the best movement is chosen among all those movements that can be generated combinatorially from two solution components, i.e., from two items, and that would lead to feasible solutions in the neighborhood of the current solution. A movement is here composed either by two items (k, l), one already in the knapsack and the other one not, which will exchange their state, or just by one item (k) not in the knapsack. From all the movements leading to feasible solutions, we select the one providing the greatest improvement in the fitness, which does not violate any of the constraints and is not tabu (or has aspiration, in case all of them are tabu). 17 This strategy is more expensive as compared to the direct exploration (quadratic time versus linear time of the direct exploration) due to the exhaustive generation of all the combinations of pairs of items. Running the instantiation. Once the implementation of all the required classes is completed in order to instantiate the 0–1mknp problem, we can run the skeleton in different settings, namely, sequential or parallel with the IR, IRAS, MS or MSNP models. To this aim, the user only needs to declare an object of the appropriate sub-class of the Solver class (i.e., Solver_Seq,Solver_IR, Solver_IRAS,Solver_MS or Solver_MSNP), and call the run method in it (see an example in Fig. 11.)    "TabuSearch-MKNP.hh" // header file of the instantiation   Main () {    skeleton TabuSearch; Problem pbl; cin >> pbl; // read the problem instance Setup params; cin >> params; // read the setup parameters Solver_IR solver(pbl,params); // select the IR solver solver.run(); // run the solver cout << solver.best_solution() << endl; // report the best solution found cout << solver.best_cost() << endl; // report its cost } Figure 11: Example to run the instantiation for the 0–1mknp problem in parallel using the IR model. 6.3 Experimental evaluation Measuring the performance of a meta-heuristic implementations requires testing on a large set of real size instances. Moreover, finding appropriate values for the search parameters of the metaheuristic is almost indispensable. We take profit of the advantages that parallelism offers us in terms of reduction of the computation time, and use the IRAS model introduced in Sec. 5 for the fine tuning of parameters. Furthermore, for our purpose of measuring the performance of the implementation for the 0–1mknp problem, we also use the other parallel models introduced in Sec. 5, as well as the sequential implementation, for experimenting. 6.3.1 Parameter tuning Many mutually-dependent parameters are involved in the instantiation of the TS skeleton for the 0–1mknp problem. Some of these parameters are related to the instantiation proposed while some others are proper to the TS meta-heuristic. As for the parameters of the TS, the basic parameters are those controlling the stopping conditions (max_execution_time and independent_runs) and the influence of the historical search memory (tabu_list_size). Other important parameters are used to control the search process, specially the neighborhood exploration (max_neighbors), the intensification (max_repetitions,nb_best_sols and nb_intensification) and the diversification (history_rep and nb_diversifications). In the following, we report the best values obtained in the tuning for each of these parameters (see Table 1 for a summary). max_execution_time and independent_runs:We found that 2 independent runs of the program already provided relatively good solutions (see, e.g., the average results in Tables 3 and 4 for 2 processors), although it depends strongly on the number of iterations of each run. The number of iterations required depends on the size of the problem, specially on n. A value of 900 seconds for this parameter already provides good solutions, even for big size instances. 18 Table 1: Description of the parameters. Parameter Description max_execution_time Maximum execution time of each independent run of the algorithm. independent_runs Number of independent runs. tabu_size Size of the tabu list (for the short term memory of the TS method). max_neighbors Maximum number of neighbors to explore. max_repetitions Number of non-improvements before the intensification is triggered. nb_intensifications Number of iterations that the intensification lasts. nb_diversifications Number of iterations that the soft diversification lasts. nb_best_sols Number of best solutions maintained as history for the intensification. history_rep How often items can belong to a solution before the diversification. 0 20 40 60 80 100 50 60 70 80 90 100 Value of the parameter nb intensifications (%) Percentage of times intensification is triggered (a) Influence of nb_intensifications on the intensification. 30 40 50 60 70 80 90 0 10 20 30 40 50 Value of the parameter history rep (%) Number of times diversification is triggered (b) Influence of history_rep on the diversification. Figure 12: Influence of parameters on intensification and diversification. tabu_size:We have found that a tabu list size of length in [3,15] performs good. The final value is chosen randomly in this interval. max_neighbors:No specific value could be decided for this parameter from our experiments. Therefore, we decided to explore the whole neighborhood instead of only a portion of it. max_repetitions:The value of this parameter is in charge of starting the intensification process. A too low value can make the intensification to start early while a too high value delays the intensification. Since it is very strict and unlikely that exactly the same solution is obtained in consecutive iterations, we have relaxed the definition of difference between solutions by considering the Hamming distance between them. Then, two solutions are considered equal if they have at most αn/ln n(0 < α ≤1) differences. Experimentally, good results are obtained for α= 0.1. nb_best_sols:The bigger the values for this parameter, the more historical information available for a good intensification. However, this also makes the intensification processes slower. The experiments suggest that keeping between 10 and 15 solutions is a good equilibrium between the benefit of the intensification and its computational cost. nb_intensifications:We have observed in the tuning process that even small values of this parameter are useful, thus justifying the need for intensification. Again we had to find a good trade-off between the computational cost and the contribution of the intensification to the quality of solutions. According to the experiments (see Fig. 12(a)), a high percentage of success for intensification can be obtained for the low value of parameter close to 10. history_rep is used to decide whether an item has been incorporated many times to the solution during the search (when so, the soft diversification is triggered). In order to assure a good long-term influence of this parameter and to overcome the drawbacks found when using the constant value in [30], we internally use an another parameter based on this one. We define rep = (history_rep/100) ·max{history[j], j = 1,...,n}, which gets a proportional value (w.r.t. the elements of the array history) at each iteration of the diversification. The better 19 results are obtained for high values of this parameter (between 80% and 95%, see Fig. 12(b)). nb_diversifications:The experiments performed could not clarify which should be a good value for this parameter. However, we could observe that worse quality solutions were obtained when no diversification is performed, i.e., when the parameter is 0. From all the values we tried out, fixing it to 10 showed to provide reasonable good solutions. 6.3.2 Computational results After tuning the parameters involved in TS for the 0–1mknp, we have tested more in detail the instantiation proposed in Sec. 6.2 for the problem. We report results concerning the sequential as well as the parallel implementations provided by the TS skeleton. In order to obtain some statistical significance about the robustness of the implementation, the same experiment was run several times and thus the results refer to the average results obtained. In our experiments, each instance is run 20 times (i.e., the independent_runs parameter is set to 20), and each of the 20 runs is fixed to last 900 seconds (i.e., the max_execution_time parameter is set to 900).3The setting for the remaining parameters is the same for each experiment, as obtained in the tuning (see Sec. 6.3.1). All our experiments are run in a cluster of nine AMD K6-11 computers with 450 MHz processors and 256Mb of memory. The implementations are done in C++ using LEDA [28], MPI and are compiled with GCC 2.95.2. We tested small, medium and big size instances (in terms of the number of variables) taken from the literature. Small instances (n≤50) are taken from [18, 10], middle size instances (50 < n ≤100) are taken from [40, 33], and big size instances (100 < n ≤500) are taken from the OR-library [3]. We report here results concerning some of their big size instances. More results concerning smaller and very big-size instances are included as appendix. Sequential executions. Table 2 summarizes some of the results obtained from the sequential implementation. We report results for the direct and the combinatorial neighborhood exploration strategies described in Sec. 6.2. We notice that the average deviation of best solutions w.r.t. the optimum is very small. On the one hand this shows that our instantiation of the problem is appropriate and, on the other, the small values for the deviation also indicates the robustness of our approach in the sense that the values we found in the tuning process perform very well for a large set of different instances. Observe, however, that the combinatorial exploration provides better results. Therefore, we choose this latter strategy for the experiments concerning parallel executions. Parallel executions. Table 3 summarizes the results obtained for the IR and IRAS parallel implementations. We can observe that, when fixing the same computation time, the IR model performs better than the IRAS model. This is due to the fact that, in the same amount of time, the IRAS model cannot do as many iterations of the algorithm as the IR model can do. The IRAS model needs also more extra time for generating the strategies and for communication. Moreover, some of those generated strategies may not be appropriate, although the IRAS model invests time on exploring with them. However, we have observed in additional experiments (not reported here) that the effect of this drawback is reduced when the execution time is increased. The nature of the IR and IRAS models reinforces the general observation that the more processors are used for computation, the better results we obtain, since a broader area of the search space is explored. Table 4 summarizes the results obtained for the execution of the MS and MSNP parallel implementations. We can observe that, for a small number of processors, the MS model achieves better results than the MSNP model. Again, a reason for this effect might be the fact that, in the fixed execution time the MS model does usually more iterations than the MSNP does. However, due to communication overhead, this effect fades away when more processors are used because, in proportion, more time is used in communication. Concerning the MS model, it is worth mentioning 3In the literature (see [8]), the execution times vary roughly from 700 seconds (for quite small instances) to 2500 seconds. 20 that the results obtained with eight processors are not better than the ones obtained with four processors. More processors in the MS model represent more exploration of the neighborhood, but also more time and more re-exploration of already explored areas; in a fixed time, this translates into less iterations of the algorithm and therefore worse results. This effect does not appear in the MSNP model, since there the usage of more processors implies a thorougher exploration of each neighborhood. Therefore, the more processors participating in the MSNP model, the better results are obtained. Moreover, the more processors, the less portion of the neighborhood that each of them will have to explore, and thus, the faster a neighborhood will be explored. This is the reason why, when using eight processors and a fixed amount of time, the number of iterations performed in both models becomes similar. 7 Conclusions In this work we have presented an approach to obtain a generic implementation of the Tabu Search meta-heuristic by using algorithmic skeletons. Algorithmic skeletons constitute a way to reduce the effort to develop sequential and parallel applications. Indeed, the skeleton separates the implementation of the generic algorithm from the specific knowledge of the concrete problem being solved. The implementation of the generic algorithm is provided in the skeleton and the user is just required to describe the elements defining his problem of interest. Moreover, due to this separation of concerns, we are able to encapsulate in the skeleton not only the generic algorithm but also different parallel implementations of it. There is no need for the user to know parallel programming: an important advantage of our approach is the use of sequential constructs in the interface of the skeleton and its instantiation. The result is a program able to run in both sequential and parallel settings. We have instantiated our skeleton for several well known combinatorial optimization problems for which TS has already been implemented. In this process, we have observed that our approach shows interesting properties regarding developing time, flexibility and easiness of use, quality of solutions and computation efficiency. In this paper, we have chosen to exemplify in detail our approach to instantiate the 0–1 Multidimensional Knapsack problem. From this instantiations, we have reported extensive experimental results from standard benchmarks for this problem. The parallel program has been executed on a cluster of commodity machines and uses MPI as a communication library. In spite of the genericity of our implementation, our results show that the resulting program provides high quality solutions very close to the optimal ones. Moreover, we have shown the flexibility of our approach by providing two different implementations for the problem by just changing the neighborhood implementation. Acknowledgments The authors wish to thank the members of the mallba Project for their support and useful discussions while conducting this research. We are also grateful to Christian Blum for providing us with the sources of the Fig. 3 from his article [7]. 21 Table 2: Results obtained in the sequential execution of big-size instances of the OR-library when using two different implementations of the neighborhood exploration for the 0–1mknp problem. Each instance is run 20 times. Instance information is found in the first four columns; the 5th and 9th columns report the best cost obtained; the 6th and 10th report the average cost obtained and the 7th and 11th the deviation of the best obtained costs w.r.t. the Best known cost. The 8th and 12th columns indicate the number of iterations that the algorithm performed in 900s. Direct exploration of the neighborhood Combinatorial exploration of the neighborhood Instance n m Best known cost Best obtained cost Average cost dev. from opt. Iterations Best cost Average cost dev. from opt. Iterations OR5x250-00 250 5 59312 55963 55450.8 0.0565 94054.8 58900 58469.8 0.0069 1970.8 OR5x250-29 250 5 154662 153312 153257.2 0.0087 115364.0 154309 153998.8 0.0023 1402.6 OR10x250-00 250 10 59187 56213 55945.6 0.0502 55132.9 58076 57680.8 0.0188 1659.6 OR10x250-29 250 10 149704 148342 148121.9 0.0091 68679.3 148868 148292.6 0.0056 901.4 OR30x250-00 250 30 56693 54711 54534.6 0.0350 15215.1 55946 55490.2 0.0132 1672.2 OR30x250-29 250 30 149572 148588 148349.6 0.0066 22437.6 148761 148579.0 0.0054 768.6 Table 3: Results obtained in the IR and IRAS parallel models’ execution of big-size instances of the OR-library (using a combinatorial exploration of the neighborhood) for the 0–1mknp problem. Each instance is run 20 times. Instance information is found in the first four columns; the 5th and 9th columns report the best cost obtained; the 6th and 10th report the average cost obtained and the 7th and 11th the deviation of the best obtained costs w.r.t. the Best known cost. The 8th and 12th columns indicate the number of iterations that the algorithm performed in 900s. IR model IRAS model Instance n m Best known cost Best obtained cost Average cost dev. from opt. Iterations Best cost Average cost dev. from opt. Iterations 2 procs. 58610 58492.0 0.0118 2163.0 57645 57223.8 0.0281 1238.4 OR5x250-00 250 5 59312 4 procs. 58908 58636.8 0.0068 6784.8 58417 57698.8 0.0151 3192.0 8 procs. 58833 58739.2 0.0081 15079.0 58106 57713.2 0.0203 8922.8 2 procs. 154437 154154.6 0.0015 1452.8 153871 152940.8 0.0051 782.8 OR5x250-29 250 5 154662 4 procs. 154446 154132.3 0.0014 3362.8 153666 153297.0 0.0064 1360.6 8 procs. 154437 154339.0 0.0015 8173.6 154188 153972.0 0.0031 4407.8 2 procs. 58353 58005.2 0.0141 1837.0 56513 55685.0 0.0452 956.4 OR10x250-00 250 10 59187 4 procs. 58090 58015.6 0.0185 5204.4 56376 55757.0 0.0475 1566.4 8 procs. 58481 58301.6 0.0119 13605.0 56496 56198.8 0.0455 4435.4 2 procs. 148499 148056.2 0.0080 822.0 147781 147739.4 0.0128 416.6 OR10x250-29 250 10 149704 4 procs. 149009 148767.0 0.0046 2782.6 148077 147831.6 0.0109 1152.8 8 procs. 149058 148889.0 0.0043 5717.2 149030 148840.2 0.0045 3762.8 2 procs. 55567 55501.8 0.0199 2016.8 55346 54872.2 0.0238 674.2 OR30x250-00 250 30 56693 4 procs. 55909 55648.2 0.0138 4404.8 55412 55055.2 0.0226 1575.6 8 procs. 55959 55811.0 0.0129 10253.0 55725 55494.6 0.0170 4764.8 2 procs. 148710 148489.0 0.0058 555.2 148147 147761.8 0.0095 223.2 OR30x250-29 250 30 149572 4 procs. 148901 148621.0 0.0045 1326.8 148010 147720.4 0.0104 398.0 8 procs. 149024 148886.6 0.0037 4785.0 149034 148969.6 0.0036 2231.4 22 Table 4: Results obtained in the MS and MSNP parallel models’ execution of big-size instances of the OR-library (using a combinatorial exploration of the neighborhood) for the 0–1mknp problem. Each instance is run 20 times. Instance information is found in the first four columns; the 5th and 9th columns report the best cost obtained; the 6th and 10th report the average cost obtained and the 7th and 11th the deviation of the best obtained costs w.r.t. the Best known cost. The 8th and 12th columns indicate the number of iterations that the algorithm performed in 900s. MS model MSNP model Instance n m Best known cost Best obtained cost Average cost dev. from opt. Iterations Best cost Average cost dev. from opt. Iterations 2 procs. 58389 58282.2 0.0156 1711.8 56258 55362.2 0.0515 271.0 OR5x250-00 250 5 59312 4 procs. 58736 58318.6 0.0097 1389.4 57838 57059.6 0.0249 747.2 8 procs. 58660 58274.2 0.0110 771.0 58085 57923.0 0.0207 1223.8 2 procs. 154398 154199.6 0.0017 1101.4 152793 152473.6 0.0121 252.2 OR5x250-29 250 5 154662 4 procs. 154315 153862.0 0.0022 838.6 153518 153079.8 0.0074 484.4 8 procs. 154105 153643.0 0.0036 554.8 153636 153283.2 0.0066 746.4 2 procs. 58176 58097.6 0.0171 1431.0 54510 54135.6 0.0790 114.0 OR10x250-00 250 10 59187 4 procs. 57847 57606.6 0.0226 1141.6 55352 54912.8 0.0648 278.4 8 procs. 57674 57227.4 0.0256 492.4 55374 54941.8 0.0644 505.4 2 procs. 148532 148140.0 0.0078 674.8 147777 147590.0 0.0129 209.4 OR10x250-29 250 10 149704 4 procs. 148426 148237.2 0.0085 625.6 147865 147771.0 0.0123 363.6 8 procs. 148151 147805.2 0.0104 368.2 148220 147954.2 0.0099 669.2 2 procs. 55642 55285.8 0.0185 797.0 54317 53820.0 0.0419 95.0 OR30x250-00 250 30 56693 4 procs. 56037 55174.6 0.0116 501.2 55082 54112.4 0.0284 142.8 8 procs. 55323 54937.8 0.0242 234.5 54951 54386.4 0.0307 269.0 2 procs. 148934 148416.2 0.0043 424.6 147155 147111.6 0.0162 57.0 OR30x250-29 250 30 149572 4 procs. 148862 148598.8 0.0047 334.2 148142 148019.2 0.0096 129.6 8 procs. 148582 148259.4 0.0066 199.0 148424 148099.2 0.0077 221.4 23 Table 5: Results obtained in the sequential execution of different size instances of the OR-library when using two different implementations of the neighborhood exploration for the 0–1mknp problem. Each instance is run 20 times. Instance information is found in the first four columns; the 5th and 9th columns report the best cost obtained; the 6th and 10th report the average cost obtained and the 7th and 11th the deviation of the best obtained costs w.r.t. the Best known cost. The 8th and 12th columns indicate the number of iterations that the algorithm performed in the established execution time. The established time was 600 seconds for those instances with n= 100, 900 seconds for those instances with n= 250, and 1200 seconds for those ones with n= 500. For the sake of comparability, the results in Table 2 are also reported here (middle part). Direct exploration of the neighborhood Combinatorial exploration of the neighborhood Instance n m Best known cost Best obtained cost Average cost dev. from opt. Iterations Best cost Average cost dev. from opt. Iterations OR5x100-00 100 5 24381 22781 22615.1 0.0656 158620.2 24381 24238.8 0 10441.6 OR5x100-29 100 5 59965 59639 59496.7 0.0054 179516.0 59945 59855.2 0.0003 6902.4 OR10x100-00 100 10 23064 22478 22360.4 0.0254 85629.8 22944 22822.0 0.0052 10340.4 OR10x100-29 100 10 60633 60629 60518.9 0.0001 68679.3 60633 60592.6 0 9335.6 OR30x100-00 100 30 21946 21614 21520.7 0.0151 31615.7 21719 21656.8 0.0103 5362.0 OR30x100-29 100 30 60603 60432 60292.8 0.0028 37874.5 60603 60349.6 0 4338.8 OR5x250-00 250 5 59312 55963 55450.8 0.0565 94054.8 58900 58469.8 0.0069 1970.8 OR5x250-29 250 5 154662 153312 153257.2 0.0087 115364.0 154309 153998.8 0.0023 1402.6 OR10x250-00 250 10 59187 56213 55945.6 0.0502 55132.9 58076 57680.8 0.0188 1659.6 OR10x250-29 250 10 149704 148342 148121.9 0.0091 68679.3 148868 148292.6 0.0056 901.4 OR30x250-00 250 30 56693 54711 54534.6 0.0350 15215.1 55946 55490.2 0.0132 1672.2 OR30x250-29 250 30 149572 148588 148349.6 0.0066 22437.6 148761 148579.0 0.0054 768.6 OR5x500-00 500 5 120130 112991 112575.3 0.0594 68692.6 116969 115622.4 0.0263 426.2 OR5x500-29 500 5 299904 296939 296079.3 0.0099 81719.4 297013 295104.6 0.0096 295.4 OR10x500-00 500 10 117726 111773 111486.7 0.0506 35487.5 115919 114188.2 0.0153 592.2 OR10x500-29 500 10 307014 303943 303642.9 0.0100 44267.8 303417 302680.8 0.0117 205.0 OR30x500-00 500 30 115868 111272 110942.4 0.0397 10459.3 112898 112028.0 0.0256 759.6 OR30x500-29 500 30 300460 298719 298533.4 0.0058 12410.6 298634 297754.4 0.0061 170.0 30 Table 6: Results obtained in the IR and MS parallel models’ execution of some (not so) small instances of the OR-library (using a combinatorial exploration of the neighborhood) for the 0–1mknp problem. Each instance is run 20 times. Instance information is found in the first four columns; the 5th and 9th columns report the best cost obtained; the 6th and 10th report the average cost obtained and the 7th and 11th the deviation of the best obtained costs w.r.t. the Best known cost. The 8th and 12th columns indicate the number of iterations that the algorithm performed in 600s. IR model MS model Instance n m Best known cost Best obtained cost Average cost dev. from opt. Iterations Best cost Average cost dev. from opt. Iterations 2 procs. 24381 24075.2 0 9112.0 24220 24109.2 0.0066 5459.6 OR5x100-00 100 5 24381 4 procs. 24329 24244.6 0.0021 25710.0 24329 24232.4 0.0021 4169.8 8 procs. 24329 24252.2 0.0021 58314.8 24282 24052.2 0.0041 1838.0 2 procs. 59931 59728.0 0.0006 5562.6 59955 59879.2 0.0002 5691.8 OR5x100-29 100 5 59965 4 procs. 59955 59919.4 0.0002 24355.2 59846 59738.6 0.0020 3294.8 8 procs. 59965 59939.4 0 54557.8 59896 59792.6 0.0012 1723.0 2 procs. 22978 22851.6 0.0037 10430.6 23055 22931.4 0.0004 4926.0 OR10x100-00 100 10 23064 4 procs. 23011 22931.0 0.0023 23355.8 22966 22833.4 0.0042 3177.4 8 procs. 23055 23022.4 0.0004 61070.0 22717 22670.0 0.0150 1079.8 2 procs. 60633 60590.0 0 6994.2 60629 60579.8 0.0001 3970.6 OR10x100-29 100 10 60633 4 procs. 60633 60553.6 0 18109.0 60633 60590.2 0 2770.8 8 procs. 60633 60597.8 0 59533.2 60629 60507.4 0.0001 1040.4 2 procs. 21829 21664.0 0.0053 6749.4 21707 21629.4 0.0109 2240.0 OR30x100-00 100 30 21946 4 procs. 21946 21780.2 0 17297.4 21662 21620.8 0.0129 1337.8 8 procs. 21946 21827.4 0 38477.4 21616 21493.8 0.0150 430.4 2 procs. 60472 60381.6 0.0022 4580.0 60327 60158.0 0.0046 1700.2 OR30x100-29 100 30 60603 4 procs. 60603 60410.8 0 11961.6 60351 60160.4 0.0042 1104.4 8 procs. 60554 60493.2 0.0008 31864.0 60123 60072.2 0.0079 387.2 31 Table 7: Results obtained in the IR and MS parallel models’ execution of very big-size instances of the OR-library (using a combinatorial exploration of the neighborhood) for the 0–1mknp problem. Each instance is run 20 times. Instance information is found in the first four columns; the 5th and 9th columns report the best cost obtained; the 6th and 10th report the average cost obtained and the 7th and 11th the deviation of the best obtained costs w.r.t. the Best known cost. The 8th and 12th columns indicate the number of iterations that the algorithm performed in 1200s. IR model MS model Instance n m Best known cost Best obtained cost Average cost dev. from opt. Iterations Best cost Average cost dev. from opt. Iterations 2 procs. 116958 114851.2 0.0264 353.6 116025 115367.4 0.0342 373.2 OR5x500-00 500 5 120130 4 procs. 116561 113983.6 0.0297 1219.4 116550 114838.4 0.0298 378.4 8 procs. 117257 114962.2 0.0239 2669.8 115552 112096.8 0.0381 281.4 2 procs. 295678 294292.4 0.0141 246.6 295162 294688.0 0.0158 233.2 OR5x500-29 500 5 299904 4 procs. 296956 295761.0 0.0098 813.0 296891 293510.8 0.0100 234.6 8 procs. 296631 295473.4 0.0110 1751.8 295432 293429.4 0.0149 191.0 2 procs. 115191 112998.6 0.0215 609.6 115087 113584.4 0.0224 592.2 OR10x500-00 500 10 117726 4 procs. 115241 114704.0 0.0211 1740.0 114635 113513.6 0.0263 436.6 8 procs. 115397 114806.8 0.0198 3860.2 114161 113312.2 0.0303 253.6 2 procs. 303476 303422.4 0.0115 258.2 305051 303728.2 0.0064 274.4 OR10x500-29 500 10 307014 4 procs. 302425 302196.2 0.0149 606.0 303690 303179.0 0.0108 215.2 8 procs. 303476 303175.2 0.0115 1886.6 303469 303322.6 0.0115 187.2 2 procs. 112863 111845.0 0.0259 729.2 112620 111334.0 0.0280 380.2 OR30x500-00 500 30 115868 4 procs. 113453 112673.2 0.0208 1945.0 111340 110791.6 0.0391 319.4 8 procs. 113545 112836.6 0.0200 5097.0 110133 109422.2 0.0495 141.0 2 procs. 298450 297875.8 0.0067 189.4 298211 297746.6 0.0075 181.8 OR30x500-29 500 30 300460 4 procs. 298193 297565.0 0.0075 487.0 298683 297912.2 0.0059 146.4 8 procs. 298701 298013.6 0.0059 1230.2 297681 297614.4 0.0092 97.6 32