30
2 Layout on a Single Row
and semidefinite relaxations for binary problems can be found in Laurent and Rendl
(2005).
The SREFLP can be viewed as a special case of the famous quadratic assignment
problem. Some work has focused on exploiting its special structure, most recently
Palubeckis (2012) and Hungerländer (2014). A formulation of the MBRLF was
given in Kouvelis and Chiang (1996), but the computation of the backward distance
was incorrect, as explained in Brusco (2004), where a corrected formulation is
provided. The formulation presented in Sect. 2.9 follows the approach of Brusco
(2004).
References
Adams WP, Sherali HD (2015) RLT insights into lift-and-project closures. Optimization Letters
9(1):19–39
Amaral ARS (2006) On the exact solution of a facility layout problem. Eur J Oper Res 173(2):508–
518
Amaral ARS (2008) An exact approach to the one-dimensional facility layout problem. Operations
Research 56(4):1026–1033
Amaral ARS (2009) A new lower bound for the single row facility layout problem. Discrete Appl
Math 157(1):183–190
Anjos MF, Vannelli A (2008) Computing globally optimal solutions for single-row layout problems
using semidefinite programming and cutting planes. INFORMS J Comput 20(4):611–617
Anjos MF, Kennings A, Vannelli A (2005) A semidefinite optimization approach for the single-row
layout problem with unequal dimensions. Discrete Optimization 2(2):113–122
Boyd SP, Vandenberghe L (2004) Convex optimization. Cambridge University Press
Brusco MJ (2004) Optimal solution methods for the minimum-backtracking row layout problem.
IIE Transactions 36(2):181–189
Heragu SS (2008) Facilities design. CRC Press
Heragu SS, Kusiak A (1991) Efficient models for the facility layout problem. Eur J Oper Res
53(1):1–13
Hungerländer P (2014) Single-row equidistant facility layout as a special case of single-row facility
layout. Int J Prod Res 52(5):1257–1268
Hungerländer P, Rendl F (2013) A computational study and survey of methods for the single-row
facility layout problem. Comput Optim Appl 55(1):1–20
Kouvelis P, Chiang WC (1996) Optimal and heuristic procedures for row layout problems in
automated manufacturing systems. J Oper Res Soc 47(6):803–816
Laurent M, Rendl F (2005) Semidefinite programming and integer programming. Handbooks Oper
Res Manag Sci 12:393–514
Lovász L, Schrijver A (1991) Cones of matrices and set-functions and 0–1 optimization. SIAM J
Optim 1(2):166–190
Love R, Wong J (1976) On solving a one-dimensional space allocation problem with integer
programming. INFOR Inf Syst Oper Res 14(2):139–143
Palubeckis G (2012) A branch-and-bound algorithm for the single-row equidistant facility layout
problem. OR Spectrum 34(1):1–21
Sanjeevi S, Kianfar K (2010) A polyhedral study of triplet formulation for single row facility layout
problem. Discrete Appl Math 158(16):1861–1867
Sherali HD, Adams WP (1990) Relaxations between the continuous and convex hull representations. SIAM J Discrete Math 3(3):411–430
2 Layout on a Single Row
and semidefinite relaxations for binary problems can be found in Laurent and Rendl
(2005).
The SREFLP can be viewed as a special case of the famous quadratic assignment
problem. Some work has focused on exploiting its special structure, most recently
Palubeckis (2012) and Hungerländer (2014). A formulation of the MBRLF was
given in Kouvelis and Chiang (1996), but the computation of the backward distance
was incorrect, as explained in Brusco (2004), where a corrected formulation is
provided. The formulation presented in Sect. 2.9 follows the approach of Brusco
(2004).
References
Adams WP, Sherali HD (2015) RLT insights into lift-and-project closures. Optimization Letters
9(1):19–39
Amaral ARS (2006) On the exact solution of a facility layout problem. Eur J Oper Res 173(2):508–
518
Amaral ARS (2008) An exact approach to the one-dimensional facility layout problem. Operations
Research 56(4):1026–1033
Amaral ARS (2009) A new lower bound for the single row facility layout problem. Discrete Appl
Math 157(1):183–190
Anjos MF, Vannelli A (2008) Computing globally optimal solutions for single-row layout problems
using semidefinite programming and cutting planes. INFORMS J Comput 20(4):611–617
Anjos MF, Kennings A, Vannelli A (2005) A semidefinite optimization approach for the single-row
layout problem with unequal dimensions. Discrete Optimization 2(2):113–122
Boyd SP, Vandenberghe L (2004) Convex optimization. Cambridge University Press
Brusco MJ (2004) Optimal solution methods for the minimum-backtracking row layout problem.
IIE Transactions 36(2):181–189
Heragu SS (2008) Facilities design. CRC Press
Heragu SS, Kusiak A (1991) Efficient models for the facility layout problem. Eur J Oper Res
53(1):1–13
Hungerländer P (2014) Single-row equidistant facility layout as a special case of single-row facility
layout. Int J Prod Res 52(5):1257–1268
Hungerländer P, Rendl F (2013) A computational study and survey of methods for the single-row
facility layout problem. Comput Optim Appl 55(1):1–20
Kouvelis P, Chiang WC (1996) Optimal and heuristic procedures for row layout problems in
automated manufacturing systems. J Oper Res Soc 47(6):803–816
Laurent M, Rendl F (2005) Semidefinite programming and integer programming. Handbooks Oper
Res Manag Sci 12:393–514
Lovász L, Schrijver A (1991) Cones of matrices and set-functions and 0–1 optimization. SIAM J
Optim 1(2):166–190
Love R, Wong J (1976) On solving a one-dimensional space allocation problem with integer
programming. INFOR Inf Syst Oper Res 14(2):139–143
Palubeckis G (2012) A branch-and-bound algorithm for the single-row equidistant facility layout
problem. OR Spectrum 34(1):1–21
Sanjeevi S, Kianfar K (2010) A polyhedral study of triplet formulation for single row facility layout
problem. Discrete Appl Math 158(16):1861–1867
Sherali HD, Adams WP (1990) Relaxations between the continuous and convex hull representations. SIAM J Discrete Math 3(3):411–430