Survey of Metaheuristic Algorithms for Combinatorial Optimization
---
paper_title: An Evolutionary Algorithm for Polishing Mixed Integer Programming Solutions

paper_content:

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.
---
paper_title: Simulated Annealing Metaheuristic for Solving P-Median Problem 1

paper_content:

We present an efficient metaheuristic based on Simulated Annealing for solving the p-Median problem. These ideas are tested on the well known OR-Lib set of problems with excellent results.
---
paper_title: Job Shop Scheduling by Simulated Annealing

paper_content:

We describe an approximation algorithm for the problem of finding the minimum makespan in a job shop. The algorithm is based on simulated annealing, a generalization of the well known iterative improvement approach to combinatorial optimization problems. The generalization involves the acceptance of cost-increasing transitions with a nonzero probability to avoid getting stuck in local minima. We prove that our algorithm asymptotically converges in probability to a globally minimal solution, despite the fact that the Markov chains generated by the algorithm are generally not irreducible. Computational experiments show that our algorithm can find shorter makespans than two recent approximation approaches that are more tailored to the job shop scheduling problem. This is, however, at the cost of large running times.
---
paper_title: A Modified Simulated Annealing Algorithm for the Quadratic Assignment Problem

paper_content:

The quadratic assignment problem (QAP) is one of the well-known combinatorial optimization problems and is known for its various applications. In this paper, we propose a modified simulated annealing algorithm for the QAP - M-SA-QAP. The novelty of the proposed algorithm is an advanced formula of calculation of the initial and final temperatures, as well as an original cooling schedule with oscillation, i.e., periodical decreasing and increasing of the temperature. In addition, in order to improve the results obtained, the simulated annealing algorithm is combined with a tabu search approach based algorithm. We tested our algorithm on a number of instances from the library of the QAP instances - QAPLIB. The results obtained from the experiments show that the proposed algorithm appears to be superior to earlier versions of the simulated annealing for the QAP. The power of M-SA-QAP is also corroborated by the fact that the new best known solution was found for the one of the largest QAP instances - THO150.
---
paper_title: An improved annealing scheme for the QAP

paper_content:

Abstract Recently there has been some interest in the use of Simulated Annealing to obtain ‘good’ solutions to a number of combinatorial problems. This paper reports on the use of this method applied to the Quadratic Assignment Problem (i.e. the assignment of inter-communicating objects to locations to minimize the total cost of communication between them). The result is a much-improved annealing scheme for this problem which performs well on a range of examples, finding improved solutions for several of the largest problems available in the literature and requiring only modest amounts of computational effort.
---
paper_title: A Heuristic Simulated Annealing Algorithm for the Circular Packing Problem

paper_content:

We study the circular packing problem (CPP) which consists of packing a set of circles of known radii into a larger containing circle without overlapping. The objective is to determine the smallest radius of the containing circle and the coordinates of the center of every packed circle. To solve CPP, we propose a heuristic simulated annealing (HSA) algorithm that incorporates heuristic neighborhood search mechanism and the gradient descent method into the simulated annealing procedure. The special neighborhood search mechanism can avoid the disadvantage of blind search in the simulated annealing algorithm and the gradient descent method can speed up searching the global optimal configuration. The computational results, on a set of instances taken from the literature, show the effectiveness of the proposed algorithm.
---
paper_title: A Reactive Tabu Search algorithm with variable clustering for the Unicost Set Covering Problem

paper_content:

We develop a Reactive Tabu Search (RTS) algorithm for solving the Unicost Set Covering Problem (SCP) â€“ USCP-TS. We solve a Linear Programming (LP) relaxation of the problem and use the LP optimum to construct a quality solution profile. We cluster the problem variables based on this profile and partition the solution space into orbits. We tested our algorithm on 65 benchmark problems and compared the results against the previous best-known solutions and those obtained by CPLEX 9.0 under varied settings. USCP-TS outperforms CPLEX in solution quality for 32 of the problems and achieves the same solution as CPLEX faster on 21 of the remaining problems.
---
paper_title: Tabu Search with Simple Ejection Chains for Coloring Graphs

paper_content:

We present a Tabu Search (TS) method that employs a simple version of ejection chains for coloring graphs. The procedure is tested on a set of benchmark problems. Empirical results indicate that the proposed TS implementation outperforms other metaheuristic methods, including Simulated Annealing, a previous version of Tabu Search and a recent implementation of a Greedy Randomized Adaptive Search Procedure (GRASP).
---
paper_title: Multistart Tabu Search and Diversification Strategies for the Quadratic Assignment Problem

paper_content:

The quadratic assignment problem (QAP) is a well-known combinatorial optimization problem with a wide variety of applications, prominently including the facility location problem. The acknowledged difficulty of the QAP has made it the focus of many metaheuristic solution approaches. In this paper, we show the benefit of utilizing strategic diversification within the tabu search (TS) framework for the QAP, by incorporating several diversification and multistart TS variants. Computational results for an extensive and challenging set of QAP benchmark test problems demonstrate the ability of our TS variants to improve on a classic TS approach that is one of the principal and most extensively used methods for the QAP. We also show that our new procedures are highly competitive with the best recently introduced methods from the literature, including more complex hybrid approaches that incorporate the classic TS method as a subroutine.
---
paper_title: Adaptive feature selection for hyperspectral data analysis using a binary hierarchical classifier and tabu search

paper_content:

