組み合わせ最適化

組合せ最適化は数学的最適化のサブフィールドであり、有限のオブジェクト集合 から最適なオブジェクトを見つけることから成り、 ^[1]実行可能なソリューションの集合は離散的であるか、離散集合に縮小できます。典型的な組合せ最適化問題には、巡回セールスマン問題(「TSP」)、最小全域木問題(「MST」)、ナップザック問題などがあります。前述のような多くの問題では、網羅的な検索は扱いにくいため、代わりに、検索空間の大部分を迅速に除外する特殊なアルゴリズムや近似アルゴリズムに頼る必要があります。

組合せ最適化は、オペレーションズ・リサーチ、アルゴリズム理論、計算複雑性理論に関連しており、人工知能、機械学習、オークション理論、ソフトウェア工学、VLSI、応用数学、理論計算機科学など、さまざまな分野で重要な応用があります。

組み合わせ最適化の基本的な応用には、以下のものが含まれますが、これらに限定されません。

• 物流^[2]
• サプライチェーンの最適化^[3]
• スポークと目的地の最高の航空ネットワークを開発する
• 乗客を乗せるためにどのタクシーをルートするかを決める
• 荷物を配送する最適な方法を決定する
• 仕事を人々に最適に割り当てる
• 給水ネットワークの設計
• 地球科学の問題（例：貯留層流量）^[4]

離散最適化の特定の特殊なクラスに対する多項式時間アルゴリズムに関する文献は多数あります。そのかなりの部分は、線形計画法の理論によって統一されています。このフレームワークでカバーされる組み合わせ最適化問題の例としては、最短経路と最短経路木、フローと循環、全域木、マッチング、マトロイド問題などがあります。

NP 完全離散最適化問題に関する現在の研究文献には、次のトピックが含まれています。

• 多項式時間で正確に解ける問題の特殊なケース（例：固定パラメータの扱いやすい問題）
• 「ランダム」なインスタンスに対して優れたパフォーマンスを発揮するアルゴリズム（巡回セールスマン問題など）
• 多項式時間で実行され、最適解に近い解を見つける近似アルゴリズム
• FPT時間で実行され、最適解に近い解を見つけるパラメータ化された近似アルゴリズム
• 実際に発生し、必ずしもNP完全問題における最悪の動作を示さない現実世界のインスタンスを解く（例えば、数万のノードを持つ現実世界のTSPインスタンス^[5]）。

組合せ最適化問題は、いくつかの離散項目の集合から最良の要素を探す問題とみなすことができるため、原理的にはあらゆる種類の探索アルゴリズムやメタヒューリスティックを使用して解決することができます。広く適用可能なアプローチには、分岐限定法（ヒューリスティックとして使用するために任意の時点で停止できる正確なアルゴリズム）、分岐切断法（境界を生成するために線形最適化を使用する）、動的計画法（限られた探索ウィンドウでの再帰的なソリューション構築）、タブー探索（貪欲なタイプのスワッピングアルゴリズム）などがあります。ただし、一般的な探索アルゴリズムでは、最適なソリューションを最初に見つけられることは保証されておらず、また、迅速に（多項式時間で）実行されることも保証されていません。巡回セールスマン（決定）問題などの一部の離散最適化問題はNP 完全であるため、 ^[6] P=NPでない限りこれが予想されます。

各組み合わせ最適化問題には、特定の測度 に対して実行可能な解が存在するかどうかを問う、対応する決定問題があります。たとえば、頂点 と を含むグラフがある場合、最適化問題は「 からへの経路のうち、最も少ない辺を使用するものを見つける」となる可能性があります。この問題の答えは、たとえば 4 となる可能性があります。対応する決定問題は、「から への経路のうち、10 個以下の辺を使用するものはありますか?」となります。この問題は、単純に「はい」または「いいえ」で答えることができます。 ${\displaystyle m_{0}}$ ${\displaystyle G}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$

近似アルゴリズムの分野は、難しい問題に対する最適解に近い解を見つけるアルゴリズムを扱う。通常の決定バージョンは、許容可能な解のみを指定するため、問題の定義としては不十分である。適切な決定問題を導入することはできるが、その場合、問題は最適化問題としてより自然に特徴付けられる。^[7]

NP最適化問題（NPO）は、以下の追加条件を伴う組み合わせ最適化問題である。^[8]以下で参照される多項式は、それぞれの関数の入力のサイズの関数であり、入力インスタンスの暗黙的なセットのサイズではないことに注意してください。

• あらゆる実行可能な解のサイズは、与えられたインスタンスのサイズに対して多項式的に制限される。${\displaystyle y\in f(x)}$${\displaystyle x}$
• 言語と多項式時間で認識でき、${\displaystyle \{\,x\,\mid \,x\in I\,\}}$${\displaystyle \{\,(x,y)\,\mid \,y\in f(x)\,\}}$
• ${\displaystyle m}$多項式時間で計算可能です。

これは、対応する決定問題がNPにあることを意味します。コンピュータサイエンスでは、興味深い最適化問題は通常、上記の性質を持ち、したがって NPO 問題です。多項式時間で最適解を見つけるアルゴリズムが存在する場合、問題はさらに P 最適化 (PO) 問題と呼ばれます。多くの場合、NPO クラスを扱う場合、決定バージョンがNP 完全である最適化問題に関心があります。困難性関係は常に何らかの削減に関するものであることに注意してください。近似アルゴリズムと計算最適化問題の関係により、何らかの点で近似を保存する削減は、この主題では通常のチューリング削減とカープ削減よりも好まれます。そのような削減の例は、L 削減です。このため、NP 完全な決定バージョンを持つ最適化問題は、必ずしも NPO 完全とは呼ばれません。^[9]

NPOは近似可能性に応じて以下のサブクラスに分類されます: ^[8]

