A Semidefinite Approach for the Single ...

This paper summarizes several results from the author’s Master’s thesis. We propose a new semidefinite approach for the NP-hard single row facility layout problem (SRFLP) which is the problem of arranging n facilities of given lengths on a straight line, while minimizing a weighted sum of distances between all facility pairs. We tighten existing semidefinite relaxations with further inequalities and use an algorithmic method not yet considered for the SRFLP. Our new approach outperforms all other approaches in the literature and significantly reduces the best known duality gaps for all unsolved benchmark instances with n≤100. Many instances with up to n=81 are solved for the first time.