High dimensional inputs coupled with scarcity of labeled data are among the greatest challenges for classification of hyperspectral data. These problems are exacerbated if the number of classes is large. High dimensional output classes can often be handled effectively by decomposition into multiple two-(meta)class problems, where each sub-problem is solved using a suitable binary classifier, and outputs of this collection of classifiers are combined in a suitable manner to obtain the answer to the original multi-class problem. This approach is taken by the binary hierarchical classifier (BHC). The advantages of the BHC for output decomposition can be further exploited for hyperspectral data analysis by integrating a feature selection methodology with the classifier. Building upon the previously developed best bases BHC algorithm with greedy feature selection, a new method is developed that selects a subset of band groups within metaclasses using reactive tabu search. Experimental results obtained from analysis of Hyperion data acquired over the Okavango Delta in Botswana are superior to those of the greedy feature selection approach and more robust than either the original BHC or the BHC with greedy feature selection.
---
paper_title: A tabu search tutorial based on a real-world scheduling problem

paper_content:

We apply a tabu search method to a scheduling problem of a company producing cables for cars: the task is to determine on what machines and in which order the cable jobs should be produced in order to save production costs. First, the problem is modeled as a combinatorial optimization problem. We then employ a tabu search algorithm as an approach to solve the specific problem of the company, adapt various intensification as well as diversification strategies within the algorithm, and demonstrate how these different implementations improve the results. Moreover, we show how the computational cost in each iteration of the algorithm can be reduced drastically from O(n 3 ) (naive implementation) to O(n) (smart implementation) by exploiting the specific structure of the problem (n refers to the number of cable orders). Copyright The Author(s) 2011
---
paper_title: The Reactive Tabu Search

paper_content:

We propose an algorithm for combinatorial optimization where an explicit check for the repetition of configurations is added to the basic scheme of Tabu search. In our Tabu scheme the appropriate size of the list is learned in an automated way by reacting to the occurrence of cycles. In addition, if the search appears to be repeating an excessive number of solutions excessively often, then the search is diversified by making a number of random moves proportional to a moving average of the cycle length. The reactive scheme is compared to a “strict” Tabu scheme that forbids the repetition of configurations and to schemes with a fixed or randomly varying list size. From the implementation point of view we show that the Hashing or Digital Tree techniques can be used in order to search for repetitions in a time that is approximately constant. We present the results obtained for a series of computational tests on a benchmark function, on the 0-1 Knapsack Problem, and on the Quadratic Assignment Problem. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
---
paper_title: SOLVING THE MULTIPLE-MACHINE WEIGHTED FLOW TIME PROBLEM USING TABU SEARCH

paper_content:

In this paper we discuss the development and application of a new and more powerful method for solving the muldple-machine weighted flow time problem using a basic tabu search (TS) approach. Previous methods of solution used branch and bound and are computationally limited to problems of about 25 jobs. In a set of previously published problems with IS to 30 jobs, the new method achieved optimality in at least an order of magnitude less computation time than branch and bound first achieved the optimum. Studies of larger problems indicate that the new method maintains its ability to achieve superior solutions with only a modest growth in computational effort.
---
paper_title: Solving the pickup and delivery problem with time windows using reactive tabu search

paper_content:

The pickup and delivery problem with time windows requires that a group of vehicles satisfy a collection of customer requests. Each customer request requires the use of a single vehicle both to load a specified amount of goods at one location and to deliver them to another location. All requests must be performed without violating either the vehicle capacity or the customer time window stipulated at each location. In this paper, we present a reactive tabu search approach to solve the pickup and delivery problem with time windows using three distinct move neighborhoods that capitalize on the dominance of the precedence and coupling constraints. A hierarchical search methodology is used to dynamically alternate between neighborhoods in order to negotiate different regions of the solution space and adjust search trajectories. In order to validate our technique's effectiveness, we have constructed a new set of benchmark problems for the pickup and delivery problem with time windows based on Solomon's benchmark vehicle routing problem with time windows data sets. Computational results substantiate the solution quality and efficiency of our reactive tabu search approach.
---
paper_title: Solving zero-one mixed integer programming problems using tabu search

paper_content:

We describe a tabu search (TS) approach for solving general zero-one mixed integer programming (MIP) problems that exploits the extreme point property of zero-one solutions. Specialized choice rules and aspiration criteria are identified for the problems, expressed as functions of integer infeasibility measures and objective function values. The first-level TS mechanisms are then extended with advanced level strategies and learning. We also look at probabilistic measures in this framework, and examine how the learning tool Target Analysis (TA) can be applied to identify better control structures and decision rules. Computational results are reported on a portfolio of multiconstraint knapsack problems. Our approach is designed to solve thoroughly general 0/1 MIP problems and thus contains no problem domain specific knowledge, yet it obtains solutions for the multiconstraint knapsack problem whose quality rivals, and in some cases surpasses, the best solutions obtained by special purpose methods that have been created to exploit the special structure of these problems.
---
paper_title: Solving the Traveling-Salesman Problem with Time Windows Using Tabu Search

paper_content:

This paper presents a robust tabu search approach to the traveling-salesman problem with time windows. The approach uses a two-level tour hashing scheme within a reactive tabu search procedure to detect unique repeated solutions and to promote a more diverse search. Strong feasibility conditions restrict the neighborhood of candidate solutions. The search returns optimal, or near-optimal, solutions within a fraction of the time required by optimal methods. The algorithm’s search neighborhood is not restricted to feasible solutions, and superior marginally infeasible solutions are reported to enhance the decision making process. The paper presents computational results for 145 problems from the literature.
---
paper_title: Tabu search for the multilevel generalized assignment problem

paper_content:

