A note on “the facility location problem with limited distances”

Abstract

In this paper, it is shown that the polynomially bounded enumerative procedure to solve the facility location problem with limited distances, originally described by Drezner, Mehrez, and Wesolowsky [Drezner Z, Mehrez A, Wesolowsky GO (1991) The facility location problem with limited distances. Transportation Sci. 25(3):183–187.], and subsequently corrected by Aloise, Hansen, and Liberti [Aloise D, Hansen P, Liberti L (2012) An improved column generation algorithm for minimum sum-of-squares clustering. Math. Programming 131(1–2):195–220.], can still fail to optimally solve the problem. Conditions under which the procedures succeed are identified. A new modified algorithm is presented that solves the facility location problem with limited distances. It is further shown that the proposed correction is complete in that it does not require further corrections.