Assigning students to course sections using tabu search

In this paper we describe a new student registration system which has been developed at the University of Valencia, Spain. The system has two steps. First, the students make a computer-aided course selection from the courses available at the University. Thereafter, an assignment procedure allocates students to sections in order to respect two criteria: to provide the students with satisfactory schedules and to get balanced section enrollments. The assignment process has two phases. In Phase I, we obtain a set of the best solutions for each student. The algorithm is based on the construction of maximum cardinality independent sets. In Phase II, these solution sets are put together and a tabu search algorithm looks for a satisfactory balance between course sections without causing the solution obtained for each student to worsen significantly. The system was used at the beginning of the academic year 1996/97 in the Faculty of Mathematics and could be extended in the near future to the rest of the University. This revised version was published online in June 2006 with corrections to the Cover Date.     

Dynamic tabu search strategies for the traveling purchaser problem

Tabu search is a metastrategy for guiding known heuristics to overcome local optimality with a large number of successful applications reported in the literature. In this paper we investigate two dynamic strategies, the reverse elimination method and the cancellation sequence method. The incorporation of strategic oscillation as well as a combination of these methods are developed. The impact of the different methods is shown with respect to the traveling purchaser problem, a generalization of the classical traveling salesman problem. The traveling purchaser problem is the problem of determining a tour of a purchaser buying several items in different shops by minimizing the total amount of travel and purchase costs. A comparison of the tabu search strategies with a simulated annealing approach is presented, too.     

Solving the frequency assignment problem with polarization by local search and tabu

In the Frequency Assignment Problem with Polarization (FAPP), a given set of links must each be assigned a frequency and a polarization, while respecting given radio-electric compatibility constraints defined on pairs of links. In this paper, we propose a tabu search algorithm for the FAPP. A specialized neighborhood is proposed for the problem. Other key features of the algorithm are an adaptive technique to adjust the tabu tenure, an original diversification technique, and a pre-processing procedure based on arc-consistency techniques. The algorithm is tested on the 40 instances of the ROADEF Challenge 2001. It reaches the best known feasibility level for all instances and finds or improves on the best known solutions of the Challenge for a majority of the instances.Received: July 2003 / Revised version: September 2004MSC classification: 90B18, 68T20All correspondence to: Philippe Galinier     

Lower bounding and tabu search procedures for the frequency assignment problem with polarization constraints

The problem retained for the ROADEF’2001 international challenge was a Frequency Assignment Problem with polarization constraints (FAPP). This NP-hard problem was proposed by the CELAR of the French Department of Defense, within the context of the CALMA project. Twenty seven competitors took part to this contest, and we present in this paper the contribution of our team that allowed us to be selected as one of the six finalists qualified for the final round of the competition.There is typically no solution satisfying all constraints of the FAPP. For this reason, some electromagnetic compatibility constraints can be progressively relaxed, and the objective is to find a feasible solution with the lowest possible level of relaxation. We have developed a procedure that computes a lower bound on the best possible level of relaxation, as well as two tabu search algorithms for the FAPP, one for the frequency assignment, and one for the polarization assignment.Received: July 2003, Revised: October 2004, AMS classification: 90C27, 90C35, 90C59Alain Hertz: Correspondence to     

A user's guide to tabu search

We describe the main features of tabu search, emphasizing a perspective for guiding a user to understand basic implementation principles for solving combinatorial or nonlinear problems. We also identify recent developments and extensions that have contributed to increasing the efficiency of the method. One of the useful aspects of tabu search is the ability to adapt a rudimentary prototype implementation to encompass additional model elements, such as new types of constraints and objective functions. Similarly, the method itself can be evolved to varying levels of sophistication. We provide several examples of discrete optimization problems to illustrate the strategic concerns of tabu search, and to show how they may be exploited in various contexts. Our presentation is motivated by the emergence of an extensive literature of computational results, which demonstrates that a well-tuned implementation makes it possible to obtain solutions of high quality for difficult problems, yielding outcomes in some settings that have not been matched by other known techniques.The research of this paper has been supported in part by the joint Air Force Office of Scientific Research and Office of Naval Research Contract No. F49620-90-C-0033, at the University of Colorado and by the Swiss National Research Council Grant No. 20-27926.89.     

A tabu thresholding algorithm for arc crossing minimization in bipartite graphs

Acyclic directed graphs are commonly used to model complex systems. The most important criterion to obtain a readable map of an acyclic graph is that of minimizing the number of arc crossings. In this paper, we present a heuristic for solving the problem of minimizing the number of arc crossings in a bipartite graph. It consists of a novel and easier implementation of fundamental tabu search ideas without explicit use of memory structures (a tabu thresholding approach). Computational results are reported on a set of 250 randomly generated test problems. Our algorithm has been compared with the two best heuristics published in the literature and with the optimal solutions for the test problems, size permitting.This research was partially supported by the C.I.C.Y.T. with code tap92-0639.     

Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem

