12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > A polyhedral approach to the single row facilit...
View graph of relations

« Back

A polyhedral approach to the single row facility layout problem

Research output: Contribution to journalJournal article

Published

Journal publication date10/2013
JournalMathematical Programming
Journal number1-2
Volume141
Number of pages25
Pages453-477
Early online date21/03/12
Original languageEnglish

Abstract

The Single Row Facility Layout Problem (SRFLP) is the NP-hard problem of arranging facilities on a line, while minimizing a weighted sum of the distances between facility pairs. In this paper, a detailed polyhedral study of the SRFLP is performed, and several huge classes of valid and facet-inducing inequalities are derived. Some separation heuristics are presented, along with a primal heuristic based on multidimensional scaling. Finally, a branch-and-cut algorithm is described and some encouraging computational results are given.