• NPO(I) : FPTASと等しい。ナップサック問題を含む。
• NPO(II) : PTASと等しい。メイクスパンスケジューリング問題が含まれます。
• NPO(III) : 多項式時間アルゴリズムを持つNPO問題のクラスで、コストが最大で最適コストのc倍(最小化問題の場合)、またはコストが少なくとも最適コスト(最大化問題の場合)のソリューションを計算します。Hromkovičの本[which?]では、 P ^{= NPの場合を除いて、すべてのNPO(II)問題はこのクラスから除外されています。除外がなければ、APXに等しいです。MAX} -SATとメトリックTSPが含まれます。${\displaystyle 1/c}$
• NPO(IV) : 入力のサイズの対数の多項式である比率で最適解を近似する多項式時間アルゴリズムを持つ NPO 問題のクラス。Hromkovič の本では、P=NP でない限り、すべての NPO(III) 問題はこのクラスから除外されます。集合被覆問題が含まれます。
• NPO(V) : 最適解をn上の何らかの関数で制限された比率で近似する多項式時間アルゴリズムを持つNPO問題のクラス。Hromkovicの本では、P = NPでない限り、すべてのNPO(IV)問題はこのクラスから除外されます。TSPとクリーク問題が含まれます。

NPO 問題は、すべてのインスタンスおよびすべてのソリューション に対して、測度がのサイズの多項式関数によって制限される場合、多項式制限(PB) と呼ばれます。クラス NPOPB は、多項式制限のある NPO 問題のクラスです。 ${\displaystyle x}$${\displaystyle y\in f(x)}$${\displaystyle m(x,y)}$${\displaystyle x}$

• 割り当て問題
• ビンパッキング問題
• 閉鎖問題
• 制約充足問題
• 在庫問題を切り詰める
• 支配集合問題
• 整数計画法
• ジョブショップスケジューリング
• ナップザック問題
• メトリック k 中心/ 頂点 k 中心問題
• 線形システムにおける最小関連変数
• 最小全域木
• 看護師のスケジュール問題
• リングスター問題
• セットカバーの問題
• タレントのスケジュール
• 巡回セールスマン問題
• 車両再スケジュールの問題
• 車両経路問題
• 兵器のターゲット割り当て問題

• 制約複合グラフ

• Beasley, JE「整数計画法」（講義ノート）。

• Cook, William J. ; Cunningham, William H.; Pulleyblank, William R. ; Schrijver, Alexander (1997).組み合わせ最適化. Wiley. ISBN 0-471-55894-X。

• クック、ウィリアム (2016)。「最適な TSP ツアー」。ウォータールー大学。 (これまでに解決された最大の TSP インスタンスに関する情報。)

• クレッシェンツィ、ピエルルイジ。カン、ヴィゴ。ハルドルソン、マグナス。Karpinski, マレク;ウーギンガー、ゲルハルト編（編）。 「NP 最適化問題の概要」。 (これは、NP 最適化問題の近似結果の継続的に更新されるカタログです。)

• Das, Arnab; Chakrabarti, Bikas K編 (2005)。量子アニーリングと関連する最適化手法。物理学講義ノート。第 679 巻。Springer。Bibcode : 2005qnro.book..... D。ISBN 978-3-540-27987-7。

• Das, Arnab; Chakrabarti, Bikas K (2008). 「コロキウム: 量子アニーリングとアナログ量子計算」Rev. Mod. Phys . 80 (3): 1061. arXiv : 0801.2193 . Bibcode :2008RvMP...80.1061D. CiteSeerX  10.1.1.563.9990 . doi :10.1103/RevModPhys.80.1061. S2CID  14255125.

• Lawler, Eugene (2001)。組み合わせ最適化: ネットワークとマトロイド。ドーバー。ISBN 0-486-41453-1。

• リー、ジョン（2004）。組み合わせ最適化入門。ケンブリッジ大学出版局。ISBN 0-521-01012-8。

• Papadimitriou, Christos H.; Steiglitz, Kenneth (1998 年 7 月)。組み合わせ最適化: アルゴリズムと複雑性。ドーバー。ISBN 0-486-40258-4。

• Schrijver, Alexander (2003)。組み合わせ最適化: 多面体と効率。アルゴリズムと組み合わせ論。第 24 巻。Springer。ISBN 9783540443896。

• Schrijver, Alexander (2005)。「組み合わせ最適化の歴史について (1960 年まで)」(PDF)。Aardal , K.、Nemhauser, GL、Weismantel, R. (編)。離散最適化ハンドブック。Elsevier。pp. 1–68。

• シュライヴァー、アレクサンダー（2006 年 2 月 1 日）。組み合わせ最適化コース(PDF)。

• Sierksma, Gerard; Ghosh, Diptesh (2010)。ネットワークの実践; ネットワーク最適化のテキストとコンピュータ演習。Springer。ISBN 978-1-4419-5512-8。

• ジェラルド・シールクスマ。ヨリ・ズウォルス (2015)。線形最適化と整数最適化: 理論と実践。 CRCプレス。ISBN 978-1-498-71016-9。

• Pintea, CM. (2014). 組み合わせ最適化問題のためのバイオインスパイアードコンピューティングの進歩。インテリジェントシステムリファレンスライブラリ。Springer。ISBN 978-3-642-40178-7。

ウィキメディア・コモンズには、組み合わせ最適化に関連するメディアがあります。

• 組み合わせ最適化ジャーナル
• オーソワ組み合わせ最適化ワークショップ
• Java 組み合わせ最適化プラットフォーム (オープンソース コード)
• なぜ人々のスケジュールを組むのは難しいのでしょうか?
• 最適化問題の複雑性クラス / Stefan Kugele ^{[リンク切れ‍ ]}