Tabu Search directed by direct search methods for nonlinear global optimization

In recent years, there has been a great deal of interest in metaheuristics in the optimization community. Tabu Search (TS) represents a popular class of metaheuristics. However, compared with other metaheuristics like genetic algorithm and simulated annealing, contributions of TS that deals with continuous problems are still very limited. In this paper, we introduce a continuous TS called Directed Tabu Search (DTS) method. In the DTS method, direct-search-based strategies are used to direct a tabu search. These strategies are based on the well-known Nelder–Mead method and a new pattern search procedure called adaptive pattern search. Moreover, we introduce a new tabu list conception with anti-cycling rules called Tabu Regions and Semi-Tabu Regions. In addition, Diversification and Intensification Search schemes are employed. Numerical results show that the proposed method is promising and produces high quality solutions.     

Continuous ant colony system and tabu search algorithms hybridized for global minimization of continuous multi-minima functions

A new hybrid optimization method, combining Continuous Ant Colony System (CACS) and Tabu Search (TS) is proposed for minimization of continuous multi-minima functions. The new algorithm incorporates the concepts of promising list, tabu list and tabu balls from TS into the framework of CACS. This enables the resultant algorithm to avoid bad regions and to be guided toward the areas more likely to contain the global minimum. New strategies are proposed to dynamically tune the radius of the tabu balls during the execution and also to handle the variable correlations. The promising list is also used to update the pheromone distribution over the search space. The parameters of the new method are tuned based on the results obtained for a set of standard test functions. The results of the proposed scheme are also compared with those of some recent ant based and non-ant based meta-heuristics, showing improvements in terms of accuracy and efficiency.     

Tabu Search for the planar three-index assignment problem

Tabu Search is a very effective method for approximately solving hard combinatorial problems. In the current work we implement Tabu Search for solving the Planar Three-Index Assignment Problem. The problem deals with finding the minimum cost assignment between elements of three distinct sets demanding that every pair of elements, each representing a different set, appears in the same solution exactly once. The solutions of the problems correspond to Latin squares. These structures form the basis of the move generation mechanism employed by the Tabu Search procedures. Standard Tabu Search ideas such as candidate move list, variable tabu list size, and frequency-based memory are tested. Computational results for a range of problems of varying dimensions are presented.     

Tabu Search with Simple Ejection Chains for Coloring Graphs

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

“MOSS” multiobjective scatter search applied to non-linear multiple criteria optimization

This paper introduces a multiple criteria scatter search to deal with bounded constrained non-linear continuous vector optimization problems of high dimension, applying a MultiStart Tabu Search (TS) as a diversification generation method, each TS works with its own starting point, recency memory, and aspiration threshold. Frequency memory is used to diversify the search and it is shared between the TS. A Pareto relation is applied in order to designate a subset of the best generated solutions to be reference solutions. A choice function called Kramer Choice function is used to divide the reference solutions in two subsets. The Euclidean distance is used as a measure of dissimilarity in order to find diverse solutions to be combined. Linear combinations of the reference solutions are used as a solution combination method. “Balls” in the decision space and the objective space are used to avoid duplications. Different tabu sets with different tabu tenures are employed in the scatter phase to enhance the diversity of the search. The performance of our approach is compared with Pareto-optimal frontiers and three other state-of-the-art MOEAs for a suite test problems taken from the literature.     

An IP-based heuristic for the post enrolment course timetabling problem of the ITC2007

Track 2 of the international timetabling competition 2007 was a post enrolment course timetabling problem. A set of events has to be assigned to a timeslot and to a room such that all students are able to attend their requested events while not violating the hard constraints. There are also soft constraints that make the timetable “nicer”.     

On the Convergence of Tabu Search

The Tabu Search (TS) meta-heuristic has proved highly successful for solving combinatorial and nonlinear problems. A key aspect of TS consists of using adaptive forms of memory to forbid the search process to revisit solutions already examined unless the trajectory to reach it is different. In Glover (ORSA Journal on Computing, 1990, 2, 4–32) a special memory design was proposed together with a choice rule for handling the situation where the method was compelled to revisit solutions already encountered. This proposal, which specified the exploration should resume from the earliest solution visited in the past, as accompanied by the conjecture that such a choice has implications for finiteness in the zero-one integer program and optimal set membership examples. Up to now numerous applications of TS in various areas of research are available, however, we are aware of only a few results concerning the convergence of TS. In this paper, we prove that Glover's conjecture is true if the neighborhood employed is strongly connected, yielding a reversible path from each solution to every other solution.     

