2.10 References and Further Reading
29
d
b
ij ≥ 0, 1 ≤ i = j ≤ n,
(2.79)
α ij + α ji = 1, 1 ≤ i < j ≤ n,
(2.80)
α ij + α jk + α ki ≤ 2, 1 ≤ i = j = k ≤ n,
(2.81)
α ij ∈ {0, 1}, 1 ≤ i = j ≤ n,
(2.82)
where we use the constraints on the α variables derived in Sect. 2.5.
2.10 References and Further Reading
The example of Tables 2.1 and 2.2 was adapted from Heragu (2008). Boyd and
Vandenberghe (2004) is an excellent reference on the theory, algorithms, and
applications of convex optimization. The compact formulation (2.6) was expressed
in Simmons (1969), where the centrality of betweenness was observed for the first
time.
The first MILO formulations of the SRFLP were proposed by Love and
Wong (1976) and Heragu and Kusiak (1991). Amaral (2006) proposed a MILO
formulation that gives a tighter linear relaxation than the Heragu and Kusiak (1991)
formulation. This is presented in Sect. 2.3.4.
The approach sketched in Sect. 2.4, where the betweenness variables are used,
was originally proposed in Amaral (2009). A polyhedral study of this formulation
can be found in Sanjeevi and Kianfar (2010).
The quadratic integer model was introduced in Amaral (2008). The quadratic
integer model of Sect. 2.5 has an objective function inspired by the integer linear
model of Sect. 2.4: it is the model of Amaral (2008) with a different objective
function. The relaxation hierarchy discussed here was introduced in Sherali and
Adams (1990, 1994), and Adams and Sherali (2015). It can be obtained by applying
the relaxation described in Adams and Sherali (2015) to the quadratic integer model
of Sect. 2.5.
Section 2.7 presents the first SDO approach for the SRFLP as introduced in Anjos
et al (2005). The combination of the SDO approach and triangle inequalities was
used in Anjos and Vannelli (2008) to compute global optimal layouts for singlerow facility layout problems with up to 30 facilities. An interesting study of the
SDO approach for one-dimensional layout problems is given by Hungerländer and
Rendl (2013). Sufficient conditions for a matrix to be of the form (2.61) and related
properties of PSD matrices with all diagonal entries equal to 1 are discussed in,
for example, Wolkowicz and Anjos (2002). The SDO approach is to date the best
approach for solving large instances of the SRFLP.
Valid inequalities such as (2.75) can be obtained using the Lovász–Schrijver
procedure introduced in Lovász and Schrijver (1991). An excellent presentation of
this procedure as well as other frameworks for constructing hierarchies of linear
29
d
b
ij ≥ 0, 1 ≤ i = j ≤ n,
(2.79)
α ij + α ji = 1, 1 ≤ i < j ≤ n,
(2.80)
α ij + α jk + α ki ≤ 2, 1 ≤ i = j = k ≤ n,
(2.81)
α ij ∈ {0, 1}, 1 ≤ i = j ≤ n,
(2.82)
where we use the constraints on the α variables derived in Sect. 2.5.
2.10 References and Further Reading
The example of Tables 2.1 and 2.2 was adapted from Heragu (2008). Boyd and
Vandenberghe (2004) is an excellent reference on the theory, algorithms, and
applications of convex optimization. The compact formulation (2.6) was expressed
in Simmons (1969), where the centrality of betweenness was observed for the first
time.
The first MILO formulations of the SRFLP were proposed by Love and
Wong (1976) and Heragu and Kusiak (1991). Amaral (2006) proposed a MILO
formulation that gives a tighter linear relaxation than the Heragu and Kusiak (1991)
formulation. This is presented in Sect. 2.3.4.
The approach sketched in Sect. 2.4, where the betweenness variables are used,
was originally proposed in Amaral (2009). A polyhedral study of this formulation
can be found in Sanjeevi and Kianfar (2010).
The quadratic integer model was introduced in Amaral (2008). The quadratic
integer model of Sect. 2.5 has an objective function inspired by the integer linear
model of Sect. 2.4: it is the model of Amaral (2008) with a different objective
function. The relaxation hierarchy discussed here was introduced in Sherali and
Adams (1990, 1994), and Adams and Sherali (2015). It can be obtained by applying
the relaxation described in Adams and Sherali (2015) to the quadratic integer model
of Sect. 2.5.
Section 2.7 presents the first SDO approach for the SRFLP as introduced in Anjos
et al (2005). The combination of the SDO approach and triangle inequalities was
used in Anjos and Vannelli (2008) to compute global optimal layouts for singlerow facility layout problems with up to 30 facilities. An interesting study of the
SDO approach for one-dimensional layout problems is given by Hungerländer and
Rendl (2013). Sufficient conditions for a matrix to be of the form (2.61) and related
properties of PSD matrices with all diagonal entries equal to 1 are discussed in,
for example, Wolkowicz and Anjos (2002). The SDO approach is to date the best
approach for solving large instances of the SRFLP.
Valid inequalities such as (2.75) can be obtained using the Lovász–Schrijver
procedure introduced in Lovász and Schrijver (1991). An excellent presentation of
this procedure as well as other frameworks for constructing hierarchies of linear