Abstract The multilevel generalized assignment problem (MGAP) differs from the classical GAP in that agents can perform tasks at more than one efficiency level. Important manufacturing problems, such as lot sizing, can be formulated as MGAPs; however, the large number of variables in the related 0–1 integer program makes the use of commercial optimization packages impractical. In this paper, we present a heuristic approach to the solution of the MGAP, which consists of a novel application of tabu search (TS). Our TS method employs neighborhoods defined by ejection chains, that produce moves of greater power without significantly increasing the computational effort.
---
paper_title: A Hybrid Grasp With Perturbations For The Steiner Problem In Graphs

paper_content:

We propose and describe a hybrid GRASP with weight perturbations and adaptive path-relinking heuristic (HGP + PR) for the Steiner problem in graphs. In this multi-start approach, the greedy randomized construction phase of a GRASP is replaced by the use of several construction heuristics with a weight perturbation strategy that combines intensification and diversification elements, as in a strategic oscillation approach. The improvement phase circularly explores two different local search strategies. The first uses anode-based neighborhood for local search, while the second uses a key-path-based neighborhood. An adaptive path-relinking technique is applied to a set of elite solutions as apost-optimization strategy. Computational results on a broad set of benchmark problems illustrate the effectiveness and the robustness of our heuristic, which is very competitive when compared to other approximate algorithms.
---
paper_title: Multiple Phase Neighborhood Search-GRASP for the Capacitated Vehicle Routing Problem

paper_content:

Greedy Randomized Adaptive Search Procedure (GRASP) has been proved to be a very efficient algorithm for the solution of the Traveling Salesman Problem. Also, it has been proved that expanding the local search with the use of two or more different local search strategies helps the algorithm to avoid trapping in a local optimum. In this paper, a new modified version of GRASP, called Multiple Phase Neighborhood Search-GRASP (MPNS-GRASP), for the solution of the Vehicle Routing Problem is proposed. In this method, a stopping criterion based on Lagrangean Relaxation and Subgradient Optimization is utilized. In addition, a different way for expanding the neighborhood search is used based on a new strategy, the Circle Restricted Local Search Moves strategy. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the results have solution qualities with average values near to the optimum values and in a number of them the algorithm finds the optimum. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the new strategy, the Expanding Neighborhood Search Strategy, is used.
---
paper_title: A GRASP strategy for a more constrained School Timetabling Problem

paper_content:

This work treats a more constrained School Timetabling Problem (STP). It consists of scheduling a set of lectures and teachers in a prefixed period of time, satisfying a set of operational requirements. We applied a Greedy Randomized Adaptive Search Procedure (GRASP) heuristic, combined with a path-relinking improvement. During execution of the GRASP heuristic, the local search procedure interleaves two types of movements. In addition, the path-relinking strategy was itself enhanced by a local search procedure. The algorithms were tested with real instances and proved to be good approaches to solve this problem. Although some restrictions are specific to Brazilian educational institutions, the same ideas can inspire similar approaches for solving the STP in other situations.
---
paper_title: Greedy Randomized Adaptive Search Procedures

paper_content:

Today, a variety of heuristic approaches are available to the operations research practitioner. One methodology that has a strong intuitive appeal, a prominent empirical track record, and is trivial to efficiently implement on parallel processors is GRASP (Greedy Randomized Adaptive Search Procedures). GRASP is an iterative randomized sampling technique in which each iteration provides a solution to the problem at hand. The incumbent solution over all GRASP iterations is kept as the final result. There are two phases within each GRASP iteration: the first intelligently constructs an initial solution via an adaptive randomized greedy function; the second applies a local search procedure to the constructed solution in hope of finding an improvement. In this paper, we define the various components comprising a GRASP and demonstrate, step by step, how to develop such heuristics for combinatorial optimization problems. Intuitive justifications for the observed empirical behavior of the methodology are discussed. The paper concludes with a brief literature review of GRASP implementations and mentions two industrial applications.
---
paper_title: Variable neighborhood search for the Vertex Separation Problem

paper_content:

The Vertex Separation Problem belongs to a family of optimization problems in which the objective is to find the best separator of vertices or edges in a generic graph. This optimization problem is strongly related to other well-known graph problems; such as the Path-Width, the Node Search Number or the Interval Thickness, among others. All of these optimization problems are NP-hard and have practical applications in VLSI (Very Large Scale Integration), computer language compiler design or graph drawing. Up to know, they have been generally tackled with exact approaches, presenting polynomial-time algorithms to obtain the optimal solution for specific types of graphs. However, in spite of their practical applications, these problems have been ignored from a heuristic perspective, as far as we know. In this paper we propose a pure 0-1 optimization model and a metaheuristic algorithm based on the variable neighborhood search methodology for the Vertex Separation Problem on general graphs. Computational results show that small instances can be optimally solved with this optimization model and the proposed metaheuristic is able to find high-quality solutions with a moderate computing time for large-scale instances.
---
paper_title: A variable neighborhood search for graph coloring C

paper_content:

Descent methods for combinatorial optimization proceed by performing a sequence of local changes on an initial solution which improve each time the value of an objective function until a local optimum is found. Several metaheuristics have been proposed which extend in various ways this scheme and avoid being trapped in local optima. For example, Hansen and Mladenovic have recently proposed the variable neighborhood search method which has not yet been applied to many combinatorial optimization problems. The aim of this paper is to propose an adaptation of this new method to the graph coloring problem. � 2003 Published by Elsevier B.V.
---
paper_title: Variable Neighborhood Search For The Degree-Constrained Minimum Spanning Tree Problem

paper_content:

