lagrangean heuristics

A hybrid Lagrangean heuristic with GRASP and path-relinking for set K-covering

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

    The set multicovering or set K-covering problem is an extension of the classical set covering problem, in which each object is required to be covered at least K times. The problem finds applications in the design of communication networks and in computational biology. We describe a GRASP with path-relinking heuristic for the set K-covering problem, … Read more

    Solving large p-median problems using a Lagrangean heuristic

  • AndrĂ©a Cynthia Santos
    • Categories Approximation Algorithms, Facility Planning and Design, Telecommunications Tags , ,

    The p-median problem consists in locating p medians in a given graph, such that the total cost of assigning each demand to the closest median is minimized. In this work, a Lagrangean heuristic is proposed and it uses two dual information to build primal solutions. It outperforms a classic heuristic based on the same Lagrangean … Read more