積分多面体

幾何学と多面体組合せ論において、積分多面体とは、すべての頂点が整数の直交座標を持つ凸多面体である。^[1]つまり、整数点の凸包に等しい多面体である。^{[2]積分多面体は、}格子多面体またはZ多面体 とも呼ばれる。2次元および3次元の積分多面体の特殊なケースは、多面体ではなく、それぞれ多角形または多面体と呼ばれることがある。

例

次元の正則単体は、における整数多面体、つまり 1 つの座標が 1 で残りが 0 であるような整数点の凸包として表すことができます。^[^{出典が必要}^]積分単体のもう 1 つの重要なタイプであるオルソスキームは、座標が連続するいくつかの 1 で始まり、残りのすべての座標が 0 となる整数点の凸包として形成されます。の次元単位立方体には、座標が 0 または 1 であるすべての整数点が頂点として存在します。置換面体は、ベクトルにすべての可能な置換を適用することによって得られる座標を頂点として持つ。Lodayの凸実現における連想面体も整数多面体であり、置換面体の変形です。 $n$ $\mathbb {R} ^{n+1}$ $n$ $\mathbb {R} ^{n}$ $(1,2,...,n)$

最適化において

線形計画法や数学的最適化の関連問題では、凸多面体は、その点が従うべき線形不等式のシステムによって記述されることが多い。多面体が整数である場合、線形計画法を使用して、与えられた不等式のシステムに対する整数計画問題を解くことができる。これは、そうでなければより困難な問題である。

組合せ最適化問題から生じる多面体の中には、自動的に整数になるものがあります。たとえば、これは任意の半順序集合の順序多面体に当てはまります。これは、集合内の比較可能な要素に対応する座標間のペアワイズ不等式によって定義される多面体です。 ^[3]組合せ最適化におけるもう1つのよく知られた多面体は、マッチング多面体です。明らかに、アルゴリズム的にマッチングを見つけようとしており、1つの手法は線型計画法です。頂点ごとに取られる辺の合計を上限とする線型計画によって記述される多面体は、 2部グラフの場合は整数、つまり、マッチング多面体を正確に記述しますが、一般のグラフの場合は非整数です。^{[4]したがって、2部グラフの場合、有効な}マッチングを得るには、対応する線型計画法を解くだけで十分です。しかし、一般のグラフの場合、マッチング多面体の他の2つの特徴付けがあり、そのうちの1つは、頂点の奇数部分集合に対するブロッサム不等式を利用し、したがって、有効なマッチングを取得しながら整数計画を線形計画に緩和することを可能にする。^{[5]これらの特徴付けは、一般のグラフでそのようなマッチングを見つけるために使用される}エドモンズの有名なブロッサムアルゴリズムにおいてさらに興味深いものである。

計算の複雑さ

線型不等式で記述される多面体について、多面体が非整数である場合、座標が整数でない頂点を見つけることでその非整数性を証明できる。そのような頂点は、線型方程式系に変換されたときに一意の解を持つ不等式のサブセットを指定し、この解点が他のすべての不等式に従うことを検証することで、組み合わせ的に記述できる。したがって、整数性のテストは、否定的な答えが簡単に証明できる問題の複雑性クラス coNPに属する。より具体的には、 coNP完全である。^[6]

参照

参考文献

^ コルヌエジョル、ジェラール (2001)、「組み合わせ最適化: パッキングとカバーリング」、CBMS-NSF 応用数学地域会議シリーズ、第 74 巻、ペンシルベニア州フィラデルフィア: 工業応用数学協会 (SIAM)、p. 4、doi :10.1137/1.9780898717105、ISBN 0-89871-481-8、MR 1828452
^ 室田和夫 (2003)、離散凸解析、SIAM 離散数学および応用に関するモノグラフ、フィラデルフィア、ペンシルバニア州: 産業応用数学協会 (SIAM)、p. 90、doi :10.1137/1.9780898718508、hdl : 2433/149564、ISBN 0-89871-540-7、MR 1997998
^ スタンレー、リチャード P. (1986)、「2つのポセット多面体」、離散および計算幾何学、1 (1): 9–23、doi : 10.1007/BF02187680、MR 0824105
^ ロヴァシュ、ラースロー (1986)。マッチング理論。北オランダ。 269–274ページ。ISBN 978-0-444-87916-5. OCLC 316569965.
^ ロヴァシュ、ラースロー (1986)。マッチング理論。北オランダ。 274–281ページ。ISBN 978-0-444-87916-5. OCLC 316569965.
^ Ding, Guoli; Feng, Li; Zang, Wenan (2008)、「特定の積分特性を持つ線形システムを認識する複雑さ」、数学プログラミング、シリーズ A、114 (2): 321–334、doi :10.1007/s10107-007-0103-y、hdl : 10722/58972、MR 2393045
^ Barvinok, AI (1994)、「凸格子多面体の Ehrhart 多項式の計算」、Discrete & Computational Geometry、12 (1): 35–48、doi : 10.1007/BF02574364、MR 1280575

[c-1] コルヌエジョル、ジェラール (2001)、「組み合わせ最適化: パッキングとカバーリング」、CBMS-NSF 応用数学地域会議シリーズ、第 74 巻、ペンシルベニア州フィラデルフィア: 工業応用数学協会 (SIAM)、p. 4、doi :10.1137/1.9780898717105、ISBN 0-89871-481-8、MR 1828452

[m-2] 室田和夫 (2003)、離散凸解析、SIAM 離散数学および応用に関するモノグラフ、フィラデルフィア、ペンシルバニア州: 産業応用数学協会 (SIAM)、p. 90、doi :10.1137/1.9780898718508、hdl : 2433/149564、ISBN 0-89871-540-7、MR 1997998

[s-3] スタンレー、リチャード P. (1986)、「2つのポセット多面体」、離散および計算幾何学、1 (1): 9–23、doi : 10.1007/BF02187680、MR 0824105

[4] ロヴァシュ、ラースロー (1986)。マッチング理論。北オランダ。 269–274ページ。ISBN 978-0-444-87916-5. OCLC 316569965.

[5] ロヴァシュ、ラースロー (1986)。マッチング理論。北オランダ。 274–281ページ。ISBN 978-0-444-87916-5. OCLC 316569965.

[dfz-6] Ding, Guoli; Feng, Li; Zang, Wenan (2008)、「特定の積分特性を持つ線形システムを認識する複雑さ」、数学プログラミング、シリーズ A、114 (2): 321–334、doi :10.1007/s10107-007-0103-y、hdl : 10722/58972、MR 2393045

[b-7] Barvinok, AI (1994)、「凸格子多面体の Ehrhart 多項式の計算」、Discrete & Computational Geometry、12 (1): 35–48、doi : 10.1007/BF02574364、MR 1280575

積分多面体

例

最適化において

計算の複雑さ

関連オブジェクト

参照

参考文献

関連するトピック

キューブ

立方八面体

八面体

切頂八面体