The vehicle routing problem (VRP) under capacity and distance restrictions involves the design of a set of minimum cost delivery routes, originating and terminating at a central depot, which services a set of customers. Each customer must be supplied exactly once by one vehicle route. The total demand of any vehicle must not exceed the vehicle capacity. The total length of any route must not exceed a pre-specified bound. Approximate methods based on descent, hybrid simulated annealing/tabu search, and tabu search algorithms are developed and different search strategies are investigated. A special data structure for the tabu search algorithm is implemented which has reduced notably the computational time by more than 50%. An estimate for the tabu list size is statistically derived. Computational results are reported on a sample of seventeen bench-mark test problems from the literature and nine randomly generated problems. The new methods improve significantly both the number of vehicles used and the total distances travelled on all results reported in the literature.     

A tabu search algorithm for scheduling pharmaceutical packaging operations

This paper addresses a practical scheduling problem arising in the packaging department of a pharmaceutical industrial plant. The problem is modeled as a multi-purpose machine scheduling problem with setup and removal times, release and due dates and additional constraints related to the scarce availability of tools and human operators. The objective functions are minimization of makespan and maximum tardiness in lexicographic order. Representing a solution with a directed graph allows us to devise an effective tabu search algorithm to solve the problem. Computational experiments, carried on real and randomly generated instances, show the effectiveness of this approach.     

A tabu search algorithm for solving economic lot scheduling problem

The economic lot scheduling problem has driven considerable amount of research. The problem is NP-hard and recent research is focused on finding heuristic solutions rather than searching for optimal solutions. This paper introduces a heuristic method using a tabu search algorithm to solve the economic lot scheduling problem. Diversification and intensification schemes are employed to improve the efficiency of the proposed Tabu search algorithm. Experimental design is conducted to determine the best operating parameters for the Tabu search. Results show that the tabu search algorithm proposed in this paper outperforms two well known benchmark algorithms.     

A tabu search algorithm for a two-dimensional non-guillotine cutting problem

In this paper we study a two-dimensional non-guillotine cutting problem, the problem of cutting rectangular pieces from a large stock rectangle so as to maximize the total value of the pieces cut. The problem has many industrial applications whenever small pieces have to be cut from or packed into a large stock sheet. We propose a tabu search algorithm. Several moves based on reducing and inserting blocks of pieces have been defined. Intensification and diversification procedures, based on long-term memory, have been included. The computational results on large sets of test instances show that the algorithm is very efficient for a wide range of packing and cutting problems.     

Solving real-life vehicle routing problems efficiently using tabu search

This paper presents a tabu search based method for finding good solutions to a real-life vehicle routing problem. The problem considered deals with some new features beyond those normally associated with the classical problems of the literature: in addition to capacity constraints for vehicles and time windows for deliveries, it takes the heterogeneous character of the fleet into account, in the sense that utilization costs are vehicle-dependent and that some accessibility restrictions have to be fulfilled. It also deals with the use of trailers. In spite of the intricacy of the problem, the proposed tabu search approach is easy to implement and can be easily adapted to many other applications. An emphasis is placed on means that have to be used to speed up the search. In a few minutes of computation on a personal workstation, our approach obtains solutions that are significantly better than those previously developed and implemented in practice.     

Solving the maximum clique problem using a tabu search approach

We describe two variants of a tabu search heuristic, a deterministic one and a probabilistic one, for the maximum clique problem. This heuristic may be viewed as a natural alternative implementation of tabu search for this problem when compared to existing ones. We also present a new random graph generator, the -generator, which produces graphs with larger clique sizes than comparable ones obtained by classical random graph generating techniques. Computational results on a large set of test problems randomly generated with this new generator are reported and compared with those of other approximate methods.The authors are grateful to the Quebec Government (Fonds F.C.A.R.) and to the Canadian Natural Sciences and Engineering Research Council (grant 0GP0038816) for financial support.     

A tabu search algorithm for maximum parsimony phylogeny inference

Phylogeny reconstruction is too complex a combinatorial problem for an exhaustive search, because the number of possible solutions increases exponentially with the number of taxa involved. In this paper, we adopt the parsimony principle and design a tabu search algorithm for finding a most parsimonious phylogeny tree. A special array structure is employed to represent the topology of trees and to generate the neighboring trees. We test the proposed tabu search algorithm on randomly selected data sets obtained from nuclear ribosomal DNA sequence data. The experiments show that our algorithm explores fewer trees to reach the optimal one than the commonly used program “dnapenny” (branch-and-bound based) while it generates much more accurate results than the default options of the program “dnapars” (heuristic search based). The percentage of search space needed to find the best solution for our algorithm decreased rapidly as the number of taxa increased. For a 20-taxon phylogeny problem, it needs on average to examine only 3.92 × 10⁻¹⁵% of the sample space.     

A tabu search heuristic using genetic diversification for the clustered traveling salesman problem

The clustered traveling salesman problem is an extension of the classical traveling salesman problem where the set of vertices is partitioned into clusters. The objective is to find a least cost Hamiltonian cycle such that the vertices of each cluster are visited contiguously and the clusters are visited in a prespecified order. A tabu search heuristic is proposed to solve this problem. This algorithm periodically restarts its search by merging two elite solutions to form a new starting solution (in a manner reminiscent of genetic algorithms). Computational results are reported on sets of Euclidean problems with different characteristics.     

