path relinking

GRASP with path-relinking for the weighted maximum satisfiability problem

  • Paola Festa
  • Panos M. Pardalos
  • Mauricio G.C. Resende
  • Leonidas S. Pitsoulis
    • Categories Meta Heuristics, Stochastic Approaches Tags , , ,

    A GRASP with path-relinking for finding good-quality solutions of the weighted maximum satisfiability problem (MAX-SAT) is described in this paper. GRASP, or Greedy Randomized Adaptive Search Procedure, is a randomized multi-start metaheuristic, where at each iteration locally optimal solutions are constructed, each independent of the others. Previous experimental results indicate its effectiveness for solving weighted … Read more

    Parallel Greedy Randomized Adaptive Search Procedures

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

    A GRASP (Greedy Randomized Adaptive Search Procedure) is a metaheuristic for producing good-quality solutions of combinatorial optimization problems. It is usually implemented with a construction procedure based on a greedy randomized algorithm followed by local search. In this Chapter, we survey parallel implementations of GRASP. We describe simple strategies to implement independent parallel GRASP heuristics … Read more

    Parallel Strategies for GRASP with path-relinking

  • Renata M. Aiex
  • Mauricio G.C. Resende
    • Categories Combinatorial Optimization, Meta Heuristics, Parallel Algorithms Tags , , , , , ,

    A Greedy Randomized Adaptive Search Procedure (GRASP) is a metaheuristic for combinatorial optimization. It usually consists of a construction procedure based on a greedy randomized algorithm and local search. Path-relinking is an intensification strategy that explores trajectories that connect high quality solutions. We analyze two parallel strategies for GRASP with path-relinking and propose a criterion … Read more

    GRASP and path-relinking: Recent advances and applications

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

    A greedy randomized adaptive search procedure (GRASP) is a multi-start metaheuristic which applies local search to starting solutions generated by a greedy randomized construction procedure. Until recently, most implementations of GRASP assumed independence of its iterations, thus making no use of memory structures. Path-relinking is an intensification strategy which explores trajectories between elite solutions. Using … Read more

    A hybrid heuristic for the P-median problem

  • Mauricio G.C. Resende
  • Renato F. Werneck
    • Categories Combinatorial Optimization, 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 a multistart hybrid heuristic … Read more

    A methodology for the analysis of parallel GRASP strategies

  • Renata M. Aiex
  • Mauricio G.C. Resende
    • Categories Meta Heuristics, Parallel Algorithms Tags , ,

    In this paper, we describe a methodology for the analysis of greedy randomized adaptive search procedures (GRASP). GRASP is a metaheuristic for combinatorial optimization. It usually consists of a construction procedure based on a greedy randomized algorithm and a local search. Hybrid approaches of GRASP with path-relinking developed for the 3-index assignment problem (AP3) and … Read more

    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

    Parallel GRASP with path-relinking for job shop scheduling

  • Renata M. Aiex
  • S. Binato
  • Mauricio G.C. Resende
    • Categories Meta Heuristics, Scheduling Tags , , , , ,

    In the job shop scheduling problem (JSP), a finite set of jobs is processed on a finite set of machines. Each job is required to complete a set of operations in a fixed order. Each operation is processed on a specific machine for a fixed duration. A machine can process no more than one job … Read more