日々の流転

λ. ゴモリーの小数カットの導出メモ

Outline of an algorithm for integer solutions to linear programs でのゴモリーカット(Gomory's fractional cut)が、割と天下りに定義して、そのあと必要な性質を満たすことを証明しているけれど、これがちょっと気に入らなかったので、演繹的に導出してみた。(An algorithm for the mixed integer problem のゴモリーの混合整数カットの方ではないので注意)

準備

N を(0を含む)自然数の集合とし、(R, ≤_R), (Z, ≤_Z) をそれぞれ実数と整数の順序集合とする。 また、 I : (Z, ≤_Z) → (R, ≤_R) を順序集合間の通常の埋め込みとするが、たいてい省略する。

⌈-⌉, ⌊-⌋ : (R, ≤_R) → (Z, ≤_Z) をそれぞれ正の無限大方向への切り上げ(ceiling)と負の無限大方向への切り捨て(floor)とする。

随伴、モナド、コモナド、双対性

⌈-⌉ と ⌊-⌋ はそれぞれ I の左随伴と右随伴になっている。すなわち、以下が成り立つ。

• ∀a∈R, b∈Z. ⌈a⌉ ≤_Z b ⇔ a ≤_R I(b)
• ∀a∈Z, b∈R. I(a) ≤_R b ⇔ a ≤_Z ⌊b⌋

したがって、 I∘⌈-⌉, I∘⌊-⌋ : (R, ≤_R) → (R, ≤_R) はそれぞれ (R, ≤_R) 上のモナド、コモナドとなっており、以下が成り立つ。

• ⌊a⌋ ≤ a ≤ ⌈a⌉
• ⌊⌊a⌋⌋ = ⌊a⌋
• ⌈a⌉ = ⌈⌈a⌉⌉

また、 ⌈-⌉∘I, ⌊-⌋∘I : (Z, ≤_Z) → (Z, ≤_Z) はそれぞれ (Z, ≤_Z) 上のコモナド、モナドとなっており、こっちは更に強く、以下が成り立っている。

• ⌈I(a)⌉ = a for all a∈Z
• a = ⌊I(a)⌋ for all a∈Z

また、(-1)×- : (R, ≤_R) → (R,≥_R) によって、⌈-⌉と⌊-⌋は双対になっており、 ⌈a⌉ = - ⌊- a⌋ が成り立つ。

⌈-⌉ と ⌊-⌋ の分配性

a≤⌈a⌉ および b≤⌈b⌉ より a+b ≤_R ⌈a⌉+⌈b⌉ = I(⌈a⌉+⌈b⌉) で、随伴性より ⌈a+b⌉ ≤_Z ⌈a⌉+⌈b⌉ 。 双対性より ⌊a+b⌋ ≥_Z ⌊a⌋+⌊b⌋ 。

さらに、帰納法により ∀n∈N. ⌈n×a⌉ ≤_Z n×⌈a⌉ もいえる。 同じく、双対性より ∀n∈N. ⌊n×a⌋ ≥_Z n× ⌊a⌋

ゴモリーの小数カットの導出

x_i, y ∈ N が

• Σ_i a_i x_i + y = b …… (1)

を満たすとする。すると、

• Σ_i a_i x_i + y ≥ b … (2)
• Σ_i a_i x_i + y ≤ b … (3)

(3)の両辺に⌊-⌋を適用すると、⌊-⌋ の単調性より

• ⌊Σ_i a_i x_i + y⌋ ≤ ⌊b⌋ … (4)

⌊-⌋ の分配性と ⌊y⌋=y より

• ⌊Σ_i a_i x_i + y⌋ ≥ Σ_i ⌊a_i x_i⌋ + ⌊y⌋ ≥ Σ_i ⌊a_i⌋ x_i + ⌊y⌋ = Σ_i ⌊a_i⌋ x_i + y … (5)

(4), (5)に推移律を適用して

• Σ_i ⌊a_i⌋ x_i + y ≤ ⌊b⌋ … (6)

両辺に -1 をかけて

• Σ_i (- ⌊a_i⌋) x_i - y ≥ -⌊b⌋ … (7)

(2) と (7) の両辺を足し合わせて、

• Σ_i (a_i - ⌊a_i⌋) x_i ≥ b - ⌊b⌋

■