@Article{HarSho87a, author = "J.P. Hart and A.W. Shogan", title = "Semi-greedy heuristics: {A}n empirical study", journal = "Operations Research Letters", volume = "6", pages = "107--114", year = "1987", annote = "In this paper the authors present a general heuristic schema, called semi-greedy heuristic which, in contrast to the greedy schema, uses randomization within the heuristic in the following two possible ways: given $p$ or $c$, a semi-greedy heuristic randomly chooses each iteration decision from among those decisions resulting in bjective improvements either within $p\%$ of the best improvement or among the $c$ best improvements.", } @Article{BarFeo89a, author = "J.F. Bard and T.A. Feo", title = "Operations sequencing in discrete parts manufacturing", journal = "Management Science", year = "1989", volume = "35", pages = "249--255", annote = "This paper presents a method for efficiently sequencing cutting operations associated with the manufacture of discrete parts. The problem is modeled as an integer program. This is relaxed via Lagrangian relaxation into a min-cut problem on a bipartite network. To obtain lower bounds, a max-flow algorithm is applied and the corresponding solution is input to a {GRASP}.", } @Article{FeoBar89a, author = "T.A. Feo and J.F. Bard", title = "Flight scheduling and maintenance base planning", journal = "Management Science", year = "1989", volume = "35", pages = "1415--1432", annote = "This paper presents a model that can be used by planners to both locate maintenance stations and develop flight schedules that better meet the cyclical demand for maintenance. The problem is formulated as large-scale mixed integer program, i.e. a minimum cost, multicommodity flow network with integral constraints, where each airplane represents a separate commodity and each arc has an upper and lower capacity of flow. Since obtaining feasible solutions from the relative LP relaxation is difficult, the authors propose a {GRASP}.", } @Article{FeoBar89b, author = "T.A. Feo and J.F. Bard", title = "The cutting path and tool selection problem in computer-aided process planning", journal = "Journal of Manufacturing Systems", year = "1989", volume = "8", pages = "17--26", annote = "The purpose of this paper is to provide a method for minimizing the sum of tool setup and volume removal times associated with metal cutting operations on a flexible machine. The problem is modeled as an integer program, then relaxed into a min-cut problem on a simple network. After obtaining a tentative solution, the authors use a {GRASP} to identify good feasible points corresponding to alternative process plans. These are seen to speed convergence during branch \& bound.", } @Article{FeoRes89a, author = "T.A. Feo and M.G.C. Resende", title = "A probabilistic heuristic for a computationally difficult set covering problem", journal = "Operations Research Letters", volume = "8", pages = "67--71", year = "1989", annote = "{GRASP} is proposed for set covering. A value based restricted candidate list is used to construct solutions of difficult set covering problems that arise in computing the $1$-width of the incidence matrix of Steiner triple systems. The local search is based on the elimination of redundant elements in the cover.", } @Article{BarFeo91a, author = "J.F. Bard and T.A. Feo", title = "An algorithm for the manufacturing equipment selection problem", journal = "IIE Transactions", volume = "23", pages = "83--92", year = "1991", annote = "This paper provides a unified framework in which product and process demands can be related to manufacturing system requirements. The authors develop a nonlinear cost minimization model. The objective is to determine how many of each machine type to purchase and what fraction of the time each piece of equipment will be configured for a particular type of operation. Once the original problem is converted into a MILP, a depth-first branch \& bound algorithm is used, employing the greedy randomized set covering heuristic of Feo and Resende (1989), to implicitly search for optimality. Viewing the contribution that any machine makes to satisfy the demand of any process as the unit benefit associated with that machine, a benefit-to-cost ratio is computed for each machine. To derive a feasible solution, the heuristic iteratively selects machines with largest ratio and updates benefits to take into account the remaining demand.", } @Article{FeoVenBar91a, author = "T.A. Feo and K. Venkatraman and J.F. Bard", title = "A {GRASP} for a difficult single machine scheduling problem", journal = "Computers \& Operations Research", volume = "18", pages = "635--643", year = "1991", annote = "{GRASP} is applied in this paper to an unusually difficult scheduling problem with flow time and earliness penalties. Two greedy functions are developed and tested. The first is the difference between the flow time and earliness penalties, normalized by the processing time. The second function evaluates the cost of scheduling a job next by estimating the cost of the remaining schedule. The local search uses $2$-exchange and insertion exchange.", } @Article{LagGon91a, author = "M. Laguna and J.L. Gonz\'alez-Velarde", title = "A search heuristic for just-in-time scheduling in parallel machines", journal = "Journal of Intelligent Manufacturing", year = "1991", volume = "2", pages = "253--260", annote = "This paper presents a hybrid {GRASP}/tabu search metaheuristic for the weighted earliness penalty problem with deadlines in identical parallel machines.", } @Article{Kli92a, author = "J.G. Klincewicz", title = "Avoiding local optima in the $p$-hub location problem using tabu search and {GRASP}", journal = "Annals of Operations Research", volume = "40", pages = "283--302", year = "1992", annote = "This paper proposes two heuristics based on tabu search and {GRASP} for the $p$-hub location problem. The objective is to overcome the difficulty that local search algorithms encounter. The local search procedure of proposed {GRASP} is based on the $2$-exchange.", } @Article{DeGhoWel94a, author = "P. De and J.B. Ghosj and C.E. Wells", title = "Solving a generalized model for {CON} due date assignment and sequencing", journal = "International Journal of Production Economics", volume = "34", pages = "179--185", year = "1994", annote = "This paper deals with a generalized model for assigning a constant flow allowance (CON) due date to a set of jobs and sequencing them on a single machine. The problem is viewed as a $0$-$1$ quadratic problem and a {GRASP} is proposed to solve the quadratic problem. The randomization strategy used was inspired by a gradient-based variable forcing methodology proposed by Pardalos and Rodgers (1990) for a branch \& bound algorithm. The local search procedure is based on a definition of neighborhood in which two solutions are neighbors if they differ in the value of exactly one variable.", } @Article{FeoResSmi94a, author = "T.A. Feo and M.G.C. Resende and S.H. Smith", title = "A greedy randomized adaptive search procedure for maximum independent set", journal = "Operations Research", volume = "42", pages = "860--878", year = "1994", annote = "A {GRASP} for approximately solving the maximum independent set problem is described. The greedy function chosen orders admissible vertices with respect to the minimum admissible vertex degree. The adjective admissible is referred to a vertex that is not adjacent to any vertex in the current independent set. The neighborhood definition used in the local search is $(2,1)$-exchange, where two nonadjacent vertices can be added to the current solution if a single vertex from the solution is removed. The proposed heuristic can be easily implemented in parallel by decomposing the problem into smaller subproblems, each defined by conditioning on vertices being in the solution. An implementation of this algorithm was tested on a MIMD computer with up to eight processors. Average linear speedup is observed.", } @Article{KliRaj94a, author = "J.G. Klincewicz and A. Rajan", title = "Using {GRASP} to solve the component grouping problem", journal = "Naval Research Logistics", volume = "41", pages = "893--912", year = "1994", annote = "Two new heuristics are proposed for solving a particular set partitioning problem that arises in robotics assembly, as well as in a number of other manufacturing and material logistics application areas. The heuristics are {GRASPs} involving two alternate procedures for determining starting i points: component-based and code-based.", } @Article{LagFeoElr94a, author = "M. Laguna and T.A. Feo and H.C. Elrod", title = "A greedy randomized adaptive search procedure for the two-partition problem", journal = "Operations Research", volume = "42", pages = "677--687", year = "1994", annote = "A {GRASP} for the network $2$-partition problem is proposed. The greedy function of the construction phase minimizes the augmented weight of the partition. For the local improvement phase, four alternative procedures are considered: best swap, first swap, slight swap, and slightest swap. The best strategies are slight and slightest swaps. Slight swap selects a near-minimum gain exchange at each iteration, while slightest swap chooses the absolute minimum gain.", } @incollection{LiParRes94a, author = "Y. Li and P.M. Pardalos and M.G.C. Resende", title = "A Greedy Randomized Adaptive Search Procedure for the Quadratic Assignment Problem", booktitle = "Quadratic assignment and related problems", editor = "P.M. Pardalos and H. Wolkowicz", series = "{DIMACS} Series on Discrete Mathematics and Theoretical Computer Science", publisher = "American Mathematical Society", volume = "16", pages = "237--261", year = "1994", annote = "A {GRASP} for the quadratic assignment problem is described. Construction first makes two assignments, and then completes the solution by making assignments, one at a time. The greedy function is assignment interaction cost. The local search procedure is a $2$ assignment exchange.", } @Article{FeoBarHol95a, author = "T.A. Feo and J.F Bard and S. Holland", title = "Facility-wide planning and scheduling of printed wiring board assembly", journal = "Operations Research", volume = "43", pages = "219--230", year = "1995", annote = "This paper describes a decision support system known as {INSITES}, designed to assist {Texas Instruments} in the day-to-day assembly operations of their printed wiring board ({PWB}) facilities. A {GRASP} is used to solve the underlying multiple machine scheduling problem. The schedule produced at each {GRASP} iteration is evaluated based on one of five different optimization criteria. The choice of the criterion to be followed is made by the user to rank order the schedules provided by multiple {GRASP} iterations.", } @Article{FeoGon95a, author = "T.A. Feo and J.L Gonz\'alez-Velarde", title = "The intermodal trailer assignment problem: {M}odels, algorithms, and heuristics", journal = "Transportation Science", volume = "29", pages = "330--341", year = "1995", annote = "This paper deals with the problem of optimally assigning highway trailers to railcar hitches in intermodal transportation. Using a set covering formulation, the problem is modeled as an integer linear program, whose linear programming relaxation yields a tight lower bound. This formulation also provides the basis for developing a branch-and-bound algorithm and a {GRASP} for solving the problem. The greedy strategy of the construction phase of {GRASP} consists in selecting at each step a feasible assignment of the most difficult to use available railcar together with the most difficult to assign trailer. To improve the constructed solution, a $2$-exchange local search is applied, carrying out a complete enumeration of the solutions in the neighborhood.", } @Article{FeoRes95a, author = "T.A. Feo and M.G.C. Resende", title = "Greedy randomized adaptive search procedures", journal = "Journal of Global Optimization", volume = "6", pages = "109--133", year = "1995", annote = "In this tutorial paper, the authors define the various components comprising a {GRASP}. A general trivial implementation of {GRASP} on a parallel computer is also discussed. The {GRASP} literature until 1994 is surveyed.", } @phdthesis{Hjo95a, author = "C.A. Hjorring", title = "The vehicle routing problem and local search metaheuristics", school = "University of Auckland", address = "Auckland, New Zealand", year = "1995", annote = "Three metaheuristics for effectively searching through the space of cyclic orders are developed. They are based on {GRASP}, tabu search, and genetic algorithms. For tabu search, different schemes are investigated to control the tabu list length, including a reactive tabu search method. To obtain good solutions when using the genetic algorithm, specialized crossovers are developed, and a local search component is added. {GRASP} is used to construct an initial good solution.", } @Article{KonBar95a, author = "G. Kontoravdis and J.F. Bard", title = "A {GRASP} for the vehicle routing problem with time windows", journal = "ORSA Journal on Computing", volume = "7", pages = "10-23", year = "1995", annote = "A {GRASP} is proposed for minimizing the fleet size of temporarily constrained vehicle routing problems with two types of service. The greedy function of the construction phase takes into account both the overall minimum insertion cost and the penalty cost. Local search is applied to the best solution found every five iterations of the first phase, rather than to each feasible solution.", } @incollection{ParPitMavRes95a, author = "P.M. Pardalos and L. Pitsoulis and T. Mavridou and M.G.C. Resende", title = "Parallel search for combinatorial optimization: {G}enetic algorithms, simulated annealing and {GRASP}", booktitle = "Parallel Algorithms for Irregularly Structured Problems, Proceedings of the Second International Workshop --Irregular'95", editor = "A. Ferreira and J. Rolim", series = "Lecture Notes in Computer Science", publisher = "Springer-Verlag", volume = "980", year = "1995", pages = "317--331", annote = "This paper summarizes some parallel search techniques for approximating the global optimal solution of combinatorial optimization problems. For large-scale problems, one of the main limitations of heuristic search is its computational complexity. Therefore, efficient parallel implementation of search algorithms can significantly increase the size of the problems that can be solved.", } @incollection{ParPitRes95a, author = "P.M. Pardalos and L.S. Pitsoulis and M.G.C. Resende", title = "A parallel {GRASP} implementation for the quadratic assignment problem", booktitle = "Parallel Algorithms for Irregularly Structured Problems~-- Irregular'94", editor = "A. Ferreira and J. Rolim", publisher = "Kluwer Academic Publishers", year = "1995", pages = "115--130", annote = "Efficient parallel techniques for large-scale sparse quadratic assignment problems are discussed. The paper provides a detailed description of a parallel implementation on an MIMD computer of the sequential {GRASP} proposed by Li, Pardalos, and Resende (1994) for solving the QAP. The {GRASP} iterations are distributed among the processors. Each processor is given its own input data and random number sequence and are run independently. A shared global variable stores the value of the incumbent solution." } @Article{ArgFeoGol96a, AUTHOR = "M.F. Arg{\"u}ello and T.A. Feo and O. Goldschmidt", TITLE = "Randomized methods for the number partitioning problem", JOURNAL = "Computers \& Operations Research", VOLUME = "23", NUMBER = "2", PAGES = "103--111", year = "1996", annote = "This paper presents randomized methodologies for solving the number partitioning problem (the partitioning of a finite set of integers into two disjoint subsets such that the difference of the sums of the elements in the subsets is minimized). The greedy criterion consists in considering only large elements for differencing. Specific selection of the elements to be differenced is made at random. Differences are placed back into the list of remaining elements, and the process of selecting the next element is repeated. The proposed methods are greedy, randomized, and adaptive construction heuristics, but local search is omitted.", } @Article{BarFeoHol96a, AUTHOR = "J.F. Bard and T.A. Feo and S. Holland", TITLE = "A {GRASP} for scheduling printed wiring board assembly", JOURNAL = "I.I.E. Trans.", VOLUME = "28", PAGES = "155--165", year = "1996", annote = "The assembly of printed wiring boards (PWBs) typically involves the coordination of thousands of components and hundreds of part numbers in a job shop environment with more than 50 different processes and workstations. The authors propose a {GRASP} for solving the daily scheduling problem that arises in such environment. The first phase of {GRASP} obtains a user-specified number of schedules. The greedy function is the product between the weighted processing time and and the slack time window.", } @inproceedings{Bre96a, author = "J.L. Bresina", title = "Heuristic-biased stochastic sampling", booktitle = "Proceedings of the AAAI-96", year = "1996", pages = "271--278", annote = "This paper presents a generalization of iterative sampling called Heuristic-Biased Stochastic Sampling (HBSS). The two search techniques have the same overall control structure. The difference lies in how a choice is made at each decision point. HBSS uses a given search heuristic to focus its exploration. The degree of focusing is determined by a chosen {\em bias function} that reflects the confidence one has in the heuristic's accuracy. This methodology can be directly applied in a {GRASP} construction phase, by biasing the selection of RCL elements to favor those with higher greedy function values.", } @techreport{CarMedPer96a, author = "C. Carvalho de Souza and C. Bauzer Medeiros and R. Scachetti Pereira", title = "Integrating heuristics and spatial databases: {A} case study", number = "IC-96-18", institution = "Institute of Computing, Universidade Estadual de Campinas", address = "Campinas, Brazil", year = "1996", annote = "This paper presents part of the ongoing efforts at IC-UNICAMP to apply heuristic algorithms to vectorial georeferenced data to help decision support in urban planning. The authors describe a first prototye implemented in C++ and tested on support planning activities for the S\~ao Paulo State Post Office System in Brazil. The problem is a special partition problem, whose goal is to minimize the number of clusters in the partition (number of districts in the distribution zone). The authors chose to represent the problem by building a special undirected graph that has two main characteristics: connectivity and information about the mailman daily loads. For solving the problem, the authors propose a set of randomized heuristics, including a {GRASP}." } @Article{FeoSarMcG96a, author = "Feo, T.A. and K. Sarathy and McGahan, J.", title = "A {GRASP} for single machine scheduling with sequence dependent setup costs and linear delay penalties", journal = "Computers \& Operations Research", volume = "23", pages = "881--895", year = "1996", annote = "A {GRASP} for single machine scheduling with sequence dependent setup costs and linear delay penalties is presented. The greedy function of the {GRASP} construction phase proposed is made up of two components: the switch over cost and the opportunity cost associated with not inserting a specific job in the next position and instead, inserting it after half of the unscheduled jobs have been scheduled. This greedy function tends to lead to a balance between the natural order and nearest neighbor approaches. The local search uses $2$-exchange, insertion exchange, and a combination of the two.", } @Article{Gho96a, author = "J.B. Ghosh", title = "Computational aspects of the maximum diversity problem", journal = "Operations Research Letters", volume = "19", pages = "175--181", year = "1996", annote = "This paper addresses two variations of the maximum diversity problem. This problem arises when $m$ elements are to be selected from an $n$-element population based on inter-element distances. Using a reduction from the vertex cover problem, the authors prove that the problem is NP-hard and propose a {GRASP} for approximately solving it. The neighborhood of a solution is the set of all solutions that can be obtained by replacing an element in the incumbent solution with one element that is not in it.", } @incollection{Gon96a, author = "J.L. Gonz\'alez", title = "{GRASP}", booktitle = "Heuristic optimization and neural networks in operations management and engineering", editor = "A. D\'{\i}az", publisher = "Editorial Paraninfo", address = "Madrid", year = "1996", pages = "143--161", annote = "This is a chapter on {GRASP} in a book on heuristic procedures for optimization. In Spanish." } @Article{ParPitRes96a, author = "P.M. Pardalos and L.S. Pitsoulis and M.G.C. Resende", title = "A parallel {GRASP} for {MAX-SAT} problems", journal = "Lecture Notes in Computer Science", volume = "1184", pages = "575--585", year = "1996", annote = "A parallel {GRASP} for weighted maximum satisfiability (MAX-SAT) problem is proposed. The {GRASP} is based on the serial {GRASP} presented by Resende, Pitsoulis, and Pardalos (1997). The parallel implementation distributes the {GRASP} iterations among several processors operating in parallel, avoiding that two processors have as input the same random number generator seed. The best solution found among all processors is identified and used as solution of the problem.", } @incollection{ResFeo96a, author = "M.G.C. Resende and T.A. Feo", title = "A {GRASP} for Satisfiability", booktitle = "{C}liques, {C}oloring, and {S}atisfiability: {T}he {S}econd {DIMACS} {I}mplementation {C}hallenge", editor = "D.S. Johnson and M.A. Trick", series = "{DIMACS} Series on Discrete Mathematics and Theoretical Computer Science", publisher = "American Mathematical Society", volume = "26", year = "1996", pages = "499--520", annote = "This paper describes a {GRASP} for the satisfiability problem that can be also directly applied to both the weighted and unweighted versions of the maximum satisfiability problem. The adaptive greedy function is a hybrid combination of two functions. One function seeks to maximize the number of yet-unsatisfied clauses that become satisfied after the assignment of each construction iteration, while the other maximizes the number of yet-unassigned literals in yet-unsatisfied clauses that become satisfied if opposite assignments were to be made. The local search flips the assignment of each variable, one at a time, checking if the new truth assignment increases the number of satisfied clauses." } @Article{ResParLi96a, author = "M.G.C. Resende and P.M. Pardalos and Y. Li", title = "Algorithm 754: {F}ortran subroutines for approximate solution of dense quadratic assignment problems using {GRASP}", journal = "ACM Transactions on Mathematical Software", volume = "22", pages = "104--118", year = "1996", annote = "This paper describes a set of ANSI standard Fortran 77 subroutines to find approximate solutions to dense quadratic assignment problems having at least one symmetric flow or distance matrix. It is an optimized implementation of the algorithm described in Li, Pardalos, and Resende (1994).", } @inproceedings{XuChiu96a, author = "J. Xu and S. Chiu", title = "Solving a real-world field technician scheduling problem", booktitle = "Proceedings of the International Conference on Management Science and the Economic Development of China", city = "Hong-Kong", month = "July", year = "1996", pages = "240--248", annote = "The objective of the field technician scheduling problem is to assign a set of jobs at different locations with time windows to technicians with different job skills. The greedy choice of the proposed {GRASP} is to select jobs with the highest unit weight. The local search implements four different moves, among them the $2$-exchange and a swap that exchanges an assigned job with another job unassigned under the candidate schedule." } @incollection{YagIba96a, author = "M. Yagiura and T. Ibakari", title = "Genetic and local search algorithms as robust and simple optimization tools", booktitle = "Meta-heuristics: {T}heory and applications", editors = "I.H. Osman and J.P. Kelly", publisher = "Kluwer Academic Publishers", city = "Boston", year = "1996", pages = "63--82", annote = "Various metaheuristics such as random multi-start local search (MLS) and genetic algorithm (GA) are implemented in this paper and their performance compared. The objective of the authors is not to propose the most powerful technique, but to compare general tendencies of various algorithms. From their analysis, they conclude that a {GRASP} type modification of MLS improves its performance and that GA combined with local search is quite effective if long computational time is allowed." } @incollection{AreVan97a, author = "S. Areibi and A. Vannelli", title = "A {GRASP} clustering technique for circuit partitioning", booktitle = "Satisfiability problems", editor = "J. Gu and P.M. Pardalos", series = "{DIMACS} Series on Discrete Mathematics and Theoretical Computer Science", publisher = "American Mathematical Society", volume = "35", pages = "711--724", year = "1997", annote = "This paper adapts a basic node interchange scheme for solving the circuit partitioning problem and develops a clustering technique that uses {GRASP} to generate clusters of moderate sizes. The number of clusters is predetermined as a function of the number of partitions required. Initially, the heuristic reads the circuit description and resizes the blocks to be used by {GRASP}, which utilizes only the construction phase to generate the number of required clusters. The {GRASP} construction phase is followed by a post-processing stage, in which a simple dynamic hill climbing algorithm is used as local search to improve the initial solution generated." } @Article{ArgBarYu97a, AUTHOR = "M.F. Arg{\"u}ello and J.F. Bard and G. Yu", TITLE = "A {GRASP} for aircraft routing in response to groundings and delays", JOURNAL = "Journal of Combinatorial Optimization", VOLUME = "1", PAGES = "211--228", year = "1997", annote = "This paper presents a {GRASP} to reconstruct aircraft routings in response to groundings and delays experienced over the course of the day. The objective is to minimize the cost of reassigning aircraft to flights taking into account available resources and other system constraints. The proposed heuristic is a neighborhood search technique that takes as input an initial feasible solution, so that the construction phase is omitted. Two types of partial route exchange operations are described. The first type is the exchange of flight sequences with identical endpoints. In the second type, the sequence of flights being exchanged must have the same origination airport, but the termination airports are swapped.", } @Article{Bar97a, author = "J.F. Bard", title = "An analysis of a rail car unloading area for a consumer products manufacturer", journal = "Journal of the Operational Research Society", volume = "48", pages = "873--883", year = "1997", annote = "This paper discusses how to design and analyze the railcar unloading area of Procter \& Gamble's principal laundry detergent plant. The related combinatorial problem of assigning railcars to positions on the platform and unloading equipment to railcars is modeled as a mixed-integer nonlinear program. To approximately solve the problem, four alternatives are proposed and evaluated with the help of a {GRASP}.", } @techreport{DelDiaFerOrt97a, author = "H. Delmaire and J.A. D\'{\i}az and E. Fern\'andez and M. Ortega", title = "Comparing new heuristics for the pure integer capacitated plant location problem", number = "DR97/10", institution = "Department of Statistics and Operations Research, Universitat Politecnica de Catalunya", address = "Barcelona, Spain", year = "1997", annote = "To solve the pure integer capacitated plant location problem, several heuristics are proposed: evolutionary algorithms, {GRASP}, simulated annealing, and tabu search. All the algorithms share the same neighborhood definition, which can be one of the following: client plant, client reassignment, client interchange, open plans interchange, and open-closed plants interchange." } @incollection{HolMigPar97a, author = "K. Holmqvist and A. Migdalas and P.M. Pardalos", title = "Greedy randomized adaptive search for a location problem with economies of scale", booktitle = "Developments in Global Optimization", editor = "I.M. Bomze et al.", publisher = "Kluwer Academic Publishers", pages = "301--313", year = "1997", annote = "This paper proposes a {GRASP} for finding approximate solutions to a facility location problem with concave costs. The greedy function of the construction phase favors the facilities that give lower cost for a costumer, regarding the effect that already connected costumers have on the solution. The neighborhood function is defined as changing facility connection for one costumer. Instead of a time consuming computation of the objective function value for each neighborhood solution, the difference in cost for changing supplier is examined." } @inproceedings{MacSou97a, author = "E.M. Macambira and C.C. de Souza", title = "A {GRASP} for the maximum clique problem with weighted edges", booktitle = "Proceedings of the XXIX Brazilian Symposium on Operations Research", month = "October", year = "1997", pages = "70", annote = "The authors propose a branch-and-cut algorithm for the maximum clique problem with weighted edges. The initialization phase of the algorithm uses a {GRASP} to generate good starting solutions. The greedy function minimizes the sum of weights of the edges outgoing from vertices in the partition. The local search uses the exchange of one element in the current partition with one not in it." } @techreport{MacSou97b, author = "E.M. Macambira and C.C. de Souza", title = "The edge-weighted clique problem: {V}alid inequalities, facets and polyhedral computations", number = "IC-97-14", institution = "Instituto de Computa\c c\~ao, Universidade Estadual de Campinas", address = "Campinas, Brazil", annote = "Given a complete undirected graph $K_n=(V,E)$ with weights $c_e$ associated to edges in $E$, the edge-weighted clique problem consists in finding a subclique $C=(U,F)$ of $K_n$ such that the sum of the weights of the edges in $F$ is maximized and $\vert U\vert\leq b$, for some $b\in \{1,2,\ldots,n\}$. In this paper, the facial structure of the polytope associated to the problem is studied and new classes of facies are introduced. To obtain initial lower bounds, the authors used a {GRASP}.", year = "1997" } @book{MocEddMocMocRek97a, author = "J. Mockus and E. Eddy and A. Mockus and L. Mockus and G.V. Reklaitis", title = "Bayesian discrete and global optimization", publisher = "Kluwer Academic Publishers", address = "", year = "1997", annote = "This book describes the Bayesian approach to discrete optimization. A Bayesian heuristic algorithm version of {GRASP} is described." } @Article{ParPitRes97a, author = "P.M. Pardalos and L.S. Pitsoulis and M.G.C. Resende", title = "Algorithm 769: {F}ortran subroutines for approximate solution of sparse quadratic assignment problems using {GRASP}", journal = "ACM Transactions on Mathematical Software", volume = "23", pages = "196--208", year = "1997", annote = "A version of the {GRASP} for the quadratic assignment problem of Li, Pardalos, and Resende (1994), tailored for sparse instances is proposed. A set of ANSI standard Fortran 77 subroutines are i described.", } @Article{ParRamResLi97a, author = "P.M. Pardalos and K.G. Ramakrishnan and M.G.C. Resende and Y. Li", title = "Implementation of a variance reduction based lower bound in a branch and bound algorithm for the quadratic assignment problem", journal = "SIAM Journal on Optimization", volume = "7", pages = "280--294", year = "1997", annote = "This paper describes a branch \& bound algorithm for the quadratic assignment problem which uses a {GRASP} to compute upper bounds.", } @inproceedings{PopPicAriDem97a, author = "F. Poppe and M. Pickavet and P. Arijs and P. Demeester", title = "Design techniques for {SDH} mesh-restorable networks", booktitle = "Proceedings of the European Conference on Networks and Optical Communications (NOC'97), Volume 2: Core and ATM Networks", pages = "94--101", year = "1997", annote = "To design low cost reliable telecommunication networks, the authors propose three algorithms: an integer linear programming algorithm (branch-and-cut-and-price), a {GRASP}, and a zoom-in approach that combines a genetic algorithm with deterministic optimization routines. The greedy choice of the proposed {GRASP} is to favor paths having lowest additional cost. The local search iteratively tries to reroute some paths in order to further decrease the overall network cost." } @incollection{ResPitPar97a, author = "M.G.C. Resende and L.S. Pitsoulis and P.M. Pardalos", title = "Approximate solution of weighted {MAX-SAT} problems using {GRASP}", booktitle = "Satisfiability problems", editor = "J. Gu and P.M. Pardalos", series = "{DIMACS} Series on Discrete Mathematics and Theoretical Computer Science", publisher = "American Mathematical Society", volume = "35", pages = "393--405", year = "1997", annote = "This article proposes a {GRASP} for finding approximate solutions of weighted {MAX-SAT} problems. The greedy adaptive function is to maximize the total weight of yet-unsatisfied clauses that become satisfied after the assignment of each construction phase iteration. The local search uses the $1$-flip neighborhood of a vector $x$, defined as the set of all binary vectors that differ from $x$ in exactly one literal." } @Article{ResRib97a, author = "M.G.C. Resende and C.C. Ribeiro", title = "A {GRASP} for graph planarization", journal = "Networks", year = "1997", volume = "29", pages = "173--189", annote = "A {GRASP} for the graph planarization problem is described, extending the two-phase heuristic of Goldschmidt and Takvorian ({\em Networks}, v. 24, pp. 69--73, 1994). The implementation of the {GRASP} is described in detail. Computational experience on a large set of standard test problems is presented. On almost all test problems considered, the heuristic either matches or finds a better solution than previously described graph planarization heuristics. In several cases, previously unknown optimal solutions are found." } @techreport{ResUlu97a, author = "M.G.C. Resende and O. Ulular", title = "{SMART}: {A} tool for {AT\&T} {W}orldnet access design -- {L}ocation of {C}ascade 9000 concentrators", institution = "AT\&T Labs Research", address = "Florham Park, NJ 07932 USA", year = "1997", annote = "This report describes {SMART}, a software tool for finding low cost configurations of Cascade 9000 concentrators in the {AT\&T} {W}orldnet backbone access network. The concentrator location problem is stated and cost model is presented for concentrator configurations. This cost model is used in a {GRASP}, proposed for finding approximate solutions to the concentrator location problem. The greedy choice favors the points-of-presence (POPs) with smallest incremental cost. The local search implements a simple $2$-exchange." } @mastersthesis{Alv98a, author = "A.C.F. Alvim", title = "Parallelization strategies for the metaheuristic {GRASP}", school = "Department of Computer Science, Catholic University of Rio de Janeiro", address = "Rio de Janeiro, RJ 22453-900 Brazil", month = "April", year = "1998", annote = "Two parallelization strategies for {GRASP} are discussed and compared: parallelization by distributing {GRASP} iterations and parallelization by varying the {GRASP} random parameter $\alpha$. Both strategies are adapted to several parallel computation models, such as MPI (Message Passing Interface) and PVM (Parallel Virtual Machine). In Portuguese." } @techreport{AlvRib98a, author = "A.C.F. Alvim and C.C. Ribeiro", title = "Load balancing in the parallelization of the metaheuristic {GRASP}", institution = "Department of Computer Science, Catholic University of Rio de Janeiro", address = "Rio de Janeiro, RJ 22453-900 Brazil", year = "1998", annote = "Two parallelization strategies for {GRASP} are compared. The difference between the two strategies concerns the way in which data is partitioned: pre-scheduled (static load balancing) or self-scheduled (dynamic load balancing). The strategies have been tested considering an application to optimal traffic assignment in TDMA satellite system. Best results have been obtained by using the self-scheduling strategy. In Portuguese." } @incollection{AndCarRib98a, author = "A.A. Andreatta and S.E.R. Carvalho and C.C. Ribeiro", title = "An object-oriented framework for local search heuristics", booktitle = "Proceedings of the 26th TOOLS USA '98 -- {T}echnology of {O}bject-{O}riented {L}anguages and {S}ystems", publisher = "IEEE Computer Society", year = "1998", pages = "33--45", annote = "This paper proposes a unified object-oriented framework for comparing in a systematic way strategies and parameters of different heuristics designed for solving the same combinatorial optimization problem." } @mastersthesis{Ara98a, author = "R.G.I. Arakaki", title = "O problema de roteamento de ve\'{\i}culos e algumas metaheur\'{\i}sticas", school = "Instituto Nacional de Pasquisas Espaciais", address = "Brazil", annote = "In this thesis, several different metaheuristics are proposed for the vehicle routing problem, including a {GRASP}. In the {GRASP} construction phase a distance function is used as the greedy function, while the local search tries to find a better allocation for a costumer at a time. In Portuguese.", month = "September", year = "1998" } @Article{Atk98a, author = "J.B. Atkinson", title = "A greedy randomised search heuristic for time-constrained vehicle scheduling and the incorporation of a learning strategy", journal = "Journal of the Operational Research Society", volume = "49", pages = "700--708", year = "1998", annote = "Two forms of adaptive search called {\em local} and {\em global} adaptation are identified. In both search techniques, the greedy function takes into account a quantity that measures heuristically the quality of the partial solution. While in local adaptation the decisions made within a particular run influence only the subsequent performance of the heuristic, global adaptation involves making decisions that affect the performance of the heuristic in subsequent runs.", } @Article{BarHuaJaiDro98a, author = "J.F. Bard and L. Huang and P. Jaillet and M. Dror", title = "A decomposition approach to the inventory routing problem with satellite facilities", journal = "Transportation Science", volume = "32", pages = "189--203", year = "1998", annote = "A methodology is presented that decomposes the inventory routing problem with satellite facilities over the planning horizon, and then solves daily rather than multi-day vehicle routing problems. Three heuristics are proposed for solving the vehicle routing problem with satellite facilities: randomized Clarke-Wright, {GRASP}, and modified sweep. The {GRASP} proposed is a modified version of the {GRASP} of Kontoravdis and Bard (1995).", } @techreport{DemEks98a, author = "R. Demirer and B. Eksioglu", title = "Subset selection in multiple linear regression: {A} new mathematical programming approach", number = "School of business working paper no. 284", institution = "School of business, University of Kansas", address = "Lawrence, Kansas, USA", annote = "The new mathematical programming model here proposed is parametrically solved to obtain a collection of efficient subsets. The parametric solution requires repeatedtly solving a mathematical program and the authors choose to solve it by using either a Langrangian relaxation based heuristic or a {GRASP}. The greedy function is based on the change in the objective function value if a variable of the problem is set equal to $1$. The improvement phase is based on the change in the objective function value if a variable of the problem is complemented.", year = "1998" } @Article{DesTri98a, author = "A.S. Deshpande and E. Triantaphyllou", title = "A greedy randomized adaptive search procedure ({GRASP}) for inferring logical clauses from examples in polynomial time and some extensions", journal = "Mathematical and Computer Modelling", volume = "27", pages = "75--99", year = "1998", annote = "Two heuristics are presented in this article for inferring a small size Boolean function from complete and incomplete examples in polynomial time. Each example can be positive or negative depending on whether it must be accepted or rejected, respectively, by the target function. Both of the proposed heuristics are randomized in the sense that instead of choosing the best candidate element, a candidate list is built whose elements are assigned with evaluative function values close to the highest one.", } @techreport{GanVanTuy98a, author = "X. Gandibleux and D. Vancoppenolle and D. Tuyttens", title = "A first making use of {GRASP} for solving {MOCO} problems", institution = "University of Valenciennes, France", year = "1998", annote = "An extension of {GRASP}, to solve multi-objective combinatorial optimization (MOCO) problems, is considered. In particular, classical covering, assignment, knapsack, and scheduling problems with multiple objectives are used as benchmarks. Computational results compare {GRASP} solutions for a benchmark set of test problems and results are discussed in comparison with an exact method, when available. In French." } @incollection{HanMla98a, author = "P. Hansen and N. Mladenovi\'c", title = "An introduction to variable neighborhood search", booktitle = "Meta-heuristics, {A}dvances and trends in local search paradigms for optimization", editor = "S. Voss and S. Martello and I. H. Osman and C. Roucairol", publisher = "Kluwer Academic Publishers", city = "Dordrecht", pages = "433--458", year = "1998", annote = "This paper introduces the metaheuristic variable neighborhood search. This local search method expands the neighborhood each time a local optimal solution is reached. Once an improvement is made, the search restarts at the initial (smallest) neighborhood. The search ends once a local optimum of the largest neighborhood is found." } @incollection{HolMigPar98a, author = "K. Holmqvist and A. Migdalas and P.M. Pardalos", title = "A {GRASP} algorithm for the single source uncapacitated minimum concave-cost network flow problem", booktitle = "Network design: {C}onnectivity and facilities location", editor = "P.M. Pardalos and D.-Z. Du", series = "{DIMACS} Series on Discrete Mathematics and Theoretical Computer Science", publisher = "American Mathematical Society", volume = "40", pages = "131--142", year = "1998", annote = "This paper is concerned with the single source uncapacitated version of the minimum concave-cost network flow problem, that requires establishing a minimum cost flow through a given network from a single source to a set of sinks. The authors propose a {GRASP} that can be trivially implemented on parallel processors. The construction phase iteratively builds a tree starting from the source node. The elements of the restricted candidate list are end nodes of arcs with a cost close to the best one. The local search phase applies either of the two local search variants proposed by Guisewite and Pardalos (1990)." } @inproceedings{JuiPol98a, author = "H. Juill\'e and J.B. Pollack", title = "A sampling-based heuristic for tree search applied to grammar induction", booktitle = "Proceedings of the Fifteenth National Conference on Artificial Intelligence", city = "Madison, Wisconsin, USA", annote = "In this paper, the authors present SAGE, a new search algorithm that incorporates the same fundamental mechanisms as the most popular metaheuristics. It is an iterative search procedure that at each iteration performs a construction phase and a competition phase. In the construction phase, SAGE implements a set of elementary randomized searches and a meta-level heuristic that controls the search procedure by distributing the alternatives among the searches. Scope of the competition phase is to favor the most promising search alternatives.", month = "July 26-30", year = "1998" } @techreport{LouSer98a, author = {H. R. Louren\c{c}o and D. Serra}, title = "Adaptive approach heuristics for the generalized assignment problem", institution = "Department of Economics and Business, Universitat Pompeu Fabra", series = {Economics Working Papers}, number = {288}, address = "Barcelona, Spain", year = "1998", annote = "For the generalized assignment problem, the authors propose several heuristics based an hybrid approaches, including a {GRASP}, whose greedy choice is to prefer tasks using small amounts of agent resource. In the improvement phase, several local searches are implemented, among them a descent local search and a search based on ejection chain neighborhood." } @techreport{KraPelRusTer98a, author = "N. Krasnogor and D.A. Pelta and W. Russo and G. Terrazas", title = "A {GRASP} approach to the protein structure prediction problem", institution = "LIFIA Lab, University of La Plata", address = "La Plata, Argentina", year = "1998", annote = "This paper discusses the applicability of a {GRASP} for solving a special protein folding problem, an important problem in computational biology. The goal is to predict from the molecular sequence of a given protein its particular 3D structure." } @techreport{Loc98a, author = {M. Locatelli}, title = {{A class of heuristic methods for the maximization of the $l_1$-norm over parallelotopes}}, institution = {Dipartimento di Sistemi ed Informatica, Universit\'a di Firenze}, address = {Firenze, Italy}, year = {1998}, annote = "For the maximization of the $l_1$-norm over parallelotopes, a class of heuristics is proposed that includes a slightly modified {GRASP}, in which between a greedy construction and local search phases a filter phase is inserted to avoid to perform local search from not enough good solutions. The local search uses is a variant of a $1$-flip neighbirhood." } @techreport{MacMen98a, author = "E.M. Macambira and C.N. Meneses", title = "A {GRASP} algorithm for the maximum weighted edge subgraph problem", institution = "Department of Statistics and Computation, University of Cear\'a", address = "Fortaleza, CE 60740-000 Brazil", year = "1998", annote = " {GRASP} for the maximum weighted edge subgraph problem is proposed to overcome the difficulties encountered by local search methods. The greedy function of the construction phase favors the vertices corresponding to the maximum sum of the weights associated with its outgoing edges. The local search tries to improve the actual solution by simply swapping one element in the solution set with one not belonging to the solution. In Portuguese." } @incollection{MarRibSou98a, author = "S.L. Martins and C.C. Ribeiro and M.C. Souza", title = "A parallel {GRASP} for the {S}teiner problem in graphs", booktitle = "Proceedings of {IRREGULAR}'98 -- 5th {I}nternational {S}ymposium on {S}olving {I}rregularly {S}tructured {P}roblems in {P}arallel", editor = "A. Ferreira and J. Rolim", series = "Lecture Notes in Computer Science", publisher = "Springer-Verlag", volume = "1457", pages = "285--297", year = "1998", annote = "A parallelization of a sequential {GRASP} for the Steiner minimal tree problem is proposed. The procedure implemented is one of the procedures described in Martins, Pardalos, Resende, and Ribeiro (1999). The parallelization is accomplished by distributing the {GRASP} iterations among the processors on a demand-driven basis." } @incollection{MurParPit98a, author = "R.A. Murphey and P.M. Pardalos and L.S. Pitsoulis", title = "A greedy randomized adaptive search procedure for the multitarget multisensor tracking problem", booktitle = "Network design: {C}onnectivity and facilities location", editor = "P.M. Pardalos and D.-Z. Du", series = "{DIMACS} Series on Discrete Mathematics and Theoretical Computer Science", publisher = "American Mathematical Society", volume = "40", pages = "277--301", year = "1998", annote = "A {GRASP} is presented for approximately solving the multitarget multisensor tracking problem, which can be interpreted as a collection of multidimensional assignment problems. Since the objective is to select a target hypothesis and partition of the measurements that is most likely to occur, a likelihood cost function and partitioning constraint set are developed. The {GRASP} construction phase creates the restricted candidate list containing the most likely to occur (lower cost) tuples. The local search explores all $2$-exchange permutations." } @incollection{MurParPit98b, author = "R.A. Murphey and P.M. Pardalos and L.S. Pitsoulis", title = "A parallel {GRASP} for the data association multidimensional assignment problem", booktitle = "Parallel Processing of Discrete Problems", editor = "P.M. Pardalos", series = "The {IMA} Volumes in Mathematics and its Applications", publisher = "Springer-Verlag", volume = "106", pages = "159--180", year = "1998", annote = "A {GRASP} for finding good solutions for the data association multidimensional assignment problem is described. At each discrete time interval, the data set is formulated as a multidimensional assignment problem (MAP) with a maximum likelihood cost function. A near-optimal solution to each MAP is obtained with a {GRASP}. The proposed method can be easily parallelized to substantially decrease the running time." } @Article{MavParPitRes98a, author = "T. Mavridou and P.M. Pardalos and L.S. Pitsoulis and M.G.C. Resende", title = "A {GRASP} for the biquadratic assignment problem", journal = "European Journal of Operational Research", volume = "105", pages = "613--621", year = "1998", annote = "This paper proposes a {GRASP} for finding approximate solutions of the biquadratic assignment problem. As in the case of {GRASP} for the quadratic assignment problem, the construction phase has two stages. The first stage simultaneously makes four assignments, selecting the pairs corresponding to the smallest interaction costs, while the second stage makes the remaining assignments, one at time. The greedy function in the second stage selects the assignment corresponding to the minimum interaction cost with respect to the already-made assignments. In the local search phase, $2$-exchange local search is applied to the permutation constructed in the first phase.", } @incollection{ParResRap98a, author = "P.M. Pardalos and M.G.C. Resende and J. Rappe", title = "An exact parallel algorithm for the maximum clique problem", booktitle = "High performance algorithms and software in nonlinear optimization", editor = "R. De Leone and A. Murli and P.M. Pardalos and G. Toraldo", publisher = "Kluwer Academic Publishers", pages = "279--300", year = "1998", annote = "A parallelized version of the exact algorithm of Carraghan and Pardalos (1990) for the unweighted maximum clique problem is described. A variant of the {GRASP} for the maximum independent set problem of Feo, Resende, and Smith (1994) is used for computing feasible solutions." } @techreport{Pas98a, author = "E.L. Pasiliao", title = "A greedy randomized adaptive search procedure for the multi-criteria radio link frequency assignment problem", institution = "Department of ISE, University of Florida", address = "Gainesville, FL 32611-6595", year = "1998", annote = "A {GRASP} for computing approximate solutions to a radio link frequency assignment problem is proposed. The objective is to minimize the order and the span of the solution set. The local search procedure attempts to eliminate each channel from the communication network. This process is repeated until an attempt to eliminate every frequency in the solution set has been made without success." } @techreport{RanAbrBoaSil98a, author = "M.C. Rangel and N.M.M. de Abreu and P.O. {Boaventura Netto} and M.C.S. Boeres", title = "A modified local search for {GRASP} in the quadratic assignment problem", institution = "Production Engineering Program, COPPE, Federal University of Rio de Janeiro", address = "Rio de Janeiro, RJ Brazil", year = "1998", annote = "An improvement of the local search phase of the {GRASP} proposed by Li, Pardalos, and Resende (1994) for solving the quadratic assignment problem is proposed. The new strategy amplifies the local search range and improves the local search's efficiency." } @Article{Res98a, author = "M.G.C. Resende", title = "Computing approximate solutions of the maximum covering problem using {GRASP}", journal = "Journal of Heuristics", volume = "4", pages = "161--171", year = "1998", annote = "A {GRASP} for the maximum covering problem is described. The greedy function is the total weight of the yet-uncovered demand points that become covered after the selection. The local search procedures uses a $2$-exchange neighborhood structure. The {GRASP} is shown to find near optimal solutions.", } @Article{ResFeoSmi98a, author = "M.G.C. Resende and T.A. Feo and S.H. Smith", title = "Algorithm 787: {Fortran} subroutines for approximate solution of maximum independent set problems using {GRASP}", journal = "ACM Transactions on Mathematical Software", year = "1998", volume = "24", pages = "386--394", annote = "This article describes a set of ANSI standard Fortran 77 subroutines to find an approximate solution of a maximum independent set problem. The {GRASP} used to produce the solutions is described in Feo, Resende, and Smith (1994).", } @Article{RioBar98a, author = "R.Z. R\'{\i}os-Mercado and J.F. Bard", title = "Heuristics for the flow line problem with setup costs", journal = "European Journal of Operational Research", vol = "110", pages = "76--98", year = "1998", annote = "This paper presents two new heuristics for the flowshop scheduling problem with sequence-dependent setup times and makespan minimization objective, one of which is a {GRASP}. Both heuristics are compared to a previously proposed algorithm, based on the traveling salesman problem (TSP), on randomly generated instances. When setup times are an order of magnitude smaller than processing times, the new approaches prove superior to the TSP-based heuristic. When both processing and setup times are identically distributed, the TSP-based heuristic outperforms the proposed procedures.", } @mastersthesis{Riv98a, author = "L.I.D. Rivera", title = "Evaluation of parallel implementations of heuristics for the course scheduling problem", school = "Instituto Tecnologico y de Estudios Superiores de Monterrey", address = "Monterrey, Mexico", year = "1998", annote = "This thesis presents several parallel implementations of heuristics for the course scheduling problem. One of the heuristics is a {GRASP}. In Spanish." } @Article{Urb98a, author = "T.L. Urban", title = "Solution procedures for the dynamic facility layout problem", journal = "Annals of Operations Research", vol = "76", pages = "323--342", year = "1998", annote = "The concept of incomplete dynamic programming is applied to the dynamic facility layout problem and a lower bound for the general problem is developed. A {GRASP} and an initialized multi-greedy algorithm are described to provide a solution methodology for large problems. The {GRASP} is the algorithm proposed by Li, Pardalos, and Resende (1994) for dense quadratic assignment problems.", } @incollection{AbeParRes99a, author = "J. Abello and P.M. Pardalos and M.G.C. Resende", title = "On maximum clique problems in very large graphs", booktitle = "External memory algorithms and visualization", editor = "J. Abello and J. Vitter", series = "{DIMACS} Series on Discrete Mathematics and Theoretical Computer Science", publisher = "American Mathematical Society", volume = "50", pages = "119--130", year = "1999", annote = "An approach for clique and quasi-clique computations in very large multi-digraphs is presented. The authors discuss graph decomposition schemes that break up the original problem into several pieces of manageable dimensions. A semi-external memory {GRASP} is presented to approximately solve the maximum clique problem and maximum quasi-clique problem. The construction phase uses vertex degrees as a guide for construction. The local search uses a simple $(2,1)$-exchange." } @Article{AktKil99a, author = {M.S. Akturk and K. Kili\c{c}}, title = {Generating short-term observations for space mission projects}, journal = {J. of Intelligent Manufacturing}, volume = {10}, pages = {387--404}, annote = {Generating short-term observations for space mission projects is basically a scheduling problem. It consists in generating short-term observation schedules of Hubble Space Telescope (HST) such that the scientific return is maximized. In this paper, a new dispatching rule and a set of local search based algorithms are proposed. The algorithms are based on the filtered beam search and include a {GRASP} and a Simulated Annealing to construct short-term observation schedules of space mission projects, mainly for NASA HST. The greedy function used in the proposed {GRASP} is based start time and completion time of scheduled observations The local search is based on a simple exchange neighborhood structure and is not performed at each {GRASP} iteration, but only if the schedule output from the construction phase seems to be promising.}, year = {1999} } @inproceedings{Are99a, author = "S.M. Areibi", title = "{GRASP}: {A}n effective constructive technique for {VLSI} circuit partitioning", booktitle = "Proc. IEEE Canadian Conference on Electrical \& Computer Engineering (CCECE'99)", city="Edmonton, Alberta, Canada", month = "May", year = "1999", volume = {1}, pages = {462--467}, annote = "This article proposes a {GRASP} for obtaining good initial solutions for an iterative improvement technique. At each iteration of the randomized approach, the gains associated with moving modules to the current block being filled are examined, and a restricted candidate list is built using the modules with the highest gains." } @Article{DelDiaFerOrt99a, author = "H. Delmaire and J.A. D\'{\i}az and E. Fern\'andez and M. Ortega", title = "Reactive {GRASP} and tabu search based heuristics for the single source capacitated plant location problem", journal = "INFOR", volume = "37", pages = "194--225", year = "1999", annote = "The single source capacitated plant location problem is a discrete location problem that takes into account capacities in the plants to be opened and imposes that clients be served from a single open plant. The authors propose a hybrid heuristic that embeds reactive {GRASP} in a tabu search algorithm as a diversification method that provides elite i candidate sets. Intensification is also done.", } @techreport{DiaVelSol99a, author = {J.C.Z. Diaz and J.S. Vel\'azquez and J.F. Solis}, title = {{Un modelo tipo {GRASP} para la paralelizaci\'on de algoritmos en computadoras {MIMD}: Aplicaci\'on al algoritmo de Jarmenson}}, institution = {Universidad Aut\'onoma del Estado de Morelos, Facultad de Ciencias}, address = {Cuernavaca, Morelos, Mexico}, annote = {In this paper, the authors use a {GRASP} to optimize operations needed to parallelize algorithms on a MIMD. The greedy criterion is to minimize the cost associated with comunication among processors, while local search uses an exchange neighborhood structure. In Spanish.}, year = {1999} } @Article{FerMar99a, author = "E. Fern\'andez and R. Mart\'{\i}", title = "{GRASP} for seam drawing in mosaicking of aerial photographic maps", journal = "Journal of Heuristics", volume = "5", pages = "181--197", year = "1999", annote = "Commercial aerial photographic maps are often so large that it is necessary to produce one map from two or even more photographs. These are combined, two at a time, in a process called {\em mosaicking}. The objective is to make the final map appear to be the product of a single photograph. The most difficult step in the mosaicking process is {\em seam-drawing}. This paper proposes a {GRASP} for solving the seam-drawing process.", } @Article{FleGlo99a, author = "C. Fleurent and F. Glover", title = "Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory", journal = "INFORMS Journal on Computing", volume = "11", year = "1999", pages = "198--204", annote = "Adaptive memory strategies that are the heart of tabu search methods are shown to be a foundation for alternative, enhanced, multistart approaches. This paper illustrates that constructive multistart methods, such as Random Restart and {GRASP}, can be improved by the addition of memory and associated heuristic search principles. The improved results indicate that these principles (learning, intensification, candidate list strategies, POP) are not limited to applications with transition neighborhoods, as in local search, but can also be useful for applications characterized by constructive (and destructive) neighborhoods. The paper shows that the {GRASP} for QAP of Li, Pardalos, and Resende (1994) can be improved upon by using these memory strategies. Study of alternatives to memoryless multistart approaches like {GRASP} is conducted for the quadratic assignment problem. Adaptive memory strategies retain and analyze features of selected solutions in order to provide a basis for improving future executions of the constructive process. The authors show that the most effective strategies are tabu search methods, which use memory in both improving and constructive phases.", } @techreport{GomSil99a, author = "M.J.N. Gomes and J.B.C. {da Silva}", title = "An experimental evaluation of the {GRASP} metaheuristic applied to the uncapacitated location problem", number = "004/99", institution = "Department of Statistics and Computation, State University of Cear\'a", address = "Fortaleza, Cear\'a, Brazil", year = "1999", annote = "Two {GRASPs}, one using the ADD heuristic and the other using the DROP heuristic, are proposed for the uncapacitated location problem. Computational experiments with instances from Beasley's OR-Library show that {GRASP}-DROP dominates {GRASP}-ADD, while both {GRASPs} dominate ADD and DROP." } @inproceedings{IorTriLiaWal99a, author = "V.I. Iorvik and E. Triantaphyllou and T.W. Liao and S.M. Waly", title = "Predicting muscle fatique via electromyography: {A} comparative study", booktitle = "Proceedings of the 25th International Conference on Computers and Industrial Engineering", city = "New Orleans, LA, USA", month = "March", year = "1999", annote = "The authors present a comparison of some state-of-the-art AI predictive and statistical techniques, including a {GRASP}.", pages = "277--280" } @Article{LagMar99a, author = "M. Laguna and R. Mart\'{\i}", title = "{GRASP} and path relinking for $2$-layer straight line crossing minimization", journal = "{INFORMS} Journal on Computing", volume = "11", pages = "44--52", year = "1999", annote = "This paper develops a {GRASP} for the problem of minimizing straight line crossings in a $2$-layer graph. The method proposed can be coupled with a path relinking strategy to search for improved outcomes. The greedy criterion of the construction phase is based on the degree of the vertices and a value based restricted candidate list is used. Each step of the improvement phase consists in selecting each vertex to be considered for a move. A probabilistic selection rule is used such that vertices with high degree are more likely to be selected first at each step of this process. This paper incorporates to {GRASP} a path relinking strategy to search for improved outcomes. Path relinking generates new solutions by exploring trajectories connecting high quality solutions. Starting from an {\em initiating solution}, path relinking generates a path in the neighborhood space that leads toward the other solutions, called {\em guiding solutions}. This is accomplished by selecting moves that introduce attributes contained in the guiding solutions.", } @phdthesis{Mar99a, author = "S.L. Martins", title = "Estrat\'egias de Paraleliza\c{c}\~ao de Metaheur\'{\i}sticas em Ambientes de Mem\'oria Distribu\'{\i}da", school = "Department of Computer Science, Catholic University of Rio de Janeiro", address = "Rio de Janeiro, Brazil", year = "1999", annote = "This thesis considers parallelization strategies for metaheuristics in distributed memory environments. {GRASPs} for the Steiner tree problem in graphs are described and implemented in parallel. In Portuguese." } @incollection{MarParResRib99a, author = "S.L. Martins and P.M. Pardalos and M.G.C. Resende and C.C. Ribeiro", title = "Greedy randomized adaptive search procedures for the {Steiner} problem in graphs", booktitle = "Randomization methods in algorithmic design", editor = "P.M. Pardalos and S. Rajasekaran and J. Rolim", series = "{DIMACS} Series on Discrete Mathematics and Theoretical Computer Science", publisher = "American Mathematical Society", volume = "43", pages = "133--145", year = "1999", annote = "Four versions of a {GRASP} for approximately solving general instances of the Steiner problem in graphs are proposed. One is implemented and tested. The construction phase is based on the distance network heuristic. A distance network corresponding to the original graph is built. Associated with each edge of the distance network is a weight that takes into account the shortest distances in the original graph. With respect to the new weight distribution, Kruskal's algorithm is used to solve the minimum spanning tree (MST) problem and the edges in the MST so computed are replaced by the edges in the corresponding shortest paths in the original graph. The local search is based on insertions and eliminations of nodes to and from the current solution." } @techreport{OliGom99a, author = "C.A.S. Oliveira and F.C. Gomes", title = "Two metaheuristics for channel allocation in mobile telephony", institution = "Artificial Intelligence Laboratory, Universidade Federal do Cear\'a", address = "Fortaleza, Brazil", month = "August", year = "1999", annote = "The frequency assignment problem described consists in minimizing the total system interference in mobile phone covered areas, with respect to co-channel and adjacent-channel interference. Two metaheuristics are proposed: {GRASP} and Asynchronous Team (A-Team). The construction phase of the proposed {GRASP} is realized by a procedure that at each step chooses the next antenna to which a frequency will be assigned. In the RCL construction, priority is given to transmitters with fewer options of frequency assignment. To implement the local search phase, the authors use a down hill algorithm, that performs random perturbations in the solution, exchanging the frequency of one antenna by another randomly chosen. The stopping criterion used for the down hill algorithm is execution time." } @Article{ParQiaRes99a, author = "P.M. Pardalos and T. Qian and M.G.C. Resende", title = "A greedy randomized adaptive search procedure for the feedback vertex set problem", journal = "Journal of Combinatorial Optimization", year = "1999", volume = "2", pages = "399--412", annote = "This article describes a {GRASP} for finding approximate solutions to the feedback vertex set problem on a digraph. Several greedy functions are tested, all of them taking into account vertices with high degree. The local search procedure tries at each iteration to eliminate redundant vertices. Some efficient problem reduction techniques are also described. They are useful both to simplify the problem instance and to determine whether a digraph is acyclic or not.", } @phdthesis{Pit99a, author = "L.S. Pitsoulis", title = "Algorithms for nonlinear assignment problems", school = "Department of Industrial and Systems Engineering, University of Florida", city = "Gainesville", year = "1999", annote = "This dissertation presents {GRASPs} for solving the following NP-hard nonlinear assignment problems (NAPs): quadratic assignment problem (QAP), biquadratic assignment problem (BiQAP), turbine balancing problem (TBP), and multidimensional assignment problem (MAP). Computational results indicate that all of the suggested algorithms are among the best in the literature in terms of solution quality and computational time." } @inproceedings{ResRes99a, author = "L.I.P. Resende and M.G.C. Resende", title = "A {GRASP} for frame relay {PVC} routing", booktitle = "Proc. of the Third Metaheuristics International Conference", city= "Angra dos Reis, Brazil", month = "July", year = "1999", pages = "397--402", annote = "This paper describes a {GRASP} for routing permanent virtual circuits (PVC) for frame relay in telecommunications systems. The objective is to minimize PVC delays while balancing trunk loads. The greedy choice selects from the set of not yet routed PVCs the one that minimizes the delay while balancing the trunk loads. The local search procedure reroutes each PVC, one at a time, checking each time if the new route taken together with the remaining fixed routes improves the objective function." } @Article{RibRes99a, author = "C.C. Ribeiro and M.G.C. Resende", title = "Algorithm 797: {Fortran} subroutines for approximate solution of graph planarization problems using {GRASP}", journal = "ACM Transactions on Mathematical Software", volume = "25", pages = "341--352", year = "1999", annote = "This paper describes a set of Fortran subroutines that implements the {GRASP} for graph planarization of Resende and Ribeiro (1997).", } @techreport{Sil99a, author = "C.M.D. Silveira", title = "{GRASP} -- {U}ma heurist\'{\i}ca para resolu\c{c}\~{a}o de problemas de otimiza\c{c}\~ao combinatoria", institution = "Institute of Informatics, Federal University of Rio Grande do Sul", address = "Porto Alegre, RS, Brazil", year = "1999", annote = "The aim of this report is to provide an exhaustive description of the features of {GRASP} as a metaheuristic method for solving hard combinatorial optimization problems. The various components comprising a generic {GRASP} are defined and it is also shown through examples how to develop {GRASPs} for combinatorial optimization problems. In Portuguese." } @Article{AhuOrlTiw00a, author = "R.K. Ahuja and J.B. Orlin and A. Tiwari", title = "A greedy genetic algorithm for the quadratic assignment problem", journal = "Computers and Operations Research", volume = "27", pages = "917--934", year = "2000", annote = "This report suggests a genetic algorithm for the QAP that incorporates the construction phase of the {GRASP} for QAP of Li, Pardalos, and Resende (1994) to generate the initial population.", } @techreport{AieResParTor00a, author = "R.M. Aiex and M.G.C. Resende and P.M. Pardalos and G. Toraldo", title = "{GRASP} with path relinking for the three-index assignment problem", institution = "AT\&T Labs Research", address = "Florham Park, NJ 07733", year = "2000", note = {To appear in {\em INFORMS J. on Computing}.}, annote = "This paper describes variants of {GRASP} with path relinking for the three index assignment problem (AP3). Computational results show clearly that this {GRASP} for AP3 benefits from path relinking and that the variants considered in this paper compare well with previously proposed heuristics for this problem. The authors also show that the random variable time to target solution, for all proposed {GRASP} with path relinking variants, fits a two-parameter exponential distribution. To illustrate the consequence of this, one of the variants of {GRASP} with path relinking is shown to benefit from parallelization." } @inproceedings{AreVan00a, author = {S. Areibi and A. Vannelli}, title = {Efficient Hybrid Search Techniques For Circuit Partitioning}, booktitle = {{IEEE 4th World Multiconference on Circuits, Systems, Communications \& Computers}}, city = {Athens, Greece}, month = {July}, year = {2000}, annote = "In this paper, for solving the problem the authors apply a simulated annealing, a tabu search, a {GRASP}, and a genetic algorithm. Two further search techniques are also proposed as hybrids, where a {GRASP} and a genetic algorithm are used for generating good initial partitions." } @Article{ArmKliLusRos00a, author = "M. Armony and J.G. Klincewicz and H. Luss and M.B. Rosenwein", title = "Design of stacked self-healing rings using a genetic algorithm", journal = "Journal of Heuristics", volume = "6", pages = "85--105", year = "2000", annote = "A genetic algorithm for design of stacked self-healing rings is proposed. The objective is to optimize the trade-off between the cost of connecting nodes to the ring and the cost of routing demand on multiple rings. The initial population of the genetic algorithm is made up of randomly generated solutions as well as solutions generated by a {GRASP}. Computational comparisons are made with a commercial integer programming package.", } @inproceedings{BauSuaMatCom00a, author = "J. Bautista and R. Su\'arez and M. Mateo and R. Companys", title = "Local search heuristics for the assembly line balancing problem with incompatibilities between tasks", booktitle = "Proceedings of the IEEE ICRA-00", volume = "3", city = "San Francisco", month = "April", year = "2000", annote = "The assembly line balancing problem with incompatibilities between tasks consists in minimizing the total number of needed workstations and minimizing the the cycle time for the minimum number of workstations. The authors propose a {GRASP} and a genetic algorithm for solving the problem. The greedy choice favors tasks with the best index value, while the local search phase simply changes the order of elements in the sequence solution.", pages = "2404--2409" } @phdthesis{Bro00a, author = "D.C. Brown", title = "Algorithmic methods in genetic mapping", school = "Cornell University", address = "Ithaca, NY, USA", annote = "This thesis is a survey of existing methods for genetic mapping problems and proposed several new algorithms. A {GRASP} has been also investigated. The greedy function is defined on bin length, while the local search first removes from the sample those population members that do not affect on the objective function value. Then, it tries to greedily augment the sample until no member can been removed without increasing the minimum bin size", year = "2000", } @Article{BroVisTan00a, author = "D.G. Brown and T.J. Vision and S.D. Tanksley", title = {{Selecting mapping: {A} discrete optimization approach to select a population subset for use in a high-density genetic mapping project}}, journal = "Genetics", volume = "155", pages = "407--420", year = "2000", annote = "The authors propose a {GRASP} for selecting a population subset for use in a high-density genetic mapping project. At each iteration of the construction phase, they add to the partial solution one among the $r$ unchosen population members which most improve the objective function value. The authors investigated very small sized RCL (i.e. $r=3$ and $r=5$). The implemented local search removes from the current solution some members and greedily includes other members, until no further improving exchange can be done.", } @techreport{FioMal03b, author = "M.S. Fiorenzo Catalano and F. Malucelli", title = "Parallel randomized heuristics for the set covering problem", note = "To appear in International J. of Computer Research", institution = {Transportation and traffic engineering section, Delft U. of Technology, 2600 AG Delft, The Netherlands}, year = "2000", annote = "The authors propose a general scheme to design heuristics for the set covering problem. A first group of procedures randomize the choice of the next element to be added at the solution under construction in a way similar to ant system, while a second set of procedures introduces a random perturbation of the costs of the problem instance. The second set includes also a {GRASP} and seems to be more efficient than competitors from the first set of algorithms.", } @Article{HelHad00a, author = "S. Abdinnour-Helm and S.W. Hadley", title = "Tabu search based heuristics for multi-floor facility layout", journal = "International Journal of Production Research", volume = "38", pages = "365--383", year = "2000", annote = "Two two-stage heuristics are proposed for solving the multi-floor facility layout problem. {GRASP}/TS applies a {GRASP} to find the initial layout and tabu search to refine the initial layout, based on total inter/intra-floor costs. Computational tests indicate that {GRASP}/TS compares favorably with heuristics that do not rely on exact algorithms.", } @Article{JinGalHab00a, author = {H. Jin-Kao and P. Galinier and M. Habib}, title = {M\'etaheuristiques pour l'optimisation combinatoire et l'affectation sous contraintes}, journal = {Revue d'Intelligence Artificielle}, volume = {13}, number = {2}, pages = {283--324}, annote = {Scope of this paper is to highlight main properties of existing metaheuristics in order to help researchers in choosing the most suitable one in practice. One of the metaheuristic addressed is {GRASP}. In French.}, year = {2000} } @inproceedings{LiCheYin00a, author = "B. Li and F. Chen and L. Yin", title = "Server replication and its placement for reliable multicast", booktitle = "Proceedings of the IEEE ICCCN-00", city = "Las Vegas", month = "October", year = "2000", annote = "In a multicast network, packets are forwarded from a source (server) to group of receivers along a distribution tree, where the source is the root, the receivers are the leaves, and the multicast-capable routers are the internal nodes. The problem studied in this paper consists of placing multiple replicated servers within the multicast-capable routers and to solve it, the authors propose a number of heuristic algorithms, including a {GRASP}. The greedy function is the router cost function, while the local search phase uses a $k$-exchange neighborhood structure with $k=1$.", pages = "396--401" } @incollection{LiuParRajRes00a, author = "X. Liu and P.M. Pardalos and S. Rajasekaran and M.G.C. Resende", title = "A {GRASP} for frequency assignment in mobile radio networks", booktitle = "Mobile Networks and Computing", editor = "S. Rajasekaran and P.M. Pardalos and F.Hsu", series = "{DIMACS} Series on Discrete Mathematics and Theoretical Computer Science", publisher = "American Mathematical Society", volume = "52", pages = "195--201", year = "2000", annote = "A {GRASP} for frequency assignment is described. Local search uses simulated annealing. The construction phase uses two greedy functions. The first chooses a vertex from the set of unselected vertices with high saturation degrees. The second function is used to assign a frequency to the selected vertex. A frequency is selected from a set of permissible frequencies that contribute little additional cost to the objective function." } @Article{MarResRibPar00b, author = "S.L. Martins and M.G.C. Resende and C.C. Ribeiro and P.M. Pardalos", title = "A parallel {GRASP} for the {Steiner} tree problem in graphs using a hybrid local search strategy", journal = "Journal of Global Optimization", volume = "17", year = "2000", pages = "267--283", annote = "This paper presents a {GRASP} for the Steiner problem in graphs. The construction phase is based on the Mehlhorn distance network heuristic, which consists of computing the modified distance network graph and using Kruskal's algorithm to solve the minimum spanning tree problem for the resulting graph. The local search is done by using a combination of key-path based local search and node based local search.", } @techreport{OsmAyoBarHas00a, author = "I.H. Osman and B. Al-Ayoubi and M. Barake and M. Hasan", title = "A greedy random adaptive search procedure for the weighted maximal planar graph problem", institution = "School of Business and Center for Advanced Mathematical Sciences, American University of Beirut", address = "Beirut, Lebanon", year = "2000", annote = "A {GRASP} is proposed and tested for the weighted maximal planar graph problem. The construction is a randomized version of the Green \& Al-Hakim algorithm (1985). A new data structure is introduced, reducing the complexity of the construction from $O(n^3)$ to $O(n^2)$. Local search uses four types of moves proposed by Pesch, Glover, Bartsch, Salewski, and Osman (1995)." } @phdthesis{Pra00a, author = "M. Prais", title = "Estrat\'egias de varia\c{c}\~ao de par\^ametros em procedimentos {GRASP} e aplica\c{c}\~oes", school = "Department of Computer Science, Catholic University of Rio de Janeiro", address = "Rio de Janeiro, Brazil", year = "2000", annote = "This thesis describes a {GRASP} for a matrix decomposition problem in {TDMA} traffic assignment. It proposes Reactive {GRASP}, a refinement of {GRASP} where the RCL parameter is adjusted dynamically to favor values that produce good solutions. Reactive {GRASP} is compared with other RCL strategies on matrix decomposition, set covering, maximum satisfiability and graph planarization." } @Article{PraRib00a, author = "M. Prais and C.C. Ribeiro", title = "Reactive {GRASP}: {A}n application to a matrix decomposition problem in {TDMA} traffic assignment", journal = "INFORMS Journal on Computing", volume = "12", pages = "164--176", year = "2000", annote = "This paper describes a {GRASP} for matrix decomposition problem arising in the context of traffic assignment in communication satellites. A geostationary communication satellite has a number of spot beam antennas covering geographically distributed areas. According to the slot switching configuration on the on-board switch, the uplink traffic received at the satellite has to be immediately sent to ground areas through a set of transponders. The slot switching configurations are determined through the solution of a time slot assignment problem, which is equivalent to the decomposition of a nonnegative traffic matrix into the sum of a family of switching mode matrices. A refinement of {GRASP}, called Reactive {GRASP}, is proposed. Instead of using a fixed value for the basic parameter that defines the restrictiveness of the candidate list during the construction phase, Reactive {GRASP} self-adjusts the parameter value according to the quality of the solutions previously found. The local search phase of the {GRASP} proposed is based on a new neighborhood, defined by constructive and destructive moves.", } @Article{PraRib00b, author = "M. Prais and C.C. Ribeiro", title = "Varia\c{c}\~ao de par\^ametros em procedimentos {GRASP}", journal = "Investigaci\'on Operativa", volume = "9", year = "2000", pages = "1--20", annote = "The {GRASP} RCL parameter $\alpha$ that determines the size of the restricted candidate list can be adjusted, leading to different behavior of the {GRASP} implementation. This paper investigates four strategies for the variation of the parameter $\alpha$: 1) reactive -- $\alpha$ is self-adjusted along the iterations; 2) uniform -- $\alpha$ is randomly chosen from a discrete uniform probability distribution; 3) hybrid -- $\alpha$ is randomly chosen from a fixed probability distribution concentrated around the value corresponding to the purely greedy choice; 4) fixed -- $\alpha$ has a fixed value close to the purely greedy choice. The reactive strategy is the most flexible and adherent to the characteristics of the specific problem to be solved. In Portuguese.", } @Article{RanAbrBoa00a, author = "M.C. Rangel and N.M.M. Abreu and P.O. {Boaventura Netto}", title = "{GRASP} para o {PQA}: {U}m limite de aceita\c{c}\~{a}o para solu\c{c}\~{o}es iniciais", journal = "Pesquisa Operacional", volume = "20", year = "2000", pages = "45--58", annote = "This paper presents a modified version of the {GRASP} algorithm proposed by Li, Pardalos, and Resende (1994) for the quadratic assignment problem. The new {GRASP} uses a criterion to accept or reject a given initial solution, thus trying to avoid searches that eventually can be fruitless. It computes a normalized limit cost, defined with the aid of {QAP} upper and lower bounds easily obtained and discards all solutions with cost less than the computed limit. In Portuguese.", } @Article{ResPitPar00a, author = "M.G.C. Resende and L.S. Pitsoulis and P.M. Pardalos", title = "{Fortran} subroutines for computing approximate solutions of {MAX-SAT} problems using {GRASP}", journal = "Discrete Applied Mathematics", volume = "100", pages = "95--113", year = "2000", annote = "A set of {Fortran} subroutines for computing approximate solutions of {MAX-SAT} problems is described. The algorithm implemented was proposed by Resende, Pitsoulis, and Pardalos (1997). Two versions of the subroutines are distributed. One version uses a neighborhood data structure in order to speed up the local search phase, while the second version, since it does not make use of this data structure, is more memory efficient but less time efficient. Computational results improve upon those in Resende, Pitsoulis, and Pardalos (1997) using an RCL parameter $\alpha$ randomly chosen each {GRASP} iteration from the interval $[0,1]$.", } @incollection{Sos00a, author = "D. Sosnowska", title = "Optimization of a simplified fleet assignment problem with metaheuristics: {S}imulated annealing and {GRASP}", booktitle = "Approximation and complexity in numerical optimization", editor = "P.M. Pardalos", publisher = "Kluwer Academic Publishers", year = "2000", annote = "Two heuristics based on simulated annealing and {GRASP} are presented for finding approximate solutions for a simplified fleet assignment problem. Both methods are based on swapping parts of sequence of flight legs assigned to an aircraft (rotation cycle) between two randomly chosen aircrafts. In simulated annealing, the exchange is such that a solution is accepted according to a probability distribution, while in {GRASP} only exchanges leading to a better solution are permitted and the potentially best part of the assignment is conserved and the rest is randomly reattributed. The construction phase does not use a restricted candidate list explicitly, but a solution is built by simply trying to make the time interval between two flights as small as possible." } @inproceedings{SriRamKumAraNaq00a, author = "A. Srinivasan and K.G. Ramakrishnan and K. Kumaram and M. Aravamudam and S. Naqvi", title = "Optimal design of signaling networks for {Internet} telephony", booktitle = "IEEE INFOCOM 2000", city= "Tel-Aviv, Israel", month = "March", year = "2000", annote = "This paper presents an approach for efficient design of a signaling network for a network of software switches supporting Internet telephony. Optimal load balancing for given demand forecast is formulated as a quadratic assignment problem, which is solved with a {GRASP}." } @Article{UrbChiRus00a, author = "T.L. Urban and W.-C. Chiang and R.A. Russel", title = "The integrated machine allocation and layout problem", journal = "International Journal of Production Research", volume = "38", pages = "2911--2930", year = "2000", annote = "{GRASP} is used to solve quadratic assignment sub-problems in a model that aggregates quadratic assignment problems with several network flow problems with side constraints. This model is used to produce machine layouts where machines are not required to be placed in a functional or cellular layout.", } @Article{YenCarChaGarNgu00a, author = "J. Yen and M. Carlsson and M. Chang and J.M. Garcia and H. Nguyen", title = "Constraint solving for inkjet print mask design", journal = "Journal of Imaging Science and Technology", volume = "44", pages = "391--397", year = "2000", annote = "Print masks are used to control the firing of the nozzles, that is, to determine which nozzles on an inkjet printer cartridge are to spit an ink droplet at each particular instant in a multiple-pass print mode. Masks are generated by minimizing the total costs. A {GRASP} is proposed for for automatic generation of print masks. It has been used to design the print masks for Hewlett Packard's wide format printers (DeskJet 2500C and 2500CM). This approach can shorten the turn-around time for print mask design.", } @Article{AhuOrlSha01a, author = "R.K. Ahuja and J.B. Orlin and D. Sharma", title = "Multi-exchange neighborhood search structures for the capacitated minimum spanning tree problem", journal = "Mathematical Programming", volume = "91", pages = "71-97", year = "2001", annote = "The main contribute of this paper is the proposal of two very large scale neighborhood search algorithms. The first one uses a node based neighborhood structure, defined by performing multi-exchanges involving several trees, where each tree contributes a subtree. The second algorithm uses instead a tree based neighborhood structure, obtained by allowing multi-exchanges, where each tree contributes a subtree. The authors compare their algorithms with the best state-of-the-art approaches, including a {GRASP}.", } @Article{AktOzd01a, author = "M.S. Akturk and D. Ozdemir", title = "A new dominance rule to minimize total weighted tardiness with unequal release dates", journal = "European Journal of Operational Research", volume = "135", pages = "394--412", year = "2001", annote = "The authors propose a new algorithm that provides sufficient condition for local optimality and that can be embedded into several heuristic framework, including {GRASP}.", } @inproceedings{AlvParTam01a, author = "R. Alvarez-Valdes and A. Parajon and J.M. Tamarit", title = "A computational study of heuristic algorithms for two-dimensional cutting stock problems", booktitle = "Proceedings of MIC'2001", city = "Porto, Portugal", month = "July 16-20", year = "2001", pages = "7--11", annote = "To solve the column generation subproblem arising while solving two-dimensional cutting stock problem, the authors propose the Gilmore-Gomory approach and several heuristics, including a {GRASP}. The greedy criterion is the potential benefit of an item, while at each iteration of the local search, waste rectangles produced in the construction phase are merged if possible with adjacent pieces thus creating new rectangles that could be cut with greater value." } @inproceedings{AreMouAbd01a, author = "S. Areibi and M. Moussa and H. Abdullah", title = "A comparison of genetic/memetic algorithms and other heuristic search techniques", booktitle = "Proceedings of IC-AI 2001", city = "Las Vegas, nevada, USA", month = "July 25", year = "2001", annote = "The authors compare in this paper several constructive procedures for circuit partitioning problems, including a genetic algorithm, a memetic algorithm, and a {GRASP}." } @inproceedings{ArrMarMezOrt01a, author = "E. Arr\'aiz and A. Mart\'{\i}nez and O. Meza and M. Ortega", title = "{GRASP} and tabu search algorithms for computing the forwarding index in a graph", booktitle = "Proceedings of MIC'2001", city = "Porto, Portugal", month = "July 16-20", year = "2001", pages = "367--370", annote = "The forwarding index in a graph is a measure of the load or of the congestion of vertices once the paths between vertices have been computed. For efficiently computing this number, the authors propose a {GRASP} and tabu search algorithms. The {GRASP} greedy choice considers the length of paths connecting nonadjacent nodes, while two different local search strategies are used. The first one replaces a path passing through an internal node with maximum load with another path joining the same endpoints. The second one replaces a path with maximum length." } @Article{BahOliPer01a, author = "L. Bahiense and G.C. Oliveira and M. Pereira", title = "A mixed integer disjunctive model for transmission network expansion", journal = "IEEE Transactions on Power Systems", volume = "16", pages = "560--565", year = "2001", annote = "Given the nonconvex nature of the transmission network expansion problem, its classical nonlinear mixed integer formulation does not guarantee an optimal solution. Hence, the authors of this paper propose an alternative mixed integer linear disjunctive formulation. The mixed integer program is solved by a commercial branch and bound code, where the upper bound in the bounding phase is obtained by applying the reactive {GRASP} proposed in Binato et al. (2001).", } @Article{BinOliAra01a, author = "S. Binato and G.C. Oliveira and J.L. Ara\'ujo", title = "A greedy randomized adaptive search procedure for transmission expansion planning", journal = "IEEE Transactions on Power Systems", volume = "16", pages = "247--253", year = "2001", annote = "This paper presents a {GRASP} for a long term transmission expansion planning problem. The greedy function is to minimize the load curtailment required to eliminate all operational violations. The local search phase is based on circuit exchanges, i.e. the procedure exchanges selected additions with unselected additions.", } @techreport{BruBat01a, author = "M. Brunato and R. Battiti", title = "A multistart randomized greedy algorithm for traffic grooming on mesh logical topologies", institution = "Department of Mathematics, University of Trento", address = "Trento, Italy", year = "2001", annote = "The authors addresse a logical topology design problem on Dense Wavelength Division Multiplexing (DWDM) optical networks, where the traffic is measured at sub-wavelength resultion and the key factor to determine the fitness of a solution is the number of lightpaths required. They describe a {GRASP}-like heuristic for minimizing the number of lightpaths. The greedy choice takes into account the load associated with each lightpath, i.e. an integer value representing the number of traffic unit routed to that lightpath." } @Article{CanResRib01a, author = "S.A. Canuto and M.G.C. Resende and C.C. Ribeiro", title = "Local search with perturbation for the prize-collecting {Steiner} tree problems in graphs", journal = "Networks", volume = "38", pages = "50--58", year = "2001", annote = "Several local search strategies have been investiged in this paper for solving the prize-collecting {Steiner} tree problems in graphs, including path relinking, VNS, and a {GRASP} that uses some cost perturbations. The greedy choice takes into account the input edge weights, while the local search routine defines as neighborhood of a solution $T(X)$ the set of all minimum spanning trees $T(X')$, where $X'$ differs from $X$ for exactly one node.", } @incollection{ChaMcKMak01a, author = "P. Chardaire and G.P. McKeown and J.A. Maki", title = "Application of {GRASP} to the multiconstraint knapsack problem", booktitle = "EvoWorkshop 2001", editor = "E.J.W. Boers et al.", publisher = "Springer-Verlag Berlin Heidelberg", pages = "30--39", year = "2001", annote = "The authors propose in this paper a number of different implementations of {GRASP} for the multiconstraint knapsack problem. In all implementations, the greedy functions are based on the profit per weight unit associated with each element. $1$-opt and $2$-opt search strategies are used in the local search phase.", } @inproceedings{ChrArm01a, author = "L.M. Christofoletti and V.A. Armentano", title = {{Estrat\'egias de rein\'{\i}cio de busca local baseadas em mem\'oria para programa\c{c}\~ao de tarefas em uma m\'aquina}}, booktitle = {{Proceedings of te XXXIII Brazilan Symposium on Operations Research}}, city = "Campos do Jord\~ao, Brazil", month = "November 6--9", annote = "In this paper, it is shown that incorporating adaptive memory in multistart random methods improves their performance. To validate their thesis, the authors address the well known difficult combinatorial optimization problem consisting in minimizing the total job tardiness on a single machine with sequence dependent setup times and implemented a {GRASP} combined with some basic principles of memory utilization during the construction phase. In Portuguese.", year = "2001", pages = "1381--1389" } @inproceedings{DelGanRod01a, author = "X. Delorme and X. Gandibleux and J. Rodriguez", title = "{GRASP} for set packing problems", booktitle = "Proceedings of the Operational Research Peripatetic Post-Graduate Programme (ORP3)", city = "Paris, France", month = "September 26-29", year = "2001" , pages = " ", annote = "This paper concerns {GRASP} implementations for the set packing problem, a classical combinatorial optimization problem related to the set covering problem and to the node packing problem. In fact, the node packing problem is a particular set packing problem, in which there are only incompatibilities between two items. Vice-versa, all set packing problems can be reformulated as a node packing problem in which each incompatibility is splitted into some incompatibilities between two items. To solve the problem, the authors propose two different {GRASP} implementations. The first {GRASP} is inspired by a {GRASP} implementation that appeared in the literature (for the set covering problem). The neighborhood structure adopted is a $k$-$p$ exchange, which consists in fixing to $0$ the value of $k$ variables and to $1$ the value of the remaining $p$ variables. The authors investigated the $0$-$1$, $1$-$1$, $2$-$1$, and $1$-$2$ exchange neighborhoods. The second {GRASP} is inspired by a {GRASP} implementation that appeared in the literature (for the node packing) problem and uses a $1$-$2$ exchange neighborhood.", } @inproceedings{DelRodGan01a, author = {X. Delorme and J. Rodriguez and X. Gandibleux}, title = {Heuristics for railway infrastructure saturation}, booktitle = {Electronic Notes in Theoretical Computer Science}, volume = {50}, issue = {1}, publisher = {Elsevier}, editor = {Christos Zaroliagis}, annote = {To evaluate railway infrastructure capacity, two heuristics appraoches in this paper are proposed, including a {GRASP}. The greedy function is defined on the number of mathematical model contraints concerned by decision variables, while local search procedure uses a $k$-$p$ exchange neighborhood.}, year = {2001}, } @Article{Fer01a, author = "T. Ferreira de Noronha", title = "Algoritmos e estrat\'egias de solu\c c\~ao para o problema do gerenciamento de sondas de produ\c c\~ao terrestre na bacia petrol\'{\i}fera potiguar", journal = "Revista Electr\^onica de Inicia\c c\~ao Cientifica", volume = "1", year = "2001", annote = "Several different heuristics are proposed, including a {GRASP}. The greedy function is a simple cost function related to the production, while the local search phase looks for improving solutions by swapping paths. In Portuguese.", } @Article{FesParRes01a, author = "P. Festa and P.M. Pardalos and M.G.C. Resende", title = "Algorithm 815: {FORTRAN} Subroutines for Computing Approximate Solution to Feedback Set Problems using {GRASP}", journal = "ACM Transactions on Mathematical Software", volume = "27", pages = "456--464", year = "2001", annote = "A set of ANSI standard Fortran 77 subroutines for approximately solving the feedback vertex and arc set problems is described.", } @inproceedings{FesRai01a, author = "P. Festa and G. Raiconi", title = "{GRASP} in switching input optimal control synthesis", booktitle = "Proceedings of MIC'2001", city = "Porto, Portugal", month = "July 16-20", year = "2001", pages = "381--385", annote = "Several optimal control problems are introduced in this paper and a {GRASP} is also designed. In the construction phase of the proposed {GRASP}, the greedy criterion minimizes the quadratic costs in the Riccati equation. The neighborhood structure used in the local search phase is defined on the Hamming distance." } @phdthesis{Gar01a, author = "J.A. D\'{\i}az Garc\'{\i}a", title = "Algorithmic approaches for the single source capacitated plant location problem", school = "Departamento d'Estad\'{\i}stica i Investigaci\'o Operativa, Univarsitat Polit\'ecnica de Catalunya", address = "Barcelona, Spain", annote = {Scope of this thesis has been to propose several algorithmic alternatives based on both exact and approximate methods for efficiently solving the single source capacitated plant location problem. One of the proposals is a reactive {GRASP} that uses a greedy function based on a percentage of the sum of the cost associated with opening a plant and the cost of allocating clients. The local search procedure uses two neighborhood structures: a client shift neighborhood and a client swap neighborhood.}, year = "2001" } @inproceedings{GarLozSmiGue01a, author = {J.M. Garc\'{\i}a and S. Lozano and K. Smith and F. Guerrero}, title = {{A comparison of {GRASP} and an exact method for solving a production and delivery scheduling problem}}, booktitle = {{First International Workshop on Hybrid Intelligent Systems (HIS'01), Adelaide, Australia}}, month = {December}, annote = {The production and delivery scheduling problem consists in selecting due dated orders to be processed by a manufacturing plant and immediately delivered to the customer. Moreover, a limited number of vehicles are available for delivery. To solve the problem, the authors propose an exact approach and a {GRASP}. The greedy criterion takes into account order weights, while the local search procedure uses an exchange neighborhood.}, year = {2001} } @inproceedings{GomOli01a, author = "A.M. Gomes and J.F. Oliveira", title = "A {GRASP} approach to the nesting problem", booktitle = "Proceedings of MIC'2001", city = "Porto, Portugal", month = "July 16-20", year = "2001", pages = "47--52", annote = "In this paper, a {GRASP} is proposed for solving a variant of the classical nesting problem, whose objective is to minimize the length of a single plate used to produce a given set of smaller pieces. Two greedy criteria have been tried. The first one is the layout length, measured as the maximum coordinate in the current layout, while the second one is the added internal waste, measured as the potential area lost when placing one piece. The local search phase uses neighbors obtained by exchanging pairs of pieces in the sequence output of the construction phase." } @Article{HamRad01a, author = "P.L. Hammer and D.J. {Rader,~Jr.}", title = "Maximally disjoint solutions of the set covering problem", journal = "Journal of Heuristics", volume = "7", pages = "131--144", year = "2001", annote = "This paper describes the problem of finding two solutions of a set covering problem that have a minimum number of common variables. It is proved that this problem is NP-complete and three heuristics are proposed for solving it. Two of these algorithms find the solutions sequentially. One of them is a {GRASP}. The third algorithm finds solutions simultaneously. Each proposed heuristic is a variant of the standard greedy method for set covering problems, whose greedy choice favors unselected variables that maximize the number of uncovered rows that become covered. To reduce the overlap of any pair of solutions, a local search algorithm is used that swaps at each iteration parts of the solution found with a set of variables not in it.", } @inproceedings{KumSriWanLanRam01a, author = {K. Kumaran and A. Srinivasan and Q. Wang and S. Lanning and K.G. Ramakrishnan}, title = {Efficient algorithms for location and sizing problems in network design}, booktitle = {Global Telecommunications Conference, 2001 (GLOBECOM '01)}, publisher = {IEEE}, volume = {4}, annote = {The authors develop algorithms based on linear programming and a slight modified {GRASP}, in which the costruction phase is performed at random. Given an initial solution, the local search procedure exhaustively evaluate objective function value for all possible single location changes.}, year = {2001}, pages = {2586--2590} } @Article{LagMar01b, author = "M. Laguna and R. Mart\'{\i}", title = "A {GRASP} for coloring sparse graphs", journal = "Computational Optimization and Applications", volume = "19", pages = "165--178", year = "2001", annote = "A {GRASP} for graph coloring is presented. The {GRASP} construction phase constructs the next coloring, one color at time. The greedy function chooses the vertex having the maximum degree among the uncolored vertices adjacent to at least one colored vertex. At each step, the local search combines the two smallest cardinality color classes into one and tries to find a valid color for each violating vertex.", } @Article{LouPaiPor01a, author = "H.R. Louren\c{c}o and J.P. Paix{\~{a}}o and R. Portugal", title = "Multiobjective metaheuristics for the bus-driver scheduling problem", journal = "Transportation Sciences", volume = "35", pages = "331--343", year = "2001", annote = "To solve real driver scheduling problems in public transportation bus companies several metaheuristics are presented in this paper, including a {GRASP}. To design {GRASP}, the authors define a set $N$ of $n$ duties and used a greedy criterion based on a quantity proportional to the cost associated with the duties. The local search procedure uses a $1$-exchange neighborhood.", } @Article{Mar01a, author = "R. Mart\'{\i}", title = "Arc crossing minimization in graphs with {GRASP}", journal = "IIE Transactions", volume = "33", pages = "913--919", year = "2001", annote = "A {GRASP} for minimizing straight-line crossings in hierarchical graphs is presented. {GRASP} is shown to be faster than more complex heuristics but produces lower-quality solutions. It is not as fast as simple heuristics, but finds better-quality solutions. Hence, it is a candidate for practical implementation in graph drawing systems.", } @Article{MarEst01a, author = "R. Mart\'{\i} and V. Estruch", title = "Incremental bipartite drawing problem", journal = "Computers and Operations Research", volume = "28", pages = "1287--1298", year = "2001", annote = "The goal of limiting the number of arc crossings is a well accepted criterion of how well a graph is drawn. Incremental graph drawing supports interactive updates by users. A {GRASP} is proposed for the incremental arc crossing minimization problem for bipartite graphs. Computational experiments are done on 450 instances and results are compared with a branch and bound algorithm.", } @Article{MedResVei01a, author = "M.C. Medeiros and M.G.C. Resende and A. Veiga", title = "Piecewise linear time series estimation with {GRASP}", journal = "Computational Optimization and Applications", volume = "19", pages = "127--144", year = "2001", annote = "This paper describes a {GRASP} to build piecewise linear statistical models with multivariate thresholds. The construction phase consists of sequentially choosing hyperplanes until the maximum number of hyperplanes is reached. The greedy function orders the possible hyperplanes with respect to the sum of squared errors of the fitted data. The local search is a $2$-exchange heuristic.", } @inproceedings{MilPesBraLabRey01a, author = "R.L. Milid\'{\i}u and A.A. Pessoa and V. Braconi and E.S. Laber and P.A, Rey", title = {{Um algoritmo {GRASP} para o problema de transporte de derivados de petr\'oleo em oleodutos}}, booktitle = {{Proceedings of te XXXIII Brazilan Symposium on Operations Research}}, city = "Campos do Jord\~ao, Brazil", month = "November 6--9", year = "2001", pages = "237--246", annote = "This paper describes a {GRASP} for petroleum derivatives transportation in pipelines. The greedy function of the {GRASP} proposed in this paper is a simple cost function obtained as sum of the total volumes of the product. The local search noeighborhood structure is defined by small perturbations of the current solution involving priorities." } @inproceedings{MotOchMar01a, author = "L. Motta and L.S. Ochi and C. Martinhon", title = {{GRASP} metaheuristics to the generalized covering tour problem}, booktitle = "Proceedings of MIC'2001", city = "Porto, Portugal", month = "July 16-20", pages = "387--391", annote = {Let $G(V\cup W,E)$ be an undirected graph, where $V\cup W=\{1,2,\ldots,n\}$ is the node set, and $E=\{(i,j)\vert i,j\in V\cup W,\ i