Given an undirected graph with weights associated with its edges, the degree-constrained minimum spanning tree problem consists in finding a minimum spanning tree of the given graph, subject to constraints on node degrees. We propose a variable neighborhood search heuristic for the degree-constrained minimum spanning tree problem, based on a dynamic neighborhood model and using a variable neighborhood descent iterative improvement algorithm for local search. Computational experiments illustrating the effectiveness of the approach on benchmark problems are reported.
---
paper_title: Variable neighbourhood search for the minimum labelling Steiner tree problem

paper_content:

We present a study on heuristic solution approaches to the minimum labelling Steiner tree problem, an NP-hard graph problem related to the minimum labelling spanning tree problem. Given an undirected labelled connected graph, the aim is to find a spanning tree covering a given subset of nodes of the graph, whose edges have the smallest number of distinct labels. Such a model may be used to represent many real world problems in telecommunications and multimodal transportation networks. Several metaheuristics are proposed and evaluated. The approaches are compared to the widely adopted Pilot Method and it is shown that the Variable Neighbourhood Search that we propose is the most effective metaheuristic for the problem, obtaining high quality solutions in short computational running times.
---
paper_title: Variable neighborhood search

paper_content:

Variable neighborhood search (VNS) is a metaheuristic for solving combinatorial and global optimization problems whose basic idea is a systematic change of neighborhood both within a descent phase to find a local optimum and in a perturbation phase to get out of the corresponding valley. In this chapter we present the basic schemes of VNS and some of its extensions. We then describe a recent development, i.e., formulation space search. We then present five families of applications in which VNS has proven to be very successful: (i) exact solution of large-scale location problems by primal–dual VNS; (ii) generation of feasible solutions to large mixed integer linear programs by hybridization of VNS and local branching; (iii) generation of good feasible solutions to continuous nonlinear programs; (iv) generation of feasible solutions and/or improved local optima for mixed integer nonlinear programs by hybridization of sequential quadratic programming and branch and bound within a VNS framework, and (v) exploration of graph theory to find conjectures, refutations, and proofs or ideas of proofs.
---
paper_title: Metaheuristics in combinatorial optimization: Overview and conceptual comparison

paper_content:

The field of metaheuristics for the application to combinatorial optimization problems is a rapidly growing field of research. This is due to the importance of combinatorial optimization problems for the scientific as well as the industrial world. We give a survey of the nowadays most important metaheuristics from a conceptual point of view. We outline the different components and concepts that are used in the different metaheuristics in order to analyze their similarities and differences. Two very important concepts in metaheuristics are intensification and diversification. These are the two forces that largely determine the behavior of a metaheuristic. They are in some way contrary but also complementary to each other. We introduce a framework, that we call the I&D frame, in order to put different intensification and diversification components into relation with each other. Outlining the advantages and disadvantages of different metaheuristic approaches we conclude by pointing out the importance of hybridization of metaheuristics as well as the integration of metaheuristics and other methods for optimization.
---
paper_title: A method of solving scheduling problems using an improved guided genetic algorithm

paper_content:

In this paper, an improved guided genetic algorithm is proposed for the job-shop scheduling problem. The proposed method is improved by a genetic algorithm using multipliers which can be adjusted during the search process. Simulation results based on some benchmark problems demonstrate that the proposed method can find better solutions than the genetic algorithm and the original guided genetic algorithm. © 2010 Wiley Periodicals, Inc. Electron Comm Jpn, 93(8): 15–15, 2010; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecj.10263
---
paper_title: A genetic algorithm for the set covering problem

paper_content:

Abstract In this paper we present a genetic algorithm-based heuristic for non-unicost set covering problems. We propose several modifications to the basic genetic procedures including a new fitness-based crossover operator (fusion), a variable mutation rate and a heuristic feasibility operator tailored specifically for the set covering problem. The performance of our algorithm was evaluated on a large set of randomly generated problems. Computational results showed that the genetic algorithm-based heuristic is capable of producing high-quality solutions.
---
paper_title: A Genetic Algorithm for the Multidimensional Knapsack Problem

paper_content:

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.
---
paper_title: Combined Mutation Operators of Genetic Algorithm for the Travelling Salesman problem

paper_content:

In this study two combined mutation operators have been developed to increase the performance of Genetic Algorithm that helps to find the minimum cost in the known Travelling Salesman problem (TSP).In order to do this the combined mutation operators which are named as Inverted Exchange and Inverted Displacement are compared with four existing mutation operators. These are programmed in C++ and algorithms, ten bench mark test problems and five variations of order crossover are used. Based implemented on a set of benchmark test problems taken from the TSPLIB. The crossover operator used here is the order crossover using two of its existing and three of its new variations. In general six mutations on the numerical and graphical analysis it indicates that the Inverted Displacement has a definite supremacy over the existing four mutations except for few instances considered here. The Inversion mutation is second best performer. All optimal values found in the six mutations are obtained when the new variations of order crossover are used.
---
paper_title: Ant colony optimization techniques for the vehicle routing problem

paper_content:

Abstract This research applies the meta-heuristic method of ant colony optimization (ACO) to an established set of vehicle routing problems (VRP). The procedure simulates the decision-making processes of ant colonies as they forage for food and is similar to other adaptive learning and artificial intelligence techniques such as Tabu Search, Simulated Annealing and Genetic Algorithms. Modifications are made to the ACO algorithm used to solve the traditional traveling salesman problem in order to allow the search of the multiple routes of the VRP. Experimentation shows that the algorithm is successful in finding solutions within 1% of known optimal solutions and the use of multiple ant colonies is found to provide a comparatively competitive solution technique especially for larger problems. Additionally, the size of the candidate lists used within the algorithm is a significant factor in finding improved solutions, and the computational times for the algorithm compare favorably with other solution methods.
---
paper_title: An Improved Ant System Algorithm for the Vehicle Routing Problem

