Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridization Metaheuristic With Dynamic Programming <s> This paper introduces a new neighborhood search technique, called dynasearch, that uses dynamic programming to search an exponential size neighborhood in polynomial time. While traditional local search algorithms make a single move at each iteration, dynasearch allows a series of moves to be performed. The aim is for the lookahead capabilities of dynasearch to prevent the search from being attracted to poor local optima. We evaluate dynasearch by applying it to the problem of scheduling jobs on a single machine to minimize the total weighted tardiness of the jobs. Dynasearch is more effective than traditional first-improve or best-improve descent in our computational tests. Furthermore, this superiority is much greater for starting solutions close to previous local minima. Computational results also show that an iterated dynasearch algorithm in which descents are performed a few random moves away from previous local minima is superior to other known local search procedures for the total weighted tardiness scheduling problem. <s> BIB001 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridization Metaheuristic With Dynamic Programming <s> Abstract The dynamic plant layout problem (DPLP) deals with the design of multi-period layout plans. Although an optimal solution method based on dynamic programming is available, it is not practical for large DPLPs. It has recently been shown that heuristics based on genetic algorithms can solve large DPLPs. In this research, we extend and improve the use of genetic algorithms by creating a hybrid genetic algorithm. A computational study is carried out to compare the proposed algorithm with the existing genetic algorithms and a recent simulated annealing algorithm. The study shows that the proposed algorithm is effective. Thus it may be useful in solving the larger problems. <s> BIB002 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridization Metaheuristic With Dynamic Programming <s> Tabu search has proven highly successful in solv- ing hard combinatorial optimization problems. In this paper, we propose a hybrid method that combines adaptive memory, sparse dynamic programming, and reduction techniques to reduce and ex- plore the search space. Our approach starts with a bi-partition of the variables, involving a small core problem, which never exceeds 15 variables, solved using the "forward" phase of the dynamic program- ming procedure. Then, the remaining subspace is explored using tabu search, and each partial solution is completed with the informa- tion stored during the forward phase of dynamic programming. Our approach can be seen as a global intensification mechanism, since at each iteration, the move evaluations involve solving a reduced prob- lem implicitly. The proposed specialized tabu search approach was tested in the context of the multidimensional 0-1 knapsack prob- lem. Our approach was compared to ILOG's commercial product CPLEX and to the corresponding "pure" tabu search (i.e., without a core problem) for various sets of test problems available in OR- libraries. The results are encouraging. In particular, this enhances the robustness of the approach, given that it performs better than the corresponding pure tabu search most of the time. Moreover, our approach compares well with CPLEX when the number of variables is large; it is able to provide elite feasible solutions in a very reason- able amount of computational time. <s> BIB003 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridization Metaheuristic With Dynamic Programming <s> We consider the generalized traveling salesman problem in which a graph with nodes partitioned into clusters is given. The goal is to identify a minimum cost round trip visiting exactly one node from each cluster. For solving difficult instances of this problem heuristically, we present a new Variable Neighborhood Search (VNS) approach that utilizes two complementary, large neighborhood structures. One of them is the already known generalized 2-opt neighborhood for which we propose a new incremental evaluation technique to speed up the search significantly. The second structure is based on node exchanges and the application of the chained Lin-Kernighan heuristic. A comparison with other recently published metaheuristics on TSPlib instances with geographical clustering indicates that our VNS, though requiring more time than two genetic algorithms, is able to find substantially better solutions. <s> BIB004 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridization Metaheuristic With Dynamic Programming <s> The simple assembly line balancing problem is the simplification of a real problem associated to the assignment of the elementary tasks required for assembly of a product in an assembly line. This problem has been extensively studied in the literature for more than half a century. The present work proposes a new procedure to solve the problem we call Bounded Dynamic Programming. This use of the term Bounded is associated not only with the use of bounds to reduce the state space but also to the reduction of such space based on heuristics. This procedure is capable of obtaining an optimal solution rate of 267 out of 269 instances, which have been used in previous works, thus obtaining the best-known performance for the problem. These results are an improvement from any previous procedure found in the literature even when using smaller computing times. <s> BIB005
Dynamic programming (DP) is an example of an optimization method that can be successfully combined with metaheuristic, both in the case of constructive and local search technique. Iterated dynasearch are a hybrid metaheuristic in which DP is used as a neighborhood exploration approach inside iterated local search. The motivation behind this integration is that in neighborhood exploration strategy, the greater the neighborhood size more effectively the quality of the local optimum generates. In some cases in polynomial time, DP can make it possible to completely explore an exponential size neighborhood. Congram et al. proposed iterated dynasearch (2002) used to solve for single machine total weight tardiness scheduling problem. It is the problem of discovering the processing order of many jobs on single machine such that the total tardiness is minimized BIB001 . BIB002 proposed a hybrid algorithm that contains evolutionary algorithms and DP for solving dynamic facility layout problem. Here several solutions are given, DP is used as a crossover operator for determining the best combination for different planning period BIB002 . Tse et al. (2007) proposes a technique called an iterative dynamic programming that combine GA with local search technique. Here the problems are subdivided into sub problems and then DP optimizes separately [106] . BIB004 proposed a hybrid algorithm for solving generalized traveling salesman problem. The authors use DP in the context of an evolutionary algorithm as a method for generating the optimal solution that can be generated from an incomplete solution BIB004 . BIB003 proposes a hybrid method merging adaptive memory, sparse DP and reduction technique to explore and reduce the search space. Here initially, bi-partition of the variable are created then the resulting small problem is solved and the space of the remaining variable is searched using tabu search BIB003 . Another work proposed by BIB005 use a heuristic version of DP labeled bounded dynamic programming for simple assembly line balancing problem. Here at each level number of positions is heuristically reduced leading to the optimal solution in a reduce amount of time BIB005 .  propose the use of DP algorithm is two different metaheuristic for the K-cardinality tree (KCT) problem. The basic idea of this strategy is not only applicable to KCT problem but also for another subset problem. Basically, the plan is to generate a large number of objects then a solution is found by applying metaheuristic. These objects carry an exponential number of solutions to the problem and DP is used to find best solution efficiently for each object  .