[De Loera+2023]離散最適化入門 3章 Graver基底 の要約

導入

代数的・幾何学的アプローチによる離散最適化入門 3章 Graver基底について，一通り読み終えたので，要約と参考になる資料について挙げたいと思います．

何が書かれているの？

• まず．離散版の勾配法で整数計画問題

$$
\mathrm{(IP)} \quad \min {f (x) | Ax = b, , \ell \leq x \leq u , , x \in \mathbb{Z}^d }
$$

を解く方法について書かれています．勾配の部分がGraver基底に対応しています．

アルゴリズム 1. (C.f. 代数的・幾何学的アプローチによる離散最適化入門 アルゴリズム3.1. 最良増加アルゴリズム)

1. INPUT $A$, $b$, $\ell$, $u$, 分離凸関数$f$, $(\mathrm{IP})$に対する実行可能解$x_0$
2. OUTPUT $(\mathrm{IP})$の最適解$x_{\min}$
3. WHILE $x_0 + \alpha t$が実行可能解で，$f(x_0 + \alpha t) < f(x_0)$となる$t \in \mathcal{G}$, $\alpha \in \mathbb{Z}_{>0}$がある DO
4. $\quad$ すべての組$t \in \mathcal{G} (A)$, $\alpha \in \mathbb{Z}_{>0}$から，$f(x_0 + \alpha t)$が最小となる組を選ぶ.
5. $\quad$ $x_0 \rightarrow x_0 + \alpha t$.
6. RETURN $x_0$

1. について，任意の$t \in \mathcal{G}(A)$に対して，$\alpha$に関して二分法を用いることによって，$O (|u - \ell |)$で計算できます(c.f. 代数的・幾何学的アプローチによる離散最適化入門 補題3.5.1.).

• アルゴリズム1.の計算時間を以下で評価することができることとその証明が書かれています，

定理 2. (C.f. 代数的・幾何学的アプローチによる離散最適化入門 定理3.4.1.)
行列$A$とそのGraver基底$\mathcal{G}(A)$, $\ell, u \in \mathbb{Z}^n, \ell \leq x \leq u$を満たすベクトル$x_0 \in \mathbb{Z}^d$, $f$は分離凸関数(例：線形関数)で，そして，$\ell \leq x \leq u$の範囲で$Ax = A x_0$を満たす全ての解$x$に対して$|f(x)| \leq M$を満たす$M$が与えられる整数計画問題$\mathrm{(IP)}$を$|\mathcal{G}(A)|, x_0, \ell, u , M$の多項式時間で解くアルゴリズムが存在する．

定理2. のアルゴリズムがアルゴリズム1に対応しています．

• 実行可能な初期値を見つける方法について書かれています．実質$|\mathcal{G}(A)|$の多項式時間で求めることができます．

定理 3. (C.f. 代数的・幾何学的アプローチによる離散最適化入門 系3.6.2.)
行列$A \in \mathbb{Z}^{nd}$とベクトル$\mathbb{n}$，$\ell, u \in \mathbb{Z}^n$とする．入力データと$|\mathcal{G}(A)|$の多項式時間で，$Ax=b , , \ell \leq x \leq u$の整数解を見つけるか，解が存在しないことを断定できる．

• Graver基底を算出する方法について書かれています．Graver基底を求めるアルゴリズムとして，Pottierの方法と射影持ち上げの方法が挙げられています．ちなみに，射影持ち上げのアプローチによるGraver基底を元揉めるアルゴリズムは，2013年時点で，理論面でも，実験面でも最速のアルゴリズムです．ちなみに，このアルゴリズムの計算量は，実質$|\mathcal{G}(A)|$の多項式時間です．

まとめると，$\mathrm{(IP)}$を$|\mathcal{G}(A)|, \ell, u , M$の多項式時間で解くことができます．

証明などの詳細を詰めたい方へ

• 下記の論文は，補題3.2.4(初期解と最適解の差がGraver基底線形和で書けること)の詳細を詰める際に読む必要があります．

• 下記の本は，補題3.3.1(演習 3.10.4)の証明が，下記の補題3.6に書いてあります．
  また，定理2.(定理3.4.1)の証明の行間を埋めたものが，下記の補題3.10に書いてあります．

おわりに

• Graver基底による離散版の勾配法で整数計画問題を解く話が書かれている，初めての日本語の文献になります．
• この節を読むだけでも，2012年までのGraver基底についての研究の知識が身につくと思います．