Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridizing Metaheuristic With Tree Search Technique <s> We propose a new randomized method for solving global optimization problems. This method, the Nested Partitions (NP) method, systematically partitions the feasible region and concentrates the search in regions that are the most promising. The most promising region is selected in each iteration based on information obtained from random sampling of the entire feasible region and local search. The method hence combines global and local search. We first develop the method for discrete problems and then show that the method can be extended to continuous global optimization. The method is shown to converge with probability one to a global optimum in finite time. In addition, we provide bounds on the expected number of iterations required for convergence, and we suggest two stopping criteria. Numerical examples are also presented to demonstrate the effectiveness of the method. <s> BIB001 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridizing Metaheuristic With Tree Search Technique <s> In this paper we present two major approaches to solve the car sequencing problem, in which the goal is to find an optimal arrangement of commissioned vehicles along a production line with respect to constraints of the form "no more than lc cars are allowed to require a component c in any subsequence of mc consecutive cars". The first method is an exact one based on integer linear programming (ILP). The second approach is hybrid: it uses ILP techniques within a general variable neighborhood search (VNS) framework for examining large neighborhoods. We tested the two methods on benchmark instances provided by CSPLIB and the automobile manufacturer RENAULT for the ROADEF Challenge 2005. These tests reveal that our approaches are competitive to previous reported algorithms. For the CSPLIB instances we were able to shorten the required computation time for reaching and proving optimality. Furthermore, we were able to obtain tight bounds on some of the ROADEF instances. For two of these instances the proposed ILP-method could provide new optimality proofs for already known solutions. For the VNS, the individual contributions of the used neighborhoods are also experimentally analyzed. Results highlight the significant impact of each structure. In particular the large ones examined using ILP techniques enhance the overall performance significantly, so that the hybrid approach clearly outperforms variants including only commonly defined neighborhoods. <s> BIB002 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridizing Metaheuristic With Tree Search Technique <s> Evolutionary algorithms adopt a natural-selection analogy, exploiting concepts such as population, combination, mutation, and selection to explore a diverse space of possible solutions to combinatorial optimization problems while, at the same time, retaining desirable properties from known solutions. This paper describes an evolutionary approach to improving solutions to mixed integer programming (MIP) models. We propose coarse-grained approaches to mutating and combining MIP solutions, both built within a large-neighborhood search framework. These techniques are then integrated within a MIP branch-and-bound framework. The resulting solution-polishing heuristic often finds significantly better feasible solutions to very difficult MIP models than do available alternatives. In contrast to most evolutionary algorithms, our polishing heuristic is domain-independent, requiring no structural information about the underlying combinatorial problem, above and beyond the information contained in the original MIP formulation. <s> BIB003 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridizing Metaheuristic With Tree Search Technique <s> Branch-and-bound (BnB) and memetic algorithms represent two very different approaches for tackling combinatorial optimization problems. However, these approaches are compatible. In this correspondence, a hybrid model that combines these two techniques is considered. To be precise, it is based on the interleaved execution of both approaches. Since the requirements of time and memory in BnB techniques are generally conflicting, a truncated exact search, namely, beam search, has opted to be carried out. Therefore, the resulting hybrid algorithm has a heuristic nature. The multidimensional 0-1 knapsack problem and the shortest common supersequence problem have been chosen as benchmarks. As will be shown, the hybrid algorithm can produce better results in both problems at the same computational cost, especially for large problem instances <s> BIB004 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridizing Metaheuristic With Tree Search Technique <s> The travelling salesman problem with time windows is a difficult optimization problem that arises, for example, in logistics. This paper deals with the minimization of the travel-cost. For solving this problem, this paper proposes a Beam-ACO algorithm, which is a hybrid method combining ant colony optimization with beam search. In general, Beam-ACO algorithms heavily rely on accurate and computationally inexpensive bounding information for differentiating between partial solutions. This work uses stochastic sampling as a useful alternative. An extensive experimental evaluation on seven benchmark sets from the literature shows that the proposed Beam-ACO algorithm is currently a state-of-the-art technique for the travelling salesman problem with time windows when travel-cost optimization is concerned. <s> BIB005
The hybridization of metaheuristic with the tree search technique is one of the popular ways of combining different algorithm for optimization. It is because many metaheuristic as well as some the major complete algorithm belongs to group of tree search technique. Tree search technique views the search space in the form of a tree. As constraints programming is used for exploring large neighborhood similarly there is a tree search method which can be applied to the same mainly branch and bound technique depend on linear programming, including branch and cut shows potential when the problem can be expressed by a mixed integer programming [MIP] model. One of the first works on a hybridization of branch and bound with an evolutionary algorithm is done by  for a two machine flow shop scheduling problem  .  proposed tree search method to solve traveling salesman problem. Experiment shows that better solutions are generated by merging solution so as to provide optimality  . Another proposed by Shi and Olafsson (2000) where breadth first searched is hybridized with backtracking for nested partitioning which is used to explore the search space under the guidance of a metaheuristic. The work mentioned above is qualified by a subsidiary use of the tree search method within metaheuristic BIB001 .  proposed an integration of mixed integer programming and local search to solve job shop scheduling problem. In this, metaheuristic can be used as subsidiary technique known as diving where the search processed is focused on neighborhood to provide high quality solutions  . BIB003 proposed a hybridization of an evolutionary algorithm in a MIP solver found on a branch and cut. The approach can be used for finding the best solution for different MIPs BIB003 . Another work proposed by BIB004 in which flow of beam search and memetic algorithm are intertwined BIB004 . A fruitful problem specific paradigm for large neighborhood search has been proposed by BIB002 for solving the car sequencing problem BIB002 . C. BIB005 proposed Beam ACO that includes ACO and beam search for solving traveling salesman problem with time window BIB005 .