paper_content:

The Ant System is a distributed metaheuristic that combines an adaptive memory with alocal heuristic function to repeatedly construct solutions of hard combinatorial optimizationproblems. In this paper, we present an improved ant system algorithm for the Vehicle RoutingProblem with one central depot and identical vehicles. Computational results on fourteenbenchmark problems from the literature are reported and a comparison with five othermetaheuristic approaches for solving Vehicle Routing Problems is given. Copyright Kluwer Academic Publishers 1999
---
paper_title: Solving Fuzzy based Job Shop Scheduling Problems using Ga and Aco

paper_content:

In this paper, we present a genetic algorithm and ant colony optimization algorithm for solving the Job-shop Scheduling Problem (JSSP). The genetic algorithm comprises of different stages like generating the initial population, selecting the individuals for reproduction and reproducing new individuals. Ant Colony Optimization (ACO) is a metaheuristic inspired by the foraging behavior of ants, which is also used to solve this combinatorial optimization problem. In JSSP ants move from one machine (nest) to another machine (food source) depending upon the job flow, thereby optimizing the sequence of jobs. The sequence of jobs is scheduled using Fuzzy logic and optimizes using GA and ACO. The makespan, completion time, makespan efficiency, algorithmic efficiency and the elapsed time for the genetic algorithm and the ant colony algorithm are evaluated and compared. The improvement in the performance of the algorithms based on the computed parameters is also discussed in this paper. Computational results of these optimization algorithms are compared by analyzing the JSSP benchmark instances, FT10 and the ABZ10 problems.
---
paper_title: An Ant Approach to the Flow Shop Problem

paper_content:

In this article we present an Ant Colony Optimization approach to the Flow Shop Problem. ACO is a new algorithmic approach, inspired by the foraging behavior of real ants, that can be applied to the solution of combinatorial optimization problems. Artificial ants are used to construct solutions for Flow Shop Problems that subsequently are improved by a local search procedure. Comparisons with other heuristics for the Flow Shop Scheduling problem show that with our approach very promising results are obtained.
---
paper_title: An improved ant colony optimization for vehicle routing problem

paper_content:

The vehicle routing problem (VRP), a well-known combinatorial optimization problem, holds a central place in logistics management. This paper proposes an improved ant colony optimization (IACO), which possesses a new strategy to update the increased pheromone, called ant-weight strategy, and a mutation operation, to solve VRP. The computational results for fourteen benchmark problems are reported and compared to those of other metaheuristic approaches.
---
paper_title: Ant Colony Optimization and the minimum spanning tree problem

paper_content:

Ant Colony Optimization (ACO) is a kind of metaheuristic that has become very popular for solving problems from combinatorial optimization. Solutions for a given problem are constructed by a random walk on a so-called construction graph. This random walk can be influenced by heuristic information about the problem. In contrast to many successful applications, the theoretical foundation of this kind of metaheuristic is rather weak. Theoretical investigations with respect to the runtime behavior of ACO algorithms have been started only recently for the optimization of pseudo-Boolean functions. We present the first comprehensive rigorous analysis of a simple ACO algorithm for a combinatorial optimization problem. In our investigations, we consider the minimum spanning tree (MST) problem and examine the effect of two construction graphs with respect to the runtime behavior. The choice of the construction graph in an ACO algorithm seems to be crucial for the success of such an algorithm. First, we take the input graph itself as the construction graph and analyze the use of a construction procedure that is similar to Broder's algorithm for choosing a spanning tree uniformly at random. After that, a more incremental construction procedure is analyzed. It turns out that this procedure is superior to the Broder-based algorithm and produces additionally in a constant number of iterations an MST, if the influence of the heuristic information is large enough.
---
paper_title: Ant system for Job-shop Scheduling

paper_content:

The study of natural processes has inspired several heuristic optimization algorithms which have proved to be very effective in combinatorial optimization. In this paper we show how a new heuristic called ant system, in which the search task is distributed over many simple, loosely interacting agents, can be successfully applied to find good solutions of job-shop scheduling problems.
---
paper_title: Particle swarm optimization

paper_content:

A concept for the optimization of nonlinear functions using particle swarm methodology is introduced. The evolution of several paradigms is outlined, and an implementation of one of the paradigms is discussed. Benchmark testing of the paradigm is described, and applications, including nonlinear function optimization and neural network training, are proposed. The relationships between particle swarm optimization and both artificial life and genetic algorithms are described.
---
paper_title: Particle Swarm Optimization Applied To Task Assignment Problem

paper_content:

Particle Swarm Optimization (PSO) is a metaheuristic inspired on the emerging social behavior found in nature. PSO has shown good results in some recent works of discrete optimization, even though it was originally designed for continuous optimization problems. This paper models the problem of allocating a set of cabs to some customers as a combinatorial problem whose optimization goal is to minimize the distance traveled by the fleet. This problem can be categorized as a Task Assignment Problem, being optimized in this paper by two versions of the discrete PSO: the first approach that is based on a binary codification and the second one which uses permutations to encode the solution. The obtained results show that the second approach (permutation encoding) is superior than the first one (binary encoding) in terms of quality of the solutions and computational time, and it is capable of achieving the known optimal values whenever they are available.
---
paper_title: A discrete particle swarm optimization algorithm for uncapacitated facility location problem

