トップ «前の日記(2013-04-02) 最新 次の日記(2013-04-09)» 月表示 編集

日々の流転


2013-04-04 [長年日記]

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

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⌋

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

xi, y ∈ N が

  • Σi ai xi + y = b …… (1)

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

  • Σi ai xi + y ≥ b … (2)
  • Σi ai xi + y ≤ b … (3)

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

  • ⌊Σi ai xi + y⌋ ≤ ⌊b⌋ … (4)

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

  • ⌊Σi ai xi + y⌋ ≥ Σi ⌊ai xi⌋ + ⌊y⌋ ≥ Σi ⌊ai⌋ xi + ⌊y⌋ = Σi ⌊ai⌋ xi + y … (5)

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

  • Σi ⌊ai⌋ xi + y ≤ ⌊b⌋ … (6)

両辺に -1 をかけて

  • Σi (- ⌊ai⌋) xi - y ≥ -⌊b⌋ … (7)

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

  • Σi (ai - ⌊ai⌋) xi ≥ b - ⌊b⌋