8
2 Layout on a Single Row
optimization and second-order cone optimization are also useful because they are
convex and can be solved efficiently using the available software (see Appendix A).
Let us look again at the formulation (2.3–2.5). If the coefficients c ij are nonnegative, then the objective function (2.3) is convex because the absolute value is
a convex function, and non-negative linear combinations of convex functions are
convex. However, the absolute value function is not differentiable everywhere, and
handling this type of objective requires specialized nondifferentiable optimization
algorithms that are not straightforward to apply.
Furthermore, the constraints (2.4) do not define a convex set. This is also because
of the presence of absolute values, and specifically because enforcing a positive
lower bound on an absolute value function results in a nonconvex set of solutions.
To see why this happens, consider the simple constraint |x − 1| ≥ 1. The set of
values of x satisfying this constraint is (−∞, 0] ∩ [2, ∞), which is not convex.
There are numerous applications of mathematical optimization in which it is
difficult or impossible to build a model with a convex objective function and/or
a convex feasible set. Various state-of-the-art optimization solvers can be used for
nonconvex problems, and some of these solvers could be applied to (2.3–2.5), but
they do not provide a guarantee of global optimality.
The best performance is achieved when the objective function and constraints are
linear, second-order cone or semidefinite expressions. We demonstrate this for the
SRFLP by expressing it using both a mixed-integer linear optimization (MILO) in
Sect. 2.3 and rank-constrained semidefinite optimization (SDO) in Sect. 2.7.
2.2 Single-Row Layout as a General Class of Problems
We have illustrated single-row layout using a manufacturing example, but the
SRFLP has a broad range of applications. Because the word “machine” is used for
a specific type of layout in manufacturing systems, we will use the generic word
department, as is done for facility layout in general, to refer to the rectangles to be
placed in an instance of the SRFLP. Similarly, the space in which the departments
are to be arranged is called the facility.
Formally, an instance of the SRFLP is defined by a set of n one-dimensional
departments {1, 2, . . . , n} with positive lengths { 1 , , 2 , . . . , , n } and non-negative
pairwise connectivities c ij . The objective is to find an arrangement of the facilities
next to each other in a line so as to minimize the total weighted sum of the centreto-centre distances between all pairs of facilities, where each distance is weighted
by the corresponding connectivity.
The problem can be compactly formulated as
min
π∈Π n
n−1
i=1
n
j =i+1
c ij d
π
ij ,
(2.6)
2 Layout on a Single Row
optimization and second-order cone optimization are also useful because they are
convex and can be solved efficiently using the available software (see Appendix A).
Let us look again at the formulation (2.3–2.5). If the coefficients c ij are nonnegative, then the objective function (2.3) is convex because the absolute value is
a convex function, and non-negative linear combinations of convex functions are
convex. However, the absolute value function is not differentiable everywhere, and
handling this type of objective requires specialized nondifferentiable optimization
algorithms that are not straightforward to apply.
Furthermore, the constraints (2.4) do not define a convex set. This is also because
of the presence of absolute values, and specifically because enforcing a positive
lower bound on an absolute value function results in a nonconvex set of solutions.
To see why this happens, consider the simple constraint |x − 1| ≥ 1. The set of
values of x satisfying this constraint is (−∞, 0] ∩ [2, ∞), which is not convex.
There are numerous applications of mathematical optimization in which it is
difficult or impossible to build a model with a convex objective function and/or
a convex feasible set. Various state-of-the-art optimization solvers can be used for
nonconvex problems, and some of these solvers could be applied to (2.3–2.5), but
they do not provide a guarantee of global optimality.
The best performance is achieved when the objective function and constraints are
linear, second-order cone or semidefinite expressions. We demonstrate this for the
SRFLP by expressing it using both a mixed-integer linear optimization (MILO) in
Sect. 2.3 and rank-constrained semidefinite optimization (SDO) in Sect. 2.7.
2.2 Single-Row Layout as a General Class of Problems
We have illustrated single-row layout using a manufacturing example, but the
SRFLP has a broad range of applications. Because the word “machine” is used for
a specific type of layout in manufacturing systems, we will use the generic word
department, as is done for facility layout in general, to refer to the rectangles to be
placed in an instance of the SRFLP. Similarly, the space in which the departments
are to be arranged is called the facility.
Formally, an instance of the SRFLP is defined by a set of n one-dimensional
departments {1, 2, . . . , n} with positive lengths { 1 , , 2 , . . . , , n } and non-negative
pairwise connectivities c ij . The objective is to find an arrangement of the facilities
next to each other in a line so as to minimize the total weighted sum of the centreto-centre distances between all pairs of facilities, where each distance is weighted
by the corresponding connectivity.
The problem can be compactly formulated as
min
π∈Π n
n−1
i=1
n
j =i+1
c ij d
π
ij ,
(2.6)