3.2 Multi-Row Facility Layout
43
We say that a polyhedron is integer if all its extreme points have integer
coordinates. If we optimize a linear function over an integer polyhedron, then there
exists an optimal integer solution (unless the optimization is unbounded). TU is a
very useful property because of the following fact.
Proposition 3.1 If A is TU and b is a vector of integers, then the set of solutions of
the system Ax ≤ b is either empty or an integer polyhedron.
The more difficult part is deciding whether or not a given matrix is TU. To apply
the TU definition, it is necessary to compute the determinants of all the square
submatrices, and their number is exponential in the dimensions of the matrix. For
this reason, we are interested in criteria for TU that can be checked efficiently (i.e.,
in polynomial time). It is straightforward to deduce from Definition 3.1 that every
element of a TU matrix must be equal to 0, 1, or −1 and that if A is TU, then so is
its transpose A T . Another useful criterion is given by the following proposition.
Proposition 3.2 If a given matrix A has all its elements equal to 0, 1, or −1, if it
has no more than two nonzero elements in each column, and if for each column with
two nonzeros the sum of the elements of that column equals zero, then A is TU.
Note that Proposition 3.2 makes it easy to check that the first matrix of
Example 3.1 is TU. We can now state and prove the property that the optimal values
of the variables y i in (3.36)–(3.50) are always integer.
Theorem 3.1 For every instantiation of the variables α ij and β ij that satisfies
(3.47)–(3.50), the coefficient matrix of the constraints (3.39)–(3.46) is TU.
Proof Let A be the coefficient matrix of the constraints (3.39)–(3.46). Observe that
every element in A T is −1, 0, or 1, i.e., the coefficients of the variables y i are −1, 0,
or 1. Since every column of A T corresponds to the coefficients of y i , y j in each
constraint, it contains at most two nonzero elements. Where a column of A T has
two nonzero elements, these are of opposite sign. Therefore, by Proposition 3.2, A T
is TU. Thus, A is also TU.
Corollary 3.1 For every feasible instantiation of the variables α ij and β ij , if d is
integer, then the y-components of every extreme point of (3.39)–(3.46) are integer.
Proof For integer d, the right-hand side of the constraints (3.41)–(3.45) is integer.
The result follows by Theorem 3.1 and Proposition 3.1.
3.2.4 Alternative Optimization Approaches for the MRFLP
The MRFLP is indeed a challenging problem. As a consequence, beyond the MILO
approaches in Sects. 3.2.1 and 3.2.2 that directly model the entire problem, the
MRFLP has successfully been modelled using alternative approaches that consider
different aspects of the problem in turn.
43
We say that a polyhedron is integer if all its extreme points have integer
coordinates. If we optimize a linear function over an integer polyhedron, then there
exists an optimal integer solution (unless the optimization is unbounded). TU is a
very useful property because of the following fact.
Proposition 3.1 If A is TU and b is a vector of integers, then the set of solutions of
the system Ax ≤ b is either empty or an integer polyhedron.
The more difficult part is deciding whether or not a given matrix is TU. To apply
the TU definition, it is necessary to compute the determinants of all the square
submatrices, and their number is exponential in the dimensions of the matrix. For
this reason, we are interested in criteria for TU that can be checked efficiently (i.e.,
in polynomial time). It is straightforward to deduce from Definition 3.1 that every
element of a TU matrix must be equal to 0, 1, or −1 and that if A is TU, then so is
its transpose A T . Another useful criterion is given by the following proposition.
Proposition 3.2 If a given matrix A has all its elements equal to 0, 1, or −1, if it
has no more than two nonzero elements in each column, and if for each column with
two nonzeros the sum of the elements of that column equals zero, then A is TU.
Note that Proposition 3.2 makes it easy to check that the first matrix of
Example 3.1 is TU. We can now state and prove the property that the optimal values
of the variables y i in (3.36)–(3.50) are always integer.
Theorem 3.1 For every instantiation of the variables α ij and β ij that satisfies
(3.47)–(3.50), the coefficient matrix of the constraints (3.39)–(3.46) is TU.
Proof Let A be the coefficient matrix of the constraints (3.39)–(3.46). Observe that
every element in A T is −1, 0, or 1, i.e., the coefficients of the variables y i are −1, 0,
or 1. Since every column of A T corresponds to the coefficients of y i , y j in each
constraint, it contains at most two nonzero elements. Where a column of A T has
two nonzero elements, these are of opposite sign. Therefore, by Proposition 3.2, A T
is TU. Thus, A is also TU.
Corollary 3.1 For every feasible instantiation of the variables α ij and β ij , if d is
integer, then the y-components of every extreme point of (3.39)–(3.46) are integer.
Proof For integer d, the right-hand side of the constraints (3.41)–(3.45) is integer.
The result follows by Theorem 3.1 and Proposition 3.1.
3.2.4 Alternative Optimization Approaches for the MRFLP
The MRFLP is indeed a challenging problem. As a consequence, beyond the MILO
approaches in Sects. 3.2.1 and 3.2.2 that directly model the entire problem, the
MRFLP has successfully been modelled using alternative approaches that consider
different aspects of the problem in turn.