The continuous reactive tabu search: Blending combinatorial optimization and stochastic search for global optimization

A novel algorithm for the global optimization of functions (C-RTS) is presented, in which a combinatorial optimization method cooperates with a stochastic local minimizer. The combinatorial optimization component, based on the Reactive Tabu Search recently proposed by the authors, locates the most promising boxes, in which starting points for the local minimizer are generated. In order to cover a wide spectrum of possible applications without user intervention, the method is designed with adaptive mechanisms: the box size is adapted to the local structure of the function to be optimized, the search parameters are adapted to obtain a proper balance of diversification and intensification. The algorithm is compared with some existing algorithms, and the experimental results are presented for a variety of benchmark tasks.     

Parallel tabu search message-passing synchronous strategies for task scheduling under precedence constraints

This paper presents parallelization strategies for a tabu search algorithm for the task scheduling problem on heterogeneous processors under task precedence constraints. Parallelization relies exclusively on the decompostion of the solution space exploration. Four different parallel strategies are proposed and implemented on an asynchronous parallel machine under PVM: the master-slave model, with two different schemes for improved load balancing, and the single-program-multiple-data model, with single-token and multiple-token message passing schemes. The comparative analysis of these strategies shows that the tabu search approach for this problem is very suitable to the parallelization of the neighborhood search, with efficiency results almost always close to one for problems over a certain size.     

A cooperative parallel tabu search algorithm for the quadratic assignment problem

In this study, we introduce a cooperative parallel tabu search algorithm (CPTS) for the quadratic assignment problem (QAP). The QAP is an NP-hard combinatorial optimization problem that is widely acknowledged to be computationally demanding. These characteristics make the QAP an ideal candidate for parallel solution techniques. CPTS is a cooperative parallel algorithm in which the processors exchange information throughout the run of the algorithm as opposed to independent concurrent search strategies that aggregate data only at the end of execution. CPTS accomplishes this cooperation by maintaining a global reference set which uses the information exchange to promote both intensification and strategic diversification in a parallel environment. This study demonstrates the benefits that may be obtained from parallel computing in terms of solution quality, computational time and algorithmic flexibility. A set of 41 test problems obtained from QAPLIB were used to analyze the quality of the CPTS algorithm. Additionally, we report results for 60 difficult new test instances. The CPTS algorithm is shown to provide good solution quality for all problems in acceptable computational times. Out of the 41 test instances obtained from QAPLIB, CPTS is shown to meet or exceed the average solution quality of many of the best sequential and parallel approaches from the literature on all but six problems, whereas no other leading method exhibits a performance that is superior to this.     

Optimization of a high-speed placement machine using tabu search algorithms

Combinatorial optimization represents a wide range of real-life manufacturing optimization problems. Due to the high computational complexity, and the usually high number of variables, the solution of these problems imposes considerable challenges. This paper presents a tabu search approach to a combinatorial optimization problem, in which the objective is to maximize the production throughput of a high-speed automated placement machine. Tabu search is a modern heuristic technique widely employed to cope with large search spaces, for which classical search methods would not provide satisfactory solutions in a reasonable amount of time. The developed TS strategies are tailored to address the different issues caused by the modular structure of the machine. This revised version was published online in June 2006 with corrections to the Cover Date.     

Progressive hedging and tabu search applied to mixed integer (0,1) multistage stochastic programming

Many problems faced by decision makers are characterized by a multistage decision process with uncertainty about the future and some decisions constrained to take on values of either zero or one (for example, either open a facility at a location or do not open it). Although some mathematical theory exists concerning such problems, no general-purpose algorithms have been available to address them. In this article, we introduce the first implementation of general purpose methods for finding good solutions to multistage, stochastic mixed-integer (0, 1) programming problems. The solution method makes use of Rockafellar and Wets' progressive hedging algorithm that averages solutions rather than data. Solutions to the induced quadratic (0,1) mixed-integer subproblems are obtained using a tabu search algorithm. We introduce the notion of integer convergence for progressive hedging. Computational experiments verify that the method is effective. The software that we have developed reads standard (SMPS) data files.     

A tabu search algorithm for the single machine total weighted tardiness problem

In this study, a tabu search (TS) approach to the single machine total weighted tardiness problem (SMTWT) is presented. The problem consists of a set of independent jobs with distinct processing times, weights and due dates to be scheduled on a single machine to minimize total weighted tardiness. The theoretical foundation of single machine scheduling with due date related objectives reveal that the problem is NP-hard, rendering it a challenging area for meta-heuristic approaches. This paper presents a totally deterministic TS algorithm with a hybrid neighborhood and dynamic tenure structure, and investigates the strength of several candidate list strategies based on problem specific characteristics in increasing the efficiency of the search. The proposed TS approach yields very high quality results for a set of benchmark problems obtained from the literature.