A new lower bound for the single row facility layout problem

Single row facility layout is the NP-hard problem of arranging n departments of given lengths on a line so as to minimize the weighted sum of the distances between department pairs. In this paper, we define a polytope associated to the problem and present a partial linear description whose integral points are the incidence vectors of a layout. We propose a new lower bound for the problem by optimizing a linear program over the partial description given and using some valid inequalities, which are introduced here, as cutting planes. Several instances from the literature as well as new large instances with size n = 33 and n = 35 are considered in the computational tests. For all the instances tested, the proposed lower bound achieves the cost of an optimal layout within reasonable computing time. (c) 2008 Elsevier B.V. All rights reserved.