primal-dual heuristics

The Set Covering Problem Revisited: An Empirical Study of the Value of Dual Information

  • Ş. İlker Birbil
  • Kerem Bülbül
  • Belma Yelbay
    • Categories Integer Programming Tags , , , ,

    This paper investigates the role of dual information on the performances of heuristics designed for solving the set covering problem. After solving the linear programming relaxation of the problem, the dual information is used to obtain the two main approaches proposed here: (i) The size of the original problem is reduced and then the resulting … 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