metaheuristics

GRASP and path-relinking: Recent advances and applications

  • Mauricio G.C. Resende
  • Celso C. Ribeiro
    • Categories Meta Heuristics Tags , , ,

    This paper addresses recent advances and application of hybridizations of greedy randomized adaptive search procedures (GRASP) and path-relinking. We present a template for implementing path-relinking as an intensification procedure for GRASP. Enhancements to the procedure, recently described in the literature, are reviewed. The effectiveness of the procedure is illustrated experimentally. CitationAT&T Labs Research Technical Report, … Read more

    A GRASP with path-relinking for the p-median problem

  • Mauricio G.C. Resende
  • Renato F. Werneck
    • Categories Applications - OR and Management Sciences, Meta Heuristics Tags , , , ,

    Given N customers and a set F of M potential facilities, the P-median problem consists in finding a subset of F with P facilities such that the cost of serving all customers is minimized. This is a well-known NP-complete problem with important applications in location science and classification (clustering). We present here a GRASP (Greedy … Read more

    Randomized heuristics for the MAX-CUT problem

  • Paola Festa
  • Panos M. Pardalos
  • Mauricio G.C. Resende
  • Celso C. Ribeiro
    • Categories Meta Heuristics Tags , , , ,

    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. It is a well-known NP-hard problem with applications in several fields, including VLSI design and statistical physics. … Read more

    A hybrid improvement heuristic for the one-dimensional bin packing problem

  • Dario J. Aloise
  • Adriana C. Alvim
  • Fred Glover
  • Celso C. Ribeiro
    • Categories Combinatorial Optimization, Meta Heuristics Tags , , ,

    We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several features: the use of lower bounding strategies; the generation of initial solutions by reference to the dual min-max problem; the use of load redistribution based on dominance, differencing, and unbalancing; and the inclusion of an improvement process … Read more

    A GRASP heuristic for the capacitated minimum spanning tree problem using a memory-based local search strategy

  • Christophe Duhamel
  • Celso C. Ribeiro
  • Mauricio C. Souza
    • Categories Combinatorial Optimization, Graphs and Matroids, Meta Heuristics Tags , , ,

    We describe a new neighborhood structure for the capacitated minimum spanning tree problem. This neighborhood structure is used by a local search strategy, leading to good trade-offs between solution quality and computation time. We also propose a GRASP with path-relinking heuristic. It uses a randomized version of a savings heuristic in the construction phase and … Read more

    Greedy randomized adaptive search procedures

  • Mauricio G.C. Resende
  • Celso C. Ribeiro
    • Categories Meta Heuristics Tags , ,

    GRASP is a multi-start metaheuristic for combinatorial problems, in which each iteration consists basically of two phases: construction and local search. The construction phase builds a feasible solution, whose neighborhood is investigated until a local minimum is found during the local search phase. The best overall solution is kept as the result. In this chapter, … Read more

    A GRASP with path-relinking for private virtual circuit routing

  • Mauricio G.C. Resende
  • Celso C. Ribeiro
    • Categories Meta Heuristics, Network Optimization, Telecommunications Tags , , , , , , , ,

    A frame relay service offers virtual private networks to customers by provisioning a set of long-term private virtual circuits (PVCs) between customer endpoints on a large backbone network. During the provisioning of a PVC, routing decisions are made without any knowledge of future requests. Over time, these decisions can cause inefficiencies in the network and … Read more

    A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs

  • Celso C. Ribeiro
  • Eduardo Uchoa
  • Renato F. Werneck
    • Categories Meta Heuristics, Telecommunications, VLSI layout Tags , , , ,

    We propose and describe a hybrid GRASP with weight perturbations and adaptive path-relinking heuristic (HGP+PR) for the Steiner problem in graphs. In this multi-start approach, the greedy randomized construction phase of a GRASP is replaced by the use of several construction heuristics with a weight perturbation strategy that combines intensification and diversification elements, as in … Read more

    Strategies for the Parallel Implementation of Metaheuristics

  • Van-Dat Cung
  • Simone Martins
  • Celso C. Ribeiro
  • Catherine Roucairol
    • Categories Meta Heuristics Tags ,

    Parallel implementations of metaheuristics appear quite naturally as an effective alternative to speed up the search for approximate solutions of combinatorial optimization problems. They not only allow solving larger problems or finding improved solutions with respect to their sequential counterparts, but they also lead to more robust algorithms. We review some trends in parallel computing … Read more

    GRASP: An annotated bibliography

  • Mauricio G.C. Resende
  • Paola Festa
    • Categories Meta Heuristics Tags , ,

    A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. It is a multi-start or iterative process, in which each {GRASP} iteration consists of two phases, a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed … Read more