Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridizing Metaheuristics With Problem Relaxation <s> In this paper we present a heuristic based upon genetic algorithms for the multidimensional knapsack problem. A heuristic operator which utilises problem-specific knowledge is incorporated into the standard genetic algorithm approach. Computational results show that the genetic algorithm heuristic is capable of obtaining high-quality solutions for problems of various characteristics, whilst requiring only a modest amount of computational effort. Computational results also show that the genetic algorithm heuristic gives superior quality solutions to a number of other heuristics. <s> BIB001 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridizing Metaheuristics With Problem Relaxation <s> We consider the generalized assignment problem in which the objective is to find a minimum cost assignment of a set of jobs to a set of agents subject to resource constraints. The presented new approach is based on a previously published, successful hybrid genetic algorithm and includes as new features two alternative initialization heuristics, a modified selection and replacement scheme for handling infeasible solutions more appropriately, and a heuristic mutation operator. Tests are performed on standard test instances from the literature and on newly created, larger and more difficult instances. The presented genetic algorithm with its two initialization variants is compared to the previous genetic algorithm and to the commercial general purpose branch-and-cut system CPLEX. Results indicate that CPLEX is able to solve relatively large instances of the general assignment problem to provable optimality. For the largest and most difficult instances, however, the proposed genetic algorithm yields on average the best results in shortest time. <s> BIB002 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridizing Metaheuristics With Problem Relaxation <s> Abstract Geometric Constraint and Cutting planes have been successfully used to solve the 0–1 multidimensional knapsack problem. Our algorithm combines Linear Programming with an efficient tabu search. It gives best results when compared with other algorithms on benchmarks issued from the OR-L ibrary . Embedding this algorithm in a variables fixing heuristic still improves our previous results. Furthermore difficult sub problems with about 100 variables issued from the 500 original ones could be generated. These small sub problems are always very hard to solve. <s> BIB003 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridizing Metaheuristics With Problem Relaxation <s> We consider the version of prize collecting Steiner tree problem (PCSTP) where each node of a given weighted graph is associated with a prize and where the objective is to find a minimum weight tree spanning a subset of nodes and collecting a total prize not less that a given quota Q. We present a lower bound and a genetic algorithm for the PCSTP. The lower bound is based on a Lagrangian decomposition of a minimum spanning tree formulation of the problem. The volume algorithm is used to solve the Lagrangian dual. The genetic algorithm incorporates several enhancements. In particular, it fully exploits both primal and dual information produced by Lagrangian decomposition. The proposed lower and upper bounds are assessed through computational experiments on randomly generated instances with up to 500 nodes and 5000 edges. For these instances, the proposed lower and upper bounds exhibit consistently a tight gap: in 76% of the cases the gap is strictly less than 2%. <s> BIB004 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridizing Metaheuristics With Problem Relaxation <s> We present a Lagrangian decomposition approach for the Knapsack Constrained Maximum Spanning Tree problem yielding upper bounds as well as heuristic solutions. This method is further combined with an evolutionary algorithm to a sequential hybrid approach. Experimental investigations, including a comparison to a previously suggested simpler Lagrangian relaxation based method, document the advantages of the new approach. Most of the upper bounds derived by Lagrangian decomposition are optimal, and together with the evolutionary algorithm, large instances with up to 12000 nodes can be either solved to provable optimality or with a very small remaining gap in reasonable time. <s> BIB005 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Hybridizing Metaheuristics With Problem Relaxation <s> In this paper the influence of structural information obtained from a problem relaxation on the performance of an ACO algorithm for the symmetric TSP is studied. More precisely, a very simple ACO algorithm is guided by including Minimal Spanning Tree information into the visibility. Empirical results on a large number of benchmark instances from TSPLIB are presented. The paper concludes with remarks on some more elaborate ideas for using problem relaxation within ACO. <s> BIB006
Taking metaheuristic problem relaxation has become a successful hybrid approach in recent year. A so-called relaxed version of the problem is achieved by modifying or recovering constraints from the original problem. The desire is to achieve two things. First one is that the relaxed problem can be solved well and the other is the construction of an optimal solution to the relaxed problem can be used to solve the original problem simultaneously with its objective function. An important kind of relaxation in combinatorial optimization relates by metaheuristic the integrity constraints of the involved variable. The leading linear programming relaxation can be efficiently solved by method like such as simplex algorithm to optimality. A straightforward way to optimality is to derive a heuristic integer solution such that it can be feasible for the main problem. It can be simple rounding or more sophisticated repairing strategies depend on the problem.  propose an algorithm for job-shop scheduling problem that work by first implementing a genetic algorithm identifying a promising area of the search space then the fitness of the solution is calculated by Lagrangian relaxation. Then, exhaustive search is performed to find the best solution within the search space  . Another work proposed by BIB001 for the multidimensional knapsack problem is an evolutionary algorithm that use dual variable values for calculating pseudo utility ratios for the variable BIB001 . BIB002 proposed a hybrid genetic algorithm for the generalized assignment problem. The LP relaxation is used to create an initial population of integral solution by a randomized rounding procedure BIB002 . Vasquez and Vimont (2005) proposed a two phase algorithm for 0-1 knapsack problem. In the first phase by neglecting the integrity constraints, a number of relaxed problems can be solved to optimality. In the second phase, tabu search is enforced to search to around the best possible solution to these relaxed problems BIB003 . Another work reported by BIB004 presents the hybrid Lagrangian genetic algorithm for prize collecting steiner tree problem. Hereby genetic algorithm makes use of a Lagrangian relaxation. Meaningful initial solutions are generated by reducing the graph by cutting edge and the objective function is modified by cost reduction BIB004 . For the knapsack constrained maximum spanning tree problem, BIB005 a hybridization of Lagrangian decomposition and a genetic algorithm is proposed by BIB005 . Finally an ant colony optimization for the symmetric TSP is proposed by BIB006 where optimal solution is used for prejudicing the search of the artificial ants towards the edges of the minimum spanning tree BIB006 .