2.5 Binary Quadratic Optimization Formulation
17
2.5 Binary Quadratic Optimization Formulation
Betweenness is fundamental to the SRFLP. In the previous section we defined
betweenness variables with three indices and modelled the SRFLP using them. We
now show that a betweenness-based model can be built using the binary variables α ij
defined in Sect. 2.3.2 provided we allow a (nonconvex) quadratic objective function.
We also show one way to linearize the resulting formulation and thus obtain a new
binary linear optimization model for the SRFLP.
Recall that α ij = 1 if department i is to the left of department j , and α ij = 0
otherwise. The key observation for a connection to betweenness is that
α ij α jk equals 1 if and only if j is between i and k, and i is to the left of k.
The following theorem shows how to use this observation to express the distance
between any two departments i and j as a quadratic function of the variables α ij .
We give a short proof that shows the connections with the variables and formulation
in Sect. 2.4.
Theorem 2.1 Let n be the number of departments in an instance of the SRFLP,
and i denote the length of department i. The centre-to-centre distance between
departments i and j in a layout can be expressed using the variables α ij as
1
2
(( i + j ) +
n
k=1
k =i,j
k
α ik α kj + α jk α ki
,
(2.34)
with 1 ≤ i < j ≤ n.
Proof Note that β ij k = α ik α kj + α jk α ki , because k is between i and j if and only
if k is after i and before k (which makes the term α ik α kj equal to 1), or k is after j
or before i (which makes the term α jk α ki equal to 1). Thus,
k =i,j
k β ij k =
k =i,j
k (α ik α kj + α jk α ki ).
Substituting this expression into (2.26), we obtain the desired result.
As we did for the variables β ij k in Sect. 2.4, we need to specify constraints
that ensure the consistency of the values assigned to the variables α ij . Note that
the constraints that we now derive are not necessary in Sect. 2.3.4 because they
are implicitly enforced via the continuous variables x i . The reasoning we follow is
similar, but the constraints are different because the α ij have only two indices, and
hence they cannot capture betweenness directly in the way that the variables β ij k
do. Nevertheless, the constraints turn out to be simpler than those in Sect. 2.4.
First, we cannot simultaneously have i to the left of j and j to the left of i. Hence,
we impose the constraints
α ij + α ji = 1, 1 ≤ i < j ≤ n.
17
2.5 Binary Quadratic Optimization Formulation
Betweenness is fundamental to the SRFLP. In the previous section we defined
betweenness variables with three indices and modelled the SRFLP using them. We
now show that a betweenness-based model can be built using the binary variables α ij
defined in Sect. 2.3.2 provided we allow a (nonconvex) quadratic objective function.
We also show one way to linearize the resulting formulation and thus obtain a new
binary linear optimization model for the SRFLP.
Recall that α ij = 1 if department i is to the left of department j , and α ij = 0
otherwise. The key observation for a connection to betweenness is that
α ij α jk equals 1 if and only if j is between i and k, and i is to the left of k.
The following theorem shows how to use this observation to express the distance
between any two departments i and j as a quadratic function of the variables α ij .
We give a short proof that shows the connections with the variables and formulation
in Sect. 2.4.
Theorem 2.1 Let n be the number of departments in an instance of the SRFLP,
and i denote the length of department i. The centre-to-centre distance between
departments i and j in a layout can be expressed using the variables α ij as
1
2
(( i + j ) +
n
k=1
k =i,j
k
α ik α kj + α jk α ki
,
(2.34)
with 1 ≤ i < j ≤ n.
Proof Note that β ij k = α ik α kj + α jk α ki , because k is between i and j if and only
if k is after i and before k (which makes the term α ik α kj equal to 1), or k is after j
or before i (which makes the term α jk α ki equal to 1). Thus,
k =i,j
k β ij k =
k =i,j
k (α ik α kj + α jk α ki ).
Substituting this expression into (2.26), we obtain the desired result.
As we did for the variables β ij k in Sect. 2.4, we need to specify constraints
that ensure the consistency of the values assigned to the variables α ij . Note that
the constraints that we now derive are not necessary in Sect. 2.3.4 because they
are implicitly enforced via the continuous variables x i . The reasoning we follow is
similar, but the constraints are different because the α ij have only two indices, and
hence they cannot capture betweenness directly in the way that the variables β ij k
do. Nevertheless, the constraints turn out to be simpler than those in Sect. 2.4.
First, we cannot simultaneously have i to the left of j and j to the left of i. Hence,
we impose the constraints
α ij + α ji = 1, 1 ≤ i < j ≤ n.