2.4 Betweenness-Based Binary Linear Optimization Formulation
15
β ij d − β jkd + β ikd ≥ 0, 1 ≤ i < j < k ≤ n, d = i, j, k,
(2.29)
− β ij d + β jkd + β ikd ≥ 0, 1 ≤ i < j < k ≤ n, d = i, j, k,
(2.30)
β ij d + β jkd + β ikd ≤ 2, 1 ≤ i < j < k ≤ n, d = i, j, k
(2.31)
β ij k ∈ {0, 1}, 1 ≤ i < j ≤ n, k = i, j.
(2.32)
Note that this is a pure binary linear optimization problem.
Most algorithms for binary and integer optimization problems rely on the
continuous relaxation, which is the optimization problem obtained when all the
integer variables are allowed to vary continuously between their bounds (smallest
and largest permitted values). The algorithms use the continuous relaxation to
obtain global bounds on the optimal solution, terminating when the best bound
matches the objective value of the best solution found so far. If the bounds on
the variables can be made tighter, then the continuous relaxation will be tighter
as well. More generally, if the feasible set of the continuous relaxation is made
smaller (while still containing all the feasible integer solutions), then this usually
results in better global bounds, and hence in lower computational times. It turns out
that when the binary formulation above is relaxed to a linear optimization problem
by allowing the binary variables to be continuous in the interval 0 ≤ β ij k ≤ 1, the
resulting relaxation is weak. A general approach to tighten the continuous relaxation
of a given formulation is to add the so-called valid inequalities to the integer
optimization problem. The continuous relaxation of the betweenness formulation
can be tightened using the class of valid inequalities given below.
Proposition 2.1 Let f ≤ n be a positive even integer and let S ⊆ {1, . . . , n} be
such that |S| = f . For each r ∈ S, and for any partition (S 1 , S 2 ) of S\{r} such that
|S 1 | =
1
2 f , the inequality
t
β tqr +
t
β tqr −
t ∈S 1
q∈S 2
β min{t,q},max{t,q},r ≤ 0
(2.33)
is valid for the betweenness formulation of the SRFLP.
Proof Let h 1 and h 2 be the number of departments to the left of r in S 1 and S 2 ,
respectively. This means that there are |S 1 | − h 1 departments in S 1 to the right of r,
and similarly |S 2 | − h 2 departments to the right of r in S 1 . Let (β ij k ) 1≤i
be equal to one when:
• t is equal to one of the h 1 departments to the left of r in S 1 , and q is equal to one
of the |S 1 | − h 1 other departments in S 1 , or
• t is equal to one of the h 2 departments to the left of r in S 2 , and q is equal to one
of the |S 2 | − h 1 other departments in S 2 .
15
β ij d − β jkd + β ikd ≥ 0, 1 ≤ i < j < k ≤ n, d = i, j, k,
(2.29)
− β ij d + β jkd + β ikd ≥ 0, 1 ≤ i < j < k ≤ n, d = i, j, k,
(2.30)
β ij d + β jkd + β ikd ≤ 2, 1 ≤ i < j < k ≤ n, d = i, j, k
(2.31)
β ij k ∈ {0, 1}, 1 ≤ i < j ≤ n, k = i, j.
(2.32)
Note that this is a pure binary linear optimization problem.
Most algorithms for binary and integer optimization problems rely on the
continuous relaxation, which is the optimization problem obtained when all the
integer variables are allowed to vary continuously between their bounds (smallest
and largest permitted values). The algorithms use the continuous relaxation to
obtain global bounds on the optimal solution, terminating when the best bound
matches the objective value of the best solution found so far. If the bounds on
the variables can be made tighter, then the continuous relaxation will be tighter
as well. More generally, if the feasible set of the continuous relaxation is made
smaller (while still containing all the feasible integer solutions), then this usually
results in better global bounds, and hence in lower computational times. It turns out
that when the binary formulation above is relaxed to a linear optimization problem
by allowing the binary variables to be continuous in the interval 0 ≤ β ij k ≤ 1, the
resulting relaxation is weak. A general approach to tighten the continuous relaxation
of a given formulation is to add the so-called valid inequalities to the integer
optimization problem. The continuous relaxation of the betweenness formulation
can be tightened using the class of valid inequalities given below.
Proposition 2.1 Let f ≤ n be a positive even integer and let S ⊆ {1, . . . , n} be
such that |S| = f . For each r ∈ S, and for any partition (S 1 , S 2 ) of S\{r} such that
|S 1 | =
1
2 f , the inequality
t
β tqr +
t
β tqr −
t ∈S 1
q∈S 2
β min{t,q},max{t,q},r ≤ 0
(2.33)
is valid for the betweenness formulation of the SRFLP.
Proof Let h 1 and h 2 be the number of departments to the left of r in S 1 and S 2 ,
respectively. This means that there are |S 1 | − h 1 departments in S 1 to the right of r,
and similarly |S 2 | − h 2 departments to the right of r in S 1 . Let (β ij k ) 1≤i
be equal to one when:
• t is equal to one of the h 1 departments to the left of r in S 1 , and q is equal to one
of the |S 1 | − h 1 other departments in S 1 , or
• t is equal to one of the h 2 departments to the left of r in S 2 , and q is equal to one
of the |S 2 | − h 1 other departments in S 2 .