paper_content:

A discrete version of particle swarm optimization (DPSO) is employed to solve uncapacitated facility location (UFL) problem which is one of the most widely studied in combinatorial optimization. In addition, a hybrid version with a local search is defined to get more efficient results. The results are compared with a continuous particle swarm optimization (CPSO) algorithm and two other metaheuristics studies, namely, genetic algorithm (GA) and evolutionary simulated annealing (ESA). To make a reasonable comparison, we applied to same benchmark suites that are collected from OR-library. In conclusion, the results showed that DPSO algorithm is slightly better than CPSO algorithm and competitive with GA and ESA.
---
paper_title: A Fast Particle Swarm Optimization Algorithm for Large Scale Multidimensional Knapsack Problem

paper_content:

Multidimensional knapsack problem (MKP) is very important and NP-hard. A strategy of mimetic profit/weight ratio (P/W-Rt) is proposed and accordingly, a fast particle swarm optimization algorithm is proposed. The most important merit of this strategy is that it can effectively solve MKP with arbitrary number of constraints under similar computing costs as one dimensional KP. Experiments illustrate the robust performance, efficiency, and computing costs independence with instance scale.
---
paper_title: A Modified Binary Particle Swarm Optimization Algorithm for Permutation Flow Shop Problem

paper_content:

In this paper, we proposed a modified version of binary particle swarm optimization algorithm (MBPSO) to solve combinatorial optimization problems. All particles are initialized as random binary vectors, and the Smallest Position Value (SPV) rule is used to construct a mapping from binary space to the permutation space. We also propose new formula to update the particles' velocities and positions. The algorithm is then applied to the permutation flow shop problem (PFSP). To avoid the stagnation, local search and perturbation are employed to improve the performance. Performance of the proposed algorithm is evaluated using the benchmarks of flow shop scheduling problems given by Taillard, (1993). Experimental results show that the algorithm with local search and perturbation is more effective.
---
paper_title: A hybrid Particle Swarm Optimization algorithm for combinatorial optimization problems

paper_content:

Particle Swarm Optimization (PSO) belongs to a class of algorithms inspired by natural social intelligent behaviors, called Swarm Intelligence (SI). PSO has been successfully applied to solve continuous optimization problems, however, its potential in discrete problems has not been sufficiently explored. Recent works have proposed hybridization of PSO using local search and Path relinking algorithms with promising results. This paper aims to present a hybrid PSO algorithm that uses local search and Path relinking too, but differently to the previous approaches, this works maintains the main PSO concept for the update of the velocity of the particle. The paper describes the proposed algorithm and a set of experiments with the Traveling Salesman Problem (TSP). The results are compared to other Particle Swarm Optimization algorithms presented previously for the same problem. The results are encouraging and reinforce the idea that PSO algorithms can also provide good results when dealing with discrete problems.
---
paper_title: Discrete Particle Swarm Optimization for the minimum labelling Steiner tree problem

paper_content:

Particle Swarm Optimization is a population-based method inspired by the social behaviour of individuals inside swarms in nature. Solutions of the problem are modelled as members of the swarm which fly in the solution space. The improvement of the swarm is obtained from the continuous movement of the particles that constitute the swarm submitted to the effect of inertia and the attraction of the members who lead the swarm. This work focuses on a recent Discrete Particle Swarm Optimization for combinatorial optimization, called Jumping Particle Swarm Optimization. Its effectiveness is illustrated on the minimum labelling Steiner tree problem: given an undirected labelled connected graph, the aim is to find a spanning tree covering a given subset of nodes, whose edges have the smallest number of distinct labels.
---
paper_title: Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem

paper_content:

Capacitated vehicle routing problem (CVRP) is an NP-hard problem. For large-scale problems, it is quite difficult to achieve an optimal solution with traditional optimization methods due to the high computational complexity. A new hybrid approximation algorithm is developed in this work to solve the problem. In the hybrid algorithm, discrete particle swarm optimization (DPSO) combines global search and local search to search for the optimal results and simulated annealing (SA) uses certain probability to avoid being trapped in a local optimum. The computational study showed that the proposed algorithm is a feasible and effective approach for capacitated vehicle routing problem, especially for large scale problems.
---
paper_title: Particle swarm optimization algorithm for single machine total weighted tardiness problem

paper_content:

In This work we present a particle swarm optimization algorithm to solve the single machine total weighted tardiness problem. A heuristic rule, the smallest position value (SPV) rule, is developed to enable the continuous particle swarm optimization algorithm to be applied to all classes of sequencing problems, which are NP-hard in the literature. A simple but very efficient local search method is embedded in the particle swarm optimization algorithm. The computational results show that the particle swarm algorithm is able to find the optimal and best-known solutions on all instances of widely used benchmarks from the OR library.
---
paper_title: Variable neighbourhood decomposition search for 0-1 mixed integer programs

paper_content:

In this paper we propose a new hybrid heuristic for solving 0-1 mixed integer programs based on the principle of variable neighbourhood decomposition search. It combines variable neighbourhood search with a general-purpose CPLEX MIP solver. We perform systematic hard variable fixing (or diving) following the variable neighbourhood search rules. The variables to be fixed are chosen according to their distance from the corresponding linear relaxation solution values. If there is an improvement, variable neighbourhood descent branching is performed as the local search in the whole solution space. Numerical experiments have proven that exploiting boundary effects in this way considerably improves solution quality. With our approach, we have managed to improve the best known published results for 8 out of 29 instances from a well-known class of very difficult MIP problems. Moreover, computational results show that our method outperforms the CPLEX MIP solver, as well as three other recent most successful MIP solution methods.
---
paper_title: Hybrid metaheuristics with evolutionary algorithms specializing in intensification and diversification: Overview and progress report

