A Lagrangean heuristic for the staircase cost facility location problem

In this research we present a Lagrangean heuristic for the staircase cost facility location problem (SCFLP), which generalizes the well-known capacitated facility location problem (CFLP) by permitting multiple types of facilities with different cost and operating profiles to be considered at each candidate site. In both problems, the objective is to select a set of facility locations on a network to serve a specified set of demands at lowest cost. The CFLP=s restriction of one candidate facility per site greatly limits its practical application, because decision-makers almost always have the opportunity to choose among several types of technologies. But because of its large number of integer variable, the SCFLP is quite difficult to solve. We show that by adapting Lagrangean problem reduction techniques developed for the CFLP, this complexity can be reduced, leading to a problem easily solvable using ordinary mixed-integer programming.