Research output: Working paper
Research output: Working paper
}
TY - UNPB
T1 - A polyhedral approach to the single row facility layout problem
AU - Letchford, A N
AU - Amaral, Andre
N1 - This was eventually published as: A.R.S. Amaral & A.N. Letchford (2013) A polyhedral approach to the single-row facility layout problem. Math. Program., 141(1-2), 453-477.
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
KW - facility layout
KW - polyhedral combinatorics
KW - branch-and-cut
M3 - Working paper
T3 - Management Science Working Paper Series
BT - A polyhedral approach to the single row facility layout problem
PB - The Department of Management Science
CY - Lancaster University
ER -