paper_content:

Nowadays, a promising way to obtain hybrid metaheuristics concerns the combination of several search algorithms with strong specialization in intensification and/or diversification. The flexible architecture of evolutionary algorithms allows specialized models to be obtained with the aim of providing intensification and/or diversification. The outstanding role that is played by evolutionary algorithms at present justifies the choice of their specialist approaches as suitable ingredients to build hybrid metaheuristics. This paper focuses on hybrid metaheuristics with evolutionary algorithms specializing in intensification and diversification. We first give an overview of the existing research on this topic, describing several instances grouped into three categories that were identified after reviewing specialized literature. Then, with the aim of complementing the overview and providing additional results and insights on this line of research, we present an instance that consists of an iterated local search algorithm with an evolutionary perturbation technique. The benefits of the proposal in comparison to other iterated local search algorithms proposed in the literature to deal with binary optimization problems are experimentally shown. The good performance of the reviewed approaches and the suitable results shown by our instance allow an important conclusion to be achieved: the use of evolutionary algorithms specializing in intensification and diversification for building hybrid metaheuristics becomes a prospective line of research for obtaining effective search algorithms.
---
paper_title: GRASP and path relinking for the max–min diversity problem

paper_content:

The max-min diversity problem (MMDP) consists in selecting a subset of elements from a given set in such a way that the diversity among the selected elements is maximized. The problem is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in the social and biological sciences. We propose a heuristic method-based on the GRASP and path relinking methodologies-for finding approximate solutions to this optimization problem. We explore different ways to hybridize GRASP and path relinking, including the recently proposed variant known as GRASP with evolutionary path relinking. Empirical results indicate that the proposed hybrid implementations compare favorably to previous metaheuristics, such as tabu search and simulated annealing.
---
paper_title: Iterated Local Search for the Quadratic Assignment Problem

paper_content:

Iterated local search (ILS) is a simple and powerful stochastic local search method. This article presents and analyzes the application of ILS to the quadratic assignment problem (QAP). We justify the potential usefulness of an ILS approach to this problem by an analysis of the QAP search space. However, an analysis of the run-time behavior of a basic ILS algorithm reveals a stagnation behavior which strongly compromises its performance. To avoid this stagnation behavior, we enhance the ILS algorithm using acceptance criteria that allow moves to worse local optima and we propose population-based ILS extensions. An experimental evaluation of the enhanced ILS algorithms shows their excellent performance when compared to other state-of-the-art algorithms for the QAP.
---
paper_title: Heuristic manipulation, tabu search and frequency assignment

paper_content:

Heuristic manipulation attempts to modify the search space of an optimization problem, using information provided by an underlying heuristic method. In this paper it is applied in combination with tabu search to the fixed spectrum frequency assignment problem. The frequency assignment problem involves the assignment of discrete channels (or frequencies) to the transmitters of a radio network, such as a mobile telephone network. Frequency separation is necessary to avoid interference by other transmitters to the signal received from the wanted transmitter at the reception points. Unnecessary separation causes an excess requirement for spectrum. Good assignments minimize interference and the spectrum required. In fixed spectrum frequency assignment the frequency spectrum available is given and the target is to minimize the interference in the network. Computational experiments confirm that the manipulation technique is able to drive the underlying tabu search algorithm towards improved solutions.
---
paper_title: Using constraint programming and local search methods to solve vehicle routing problems

paper_content:

We use a local search method we term Large Neighbourhood Search (LNS) to solve vehicle routing problems. LNS is analogous to the shuffling technique of job-shop scheduling, and so meshes well with constraint programming technology. LNS explores a large neighbourhood of the current solution by selecting a number of related customer visits to remove from the set of planned routes, and re-inserting these visits using a constraint-based tree search. Unlike similar methods, we use Limited Discrepancy Search during the tree search to re-insert visits. We analyse the performance of our method on benchmark problems. We demonstrate that results produced are competitive with Operations Research meta-heuristic methods, indicating that constraint-based technology is directly applicable to vehicle routing problems.
---
paper_title: Solution-Guided Multi-Point Constructive Search for Job Shop Scheduling

paper_content:

Solution-Guided Multi-Point Constructive Search (SGMPCS) is a novel constructive search technique that performs a series of resource-limited tree searches where each search begins either from an empty solution (as in randomized restart) or from a solution that has been encountered during the search. A small number of these"elite solutions is maintained during the search. We introduce the technique and perform three sets of experiments on the job shop scheduling problem. First, a systematic, fully crossed study of SGMPCS is carried out to evaluate the performance impact of various parameter settings. Second, we inquire into the diversity of the elite solution set, showing, contrary to expectations, that a less diverse set leads to stronger performance. Finally, we compare the best parameter setting of SGMPCS from the first two experiments to chronological backtracking, limited discrepancy search, randomized restart, and a sophisticated tabu search algorithm on a set of well-known benchmark problems. Results demonstrate that SGMPCS is significantly better than the other constructive techniques tested, though lags behind the tabu search.
---
paper_title: Hybrids of Constructive Metaheuristics and Constraint Programming: A Case Study with ACO

paper_content:

