86
T. Okudono and A. King
Fig. 2. Gapping and boxing for x + 2y ≤ 5
Observe that the result requires b < m/2. In this circumstance L = 2b/m +
1 = 1 and number of logical connectives in box BV (c; b) is determined by the
cardinality of the set I d ((d − 1)(L + 1)) = I d (2(d − 1)), which is given below:
d 2(d − 1)
I d (2(d − 1)) |I d (2(d − 1))|
2
2
Π(1, 1)
1
3
4
Π(1, 1, 2)
3
4
6
Π(1, 1, 1, 3) ∪ Π(1, 1, 2, 2)
10
5
8 Π(1, 1, 1, 1, 4) ∪ Π(1, 1, 1, 2, 3) ∪ Π(1, 1, 2, 2, 2)
35
where Π(v) denote the set of permutations of the vector v. For d = 4, box BV (c; b)
thus requires 10(d − 1) = 30 binary conjunctions and 10 − 1 = 9 disjunctions.
3.2 Boxing and Gapping
Example 3. Consider
x + 2y ≤ 5
BV
and
x + 2y ≤ 5
LIA
for m = 8 as shown
in Figure 2(a). Observe
box BV (1, 2; 5) = (x ≤ 3 ∧ y ≤ 3) ∨ (x ≤ 7 ∧ y ≤ 1)
which is illustrated by the two grey rectangles. Hence 2, 3 /
∈
x + 2y ≤ 5
LIA
but 2, 3 ∈
x + 2y ≤ 5 ∧ box BV (1, 2; 5)
BV
therefore using boxing alone is not
sufficient to encode the LIA inequality x + 2y ≤ 5.
Example 4. Yet the LIA inequality x + 2y ≤ 5 can be decomposed as follows:
x + 2y ≤ 5
LIA
=
x + 2y ≤ 3
LIA
∪
4 ≤ x + 2y ≤ 5
LIA
=
x + 2y ≤ 3
LIA
∪
0 ≤ x + 2y − 4 ≤ 1
LIA
Figures 2(b, c) illustrates boxing for x + 2y ≤ 3 and 0 ≤ x + 2y − 4 ≤ 1 where:
x + 2y ≤ 3
LIA
=
x + 2y ≤ 3 ∧ box BV (1, 2; 3)
BV
=
x + 2y ≤ 3 ∧ (x ≤ 3 ∧ y ≤ 1)
BV
(a) x + 2y ≤ 5 with boxes (b) x + 2y ≤ 3 with box (c) 0 ≤ x + 2y − 4 ≤ 1 with boxes