Comparison of metaheuristic algorithms for Examination Timetabling Problem

SA, TS, GA and ACS are four of the main algorithms for solving challenging problems of intelligent systems. In this paper we consider Examination Timetabling Problem that is a common problem for all universities and institutions of higher education. There are many methods to solve this problem, In this paper we use Simulated Annealing, Tabu Search, Genetic Algorithm and Ant Colony System in their basic frameworks for solving this problem and compare results of them with each other.     

Combinatorial Groupoids,Cubical Complexes,and the Lovász Conjecture

This paper lays the foundation for a theory of combinatorial groupoids that allows us to use concepts like “holonomy”, “parallel transport”, “bundles”, “combinatorial curvature”, etc. in the context of simplicial (polyhedral) complexes, posets, graphs, polytopes and other combinatorial objects. We introduce a new, holonomy-type invariant for cubical complexes, leading to a combinatorial “Theorema Egregium” for cubical complexes that are non-embeddable into cubical lattices. Parallel transport of Hom-complexes and maps is used as a tool to extend Babson–Kozlov–Lovász graph coloring results to more general statements about nondegenerate maps (colorings) of simplicial complexes and graphs. The author was supported by grants 144014 and 144026 of the Serbian Ministry of Science and Technology.     

Optimizing base station location and configuration in UMTS networks

Radio planning and coverage optimization are critical issues when deploying and expanding third generation cellular systems. We investigate mixed integer programming models for locating and configuring base stations in UMTS networks so as to maximize coverage and minimize installation costs. The overall model considers both uplink and downlink directions, that we studied separately in Amaldi et al. (2002, 2003b). The two-stage Tabu Search algorithm we propose exploits solutions of a simplified model for the uplink direction to drastically reduce the computational time required to find good approximate solutions of the overall uplink and downlink model.Computational results obtained for realistic instances %with voice as well as data traffic are reported and discussed. Research carried out within the national project “Optimization, simulation and complexity in the design and management of telecommunication networks”funded by the Italian Ministry of Education, University and Scientific Research (MIUR).     

A supernodal formulation of vertex colouring with applications in course timetabling

For many problems in scheduling and timetabling, the choice of a mathematical programming formulation is determined by the formulation of the graph colouring component. This paper briefly surveys seven known integer programming formulations of vertex colouring and introduces a new approach using “supernodes”.     

Solving TSP by considering processing time: Meta-heuristics and fuzzy approaches

In this paper, general properties of traveling salesman problem has been illustrated, then a model has been introduced to minimize Make-span (time interval which all of jobs will be done) with considering sequence-dependence setup times and processing time. Furthermore, fuzzy sets and its characteristics are applied to a Hard-solvable traveling salesman problem with considering processing times. As it can be seen, traveling salesman problems are NP-hard, so solving problem in huge dimensions is uncontrollably manageable and in other side these kinds of problems in real-world are unavoidable, so a local search can prove their importance. (However this Meta-heuristic methods may not reveal exact optimal solution, but they yield a near-exact optimal solution in undeniable reduced computational time). Here, some of most famous local searches have been explained in their common and normal form, which are Genetic Algorithm (GA), Tabu Search (TS), Simulated Annealing (SA), Ant Colony System (ACO). In rest, a comprehensive comparison through these methods has been shown. This normality in methods structure could help the article to hold no-side-taken and acceptable judgments. In final, point methods analysis and parameter tuning are held.     

Diversification-driven tabu search for unconstrained binary quadratic problems

This paper describes a Diversification-Driven Tabu Search (D²TS) algorithm for solving unconstrained binary quadratic problems. D²TS is distinguished by the introduction of a perturbation-based diversification strategy guided by long-term memory. The performance of the proposed algorithm is assessed on the largest instances from the ORLIB library (up to 2500 variables) as well as still larger instances from the literature (up to 7000 variables). The computational results show that D²TS is highly competitive in terms of both solution quality and computational efficiency relative to some of the best performing heuristics in the literature.     

Polynomial Approximation of Functions: Historical Perspective and New Tools