The securing and sealing of a connector 10 to a pipe 12 for a hydraulic connection comprises a pre-assembly step wherein a cutting/clamping ring 34 is secured to the pipe and a final assembly step wherein the ring 34 is sealed to a connector body 14. The axial force applied by a nut 20 to the ring 34 during the final assembly step is less than the axial force applied to the ring 34 during the pre-assembly step whereby no further cutting of the teeth 40 into the pipe is permitted but sealing takes place between cooperating conical surfaces 22 and 36 of the connector body and cutting/clamping ring respectively.
---
paper_title: Integration of ACO in a Constraint Programming Language

paper_content:

We propose to integrate ACO in a Constraint Programming (CP) language. Basically, we use the CP language to describe the problem to solve by means of constraints and we use the CP propagation engine to reduce the search space and check constraint satisfaction; however, the classical backtrack search of CP is replaced by an ACO search. We report first experimental results on the car sequencing problem and compare different pheromone strategies for this problem.
---
paper_title: Beam-ACO for the travelling salesman problem with time windows

paper_content:

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.
---
paper_title: An Evolutionary Algorithm for Polishing Mixed Integer Programming Solutions

paper_content:

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.
---
paper_title: Nested Partitions Method for Global Optimization

paper_content:

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.
---
paper_title: On the Hybridization of Memetic Algorithms With Branch-and-Bound Techniques

paper_content:

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
---
paper_title: An Integer Linear Programming Approach and a Hybrid Variable Neighborhood Search for the Car Sequencing Problem

paper_content:

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.
---
paper_title: Improved results on the 0-1 multidimensional knapsack problem

paper_content:

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.
---
paper_title: Combining Lagrangian decomposition with an evolutionary algorithm for the knapsack constrained maximum spanning tree problem

paper_content:

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.
---
paper_title: A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem

paper_content:

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%.
---
paper_title: An improved hybrid genetic algorithm for the generalized assignment problem

paper_content:

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.
---
paper_title: A Genetic Algorithm for the Multidimensional Knapsack Problem

paper_content:

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.
---
paper_title: Guiding ACO by problem relaxation: a case study on the symmetric TSP

paper_content:

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.
---
paper_title: A dynamic programming based heuristic for the assembly line balancing problem

paper_content:

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.
---
paper_title: Effective neighborhood structures for the generalized traveling salesman problem

paper_content:

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.
---
paper_title: A Hybrid Genetic Algorithm for the Dynamic Plant Layout Problem

paper_content:

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.
---
paper_title: Tabu search: global intensification using dynamic programming

paper_content:

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.
---
paper_title: An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem

paper_content:

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.
---

Title: Survey of Metaheuristic Algorithms for Combinatorial Optimization

Section 1: INTRODUCTION
Description 1: This section introduces the concept of optimization, various types of optimization problems, and focuses particularly on combinatorial optimization problems, their characteristics, and how they can be approached.

Section 2: TRAJECTORY METHODS
Description 2: This section outlines metaheuristics known as trajectory methods, which work on a single solution, and provides an introduction and survey of various types of these methods.

Section 2.1: Simulated Annealing
Description 2.1: A subsection detailing the development of simulated annealing, its principles, modifications, and applications in optimization problems.

Section 2.2: Tabu Search
Description 2.2: A subsection that discusses the tabu search algorithm, including its mechanisms, enhancements, and real-world applications.

Section 2.3: Greedy Randomized Adaptive Search Procedure
Description 2.3: This subsection explains the GRASP methodology, how it operates, and reviews of its usage in different applications.

Section 2.4: Variable Neighborhood Search
Description 2.4: An explanation of variable neighborhood search, its basic concepts, variants, and its practical applications in solving optimization problems.

Section 3: POPULATION BASED METAHEURISTICS
Description 3: This section discusses metaheuristics that work explicitly with a set of solutions, detailing how different solutions are merged to create new solutions.

Section 3.1: Genetic Algorithms
Description 3.1: A subsection that provides an overview of genetic algorithms, their mechanisms based on natural selection, and their application across various problems.

Section 3.2: Ant Colony Optimization
Description 3.2: This subsection describes ant colony optimization, its inspiration from real ants' behavior, and its application to optimization problems.

Section 3.3: Particle Swarm Optimization
Description 3.3: An overview of particle swarm optimization, inspired by social behavior of bird flocking, and its application to different combinatorial optimization problems.

Section 4: HYBRID METHODS
Description 4: This section covers the hybridization of different metaheuristic algorithms with other optimization methods to achieve enhanced performance.

Section 4.1: Hybridizing Metaheuristic With (Meta-) Heuristics
Description 4.1: Describes the integration of metaheuristics with heuristic or other metaheuristic methods and reviews various examples from the literature.

Section 4.2: Hybridizing Metaheuristic With Constraint Programming
Description 4.2: This subsection explains the combination of metaheuristics with constraint programming techniques to handle specific optimization problems more effectively.

Section 4.3: Hybridizing Metaheuristic With Tree Search Technique
Description 4.3: Discusses the hybridization of metaheuristics with tree search techniques like branch and bound for optimization challenges.

Section 4.4: Hybridizing Metaheuristic With Problem Relaxation
Description 4.4: Focuses on hybrid methods involving problem relaxation techniques to solve complex optimization problems more efficiently.

Section 4.5: Hybridization Metaheuristic With Dynamic Programming
Description 4.5: Covers the integration of dynamic programming with metaheuristics, enhancing the ability to explore large neighborhoods efficiently.

Section 5: CONCLUSIONS
Description 5: This section summarizes the survey, emphasizing the effectiveness of trajectory, population-based, and hybrid metaheuristics in solving combinatorial optimization problems. It also discusses various issues researchers should consider when developing metaheuristic algorithms.