A Lagrangean heuristic for the facility location problem with staircase costs

In this paper we develop and compare heuristic solution methods for the capacitated facility location problem with staircase shaped production cost functions, a linear mixed integer programming problem with a large proportion of integer variables. We propose a Lagrangean heuristic, including Lagrangean relaxation and subgradient optimization as a base for an efficient primal heuristic, and using convex piecewise linearizations of the staircase shaped cost functions to get good initial upper and lower bounds as well as initial dual solutions. Based on the solution of the Lagrangean relaxation a transportation problem which yields primal feasible solutions is constructed. For comparison we have generalized the well-known ADD heuristic for the capacitated plant location problem to enable the application to the staircase cost facility location problem, and improved it by including certain priority rules. Computational results are given indicating that the Lagrangean heuristic is quite promising.