This paper examines the effect of applying symbolic computation and graphics to enhance students' ability to move from a visual interpretation of mathematical concepts to formal reasoning. The mathematics topics involved, Approximation and Interpolation, were taught according to their historical development, and the students tried to follow the thinking process of the creators of the theory. They used a Computer Algebra System to manipulate algebraic expressions and generate a wide variety of dynamic graphics; thus21st century technology was applied in order to “walk” with the students from the period of Euler in 1748 to the period of Runge in 1901. We describe some situations in which the combination of dynamic graphics,algorithms, and historical perspective enabled the students to improve their understanding of concepts such as limit, convergence, and the quality of approximation. This revised version was published online in July 2006 with corrections to the Cover Date.     

A hybrid method combining continuous tabu search and Nelder–Mead simplex algorithms for the global optimization of multiminima functions

Tabu search (TS) is a metaheuristic, which proved efficient to solve various combinatorial optimization problems. However, few works deal with its application to the global minimization of functions depending on continuous variables. To perform this task, we propose an hybrid method combining tabu search and simplex search (SS). TS allows to cover widely the solution space, to stimulate the search towards solutions far from the current solution, and to avoid the risk of trapping into a local minimum. SS is used to accelerate the convergence towards a minimum. The Nelder–Mead simplex algorithm is a classical very powerful local descent algorithm, making no use of the objective function derivatives. A “simplex” is a geometrical figure consisting, in n-dimensions, of (n+1) points. If any point of a simplex is taken as the origin, the n other points define vector directions that span the n-dimension vector space. Through a sequence of elementary geometric transformations (reflection, contraction and extension), the initial simplex moves, expands or contracts. To select the appropriate transformation, the method only uses the values of the function to be optimized at the vertices of the simplex considered. After each transformation, the current worst vertex is replaced by a better one. Our algorithm called continuous tabu simplex search (CTSS) implemented in two different forms (CTSS_single, CTSS_multiple) is made up of two steps: first, an adaptation of TS to continuous optimization problems, allowing to localize a “promising area”; then, intensification within this promising area, involving SS. The efficiency of CTSS is extensively tested by using analytical test functions of which global and local minima are known. A comparison is proposed with several variants of tabu search, genetic algorithms and simulated annealing. CTSS is applied to the design of a eddy current sensor aimed at non-destructive control.     

A Tabu Search Approach for the Resource Constrained Project Scheduling Problem

An appropriate tabu search implementation is designed to solve the resource constrained project scheduling problem. This approach uses well defined move strategies and a structured neighbourhood, defines appropriate tabu status and tenure and takes account of objective function approximation to speed up the search process. A sound understanding of the problem has helped in many ways in designing and enhancing the tabu search methodology. The method uses diversification, intensification and handles infeasibility via strategic oscillation.The above methodology is tested on existing problems from the literature and also on parametrically generated problems with encouraging results. For comparison of results, optimal solutions are used in the former and lower bounds obtained by Lagrangian heuristics are used in the latter.     

Optimal location and optimized parameters for robust power system stabilizer using honeybee mating optimization

A honeybee mating optimization technique is used to tune the power system stabilizer (PSS) parameters and find optimal location of PSSs in this article. The PSS parameters and placement are computed to assure maximum damping performance under different operating conditions. One of the main advantages of the proposed approach is its robustness to the initial parameter settings. The effectiveness of the proposed method is demonstrated on two case studies as; 10‐machine 39‐buses New England (NE) power system in comparison with Tabu Search (TS) and 16 machines and 68 buses‐modified reduced order model of the NE New York interconnected system by genetic algorithm through some performance indices under different operating condition. The proposed method of tuning the PSS is an attractive alternative to conventional fixed gain stabilizer design as it retains the simplicity of the conventional PSS and at the same time guarantees a robust acceptable performance over a wide range of operating and system condition. © 2014 Wiley Periodicals, Inc. Complexity 21: 242–258, 2015     

A two-pheromone trail ant colony system—tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products

This paper considers a practical variant of the Vehicle Routing Problem (VRP) known as the Heterogeneous Vehicle Routing Problem with Time Windows and Multiple Products (HVRPTWMP). As the problem is NP-hard, the resolution approach proposed here is a sequential Ant Colony System (ACS)—Tabu Search algorithm. The approach introduces a two pheromone trail strategy to accelerate agents’ (ants) learning process. Its convergence to good solutions is given in terms of fleet size and travel time while completing tours and service to all customers. The proposed procedure uses regency and frequency memories form Tabu Search to further improve the quality of solutions. Experiments are carried out using instances from literature and show the effectiveness of this procedure.