@article{AhmOsm03a, author = {S. Ahmadi and I.H. Osman}, title = {Greedy random adaptive memory programming search for the capacitated clustering problem}, journal = {European Journal of Operational Research}, volume = {}, number = {}, year = {2003}, pages = {}, note = {To appear.}, annote = "Given a set $N$ of $n$ points, the capacitated clustering problem consists in finding a partition of $N$ in $p$ clusters such that the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of $p$ centers that minimizes the total scatter of points allocated to these centers. In order to introduce some sort of memory into the pure {GRASP} framework, the authors propose a GRAMPS framework, which is an hybrid of {GRASP} and AMP (Adaptive Memory Programming). Local search procedure is descent based on a restricted $\lambda$-interchange neighborhood." } @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." } @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{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{CanCalCabVeg02a, author = "J.D.B. Cano and R.J. Cabrera and J.M.M. Vega", title = "Procedimientos constructivos adaptivos ({GRASP}) para el problema del empaquetado bidimensional", journal = "Revista Iberoamericana de Inteligencia Artificial", volume = "15", pages = "26--33", year = "2002", annote = "To solve the bidimensional packing problem, several constructive adaptive heuristics are proposed in this paper. Some of them realize only the {GRASP} construction phase, while others apply also a local search phase. Computational results show that in many cases the proposed heuristics obtain the optimal solution. In Spanish.", } @inproceedings{CanCorHerSan02a, author = "J.R. Cano and O. Cord\'on and F. Herrera and L. S\'anchez", title = "A {GRASP} Algorithm for clustering", editor = {F. J. Garijo and J.C.R. Santos and M. Toro}, booktitle = {Advances in Artificial Intelligence - IBERAMIA 2002, 8th Ibero-American Conference on AI, Seville, Spain, November 12-15, 2002, Proceedings}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {2527}, pages = {214--223}, year = {2002}, isbn = {3-540-00131-X}, annote = "A {GRASP} for cluster analysis is described. Construction is done using a randomized greedy Kaufman procedure and local search uses the $K$-means algorithm. High quality solutions are found for benchmark problems. The best solutions are found with a hybid {GRASP}/$K$-means with Kaufman initialization." } @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{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.", } @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.", } @Article{FesParResRib02a, author = "P. Festa and P.M. Pardalos and M.G.C. Resende and C.C. Ribeiro", title = "Randomized heuristics for the {MAX-CUT} problem", journal = "Optimization Methods and Software", volume = "7", pages = {1033--1058}, year = "2002", annote = {Given an undirected graph with edge weights, the max-cut problem consists in finding a partition of the nodes into two subsets, such that the sum of the weights of the edges having endpoints in different subsets is maximized. For solving this well-known NP-hard problem, the authors propose and test a {GRASP}, a variable neighborhood search (VNS), a path relinking intensification heuristic, and new hybrid heuristics that combine {GRASP}, VNS, and path relinking. The greedy function of the pure {GRASP} is related to the sum of the weights of the edges in each cut. Let $(S,\bar S)$ be the current cut solution and let $v\in V$ be a vertex, then the pure {GRASP} local search associates to $v$ either the neighbor $(S \setminus \{v\}, \bar S\cup \{v\})$ if $v \in S$, or the neighbor $(S \cup \{v\}, \bar S \setminus \{v\})$ otherwise. Computational results indicate that the proposed randomized heuristics find near-optimal solutions. On a set of standard test problems, new best known solutions were produced for many of the instances.}, } @article{PacVel03a, author = {J. Pacheco and O. Valencia}, title = {Design of hybrids for the minimum sum-of-squares clustering problem}, journal = {Computational Statistics and Data Analysis}, volume = {43}, pages = {235--248}, annote = {For the non-hierchical clustering problem under the criterion of minimum sum-of-squares clustering a set of heuristics are proposed that incorporate genetic operators, local search, and tabu search. The authors compare their algorithms with other heuristic approaches including a {GRASP} on a set of test problems.}, year = {2003} } @article{DelGanRod04a, author = "X. Delorme and X. Gandibleux and J. Rodriguez", title = "{GRASP} for set packing problems", journal = "European J. of Operational Research", volume = "153", number = "3", pages = "564--580", year = "2004", annote = " In this paper, GRASP is applied to solve the set packing problem. Several construction phases are studied and improvements based on advanced strategies are evaluated. These include reactive GRASP, path relinking, and a procedure involving the diversification of the selection (using a learning process).", } @Article{CanCorHerSan02b, author = "J.R. Cano and O. Cord\'on and F. Herrera and L. S\'anchez", title = {{A greedy randomized adaptive search procedure applied to the clustering problem as an initialization process using K-means as a local search procedure}}, journal = {Journal of Intelligent and Fuzzy Systems}, volume = {12}, pages = {235--242}, annote = {A {GRASP} is proposed for cluster analysis using a probabilistic greedy Kaufman initialization in the construction phase and K-Means as local search procedure.}, year = {2002} }