組合せ最適化問題とは?

Weblio 辞書 > 学問 > OR事典 > 組合せ最適化問題の意味・解説 

組合せ最適化問題

読み方くみあわせさいてきかもんだい
【英】:combinatorial optimization problem

概要

離散最適化問題のうち, 解集合の定義が組合せ条件よるものをいう. 多く組合せ条件は, 変数整数性を含む形式表現できるため, 整数計画問題とほぼ同義的に用いられることも多い. 一般に問題サイズ大きくなるにつれ, 対象とすべき解の数が爆発的増加するため, 有効な時間最適解を得るのが困難な問題多く含まれている. そのため, 近似的な解を有効な時間精度求め研究も盛んである.

詳説

 ある計画遂行するとき, 様々な条件を満足させながら, 最適順序決めたり, 複数選択肢からいくつかを選んだり, 仕事機械とを割り当て (一般化割当問題) たり, 施設配置場所を決め (施設配置問題) たりする問題は現実中でもよく当面する. これらの問題, あるいは論理代数学にみられる充足可能性問題 (satisfability problem) などのように, 解集合順列, 組合せなどで表される離散最適化問題 (discrete optimization problem) を総称して組合せ最適化問題 (combinatorial optimization problem) という.

 ほとんどの組合せ最適化問題は, 変数整数性を含む形式数学的表現できるため, 整数計画問題と明確な区別できない. 慣例的には, 巡回セールスマン問題 (traveling salesman problem), ナップサック問題 (knapsack problem), 集合被覆問題 (set covering problem)などのように,問題や解の構造何等かの特徴のある離散最適化問題を, より一般的な整数計画問題区別して, 組合せ最適化問題と呼ぶこともある.

 組合せ最適化問題の難しさは, 一般に問題サイズ大きくなるにつれ, 解集合構成する要素の数が組合せ的に増加 (組合せ的爆発) することにある. したがって, たとえ有限ではあっても, すべての解を列挙して最適な解を得ることは事実上不可能となる. また, それらの多くNP困難クラス属するため,単純なアルゴリズム貪欲的な解法だけでは, 最悪場合,最適とはかけ離れた (問題サイズ増大に従って急速に悪くなるような) 解が得られることさえもある.

 組合せ最適化問題を厳密に解くアプローチとしては,それらが (0-1) 整数計画問題定式化できることから, そこで研究・開発されている解法ほとんど全てが, 組合せ最適化問題にも適用可能であるため, 一般的な整数計画問題を解くパッケージなどを利用するのも一法ではある. しかしながら, 組合せ最適化問題は,制約式の表現形式そのもの組合せ的に増大してしまうこともあるため, 単にソフトウェア任せでは, 問題入力時点ですでに行き詰まってしまうことも少なくない.

 例えn\, 都市巡回セールスマン問題場合, V\, グラフの点集合とし, c_{ij}\, (i,j)\, 重み,x_{ij}\, (i,j)\, が解に含まれるとき1, そうでないとき0の値をとる0-1変数とするとき, 次のように定式化することができる.


\begin{array}{rll}
\mbox{min.} & \sum_{i \in V} \sum_{j \in V}c_{ij} x_{ij}& \\
\mbox{s. t.} & \sum_{j=1}^n x_{ij} = 1 & (\forall i \in V), \\
& \sum_{i=1}^n x_{ij} = 1 & (\forall j \in V), \\
& \sum_{i \in S} \sum_{j \in V \setminus S} x_{ij} \geq 1 
 & (\forall S \subset V, S \neq \emptyset),\\
& x_{ij} \in \{ 0, 1 \}& (\forall i, j \in V).
\end{array}\,


この定式化では, 変数の数はn^2\, であり, 制約式の1, 2番目は各n\, 本で割当問題と同じ形をしているが, 部分巡回除去制約呼ばれている第3番目の制約は, 式の数が組合せ的に増大するため, 一般的な整数計画問題パッケージを使うことは難しい. もちろん, 1つ問題対す定式化方法一意ではなく, 巡回セールスマン問題2次割当問題 (quadratic assignment problem) や 3部グラフにおける割当問題帰着して定式化すれば, パッケージ利用は可能になるが, それによって解きやすくなることは期待できない.

 定式化における規模増大克服する試みもなされている. たとえば, 板取り問題 (cutting-stock problem) は, 変数の数が非常に多くなる形で定式化できるが, 列生成法によって必要な変数 (取り出しパターン) を生成しながら解くことで成功をおさめている. また, 巡回セールスマン問題のように制約式が非常に多くなる問題については, 必要な制約随時加え, 解領域次第に狭くしていきながら解く 切除平面法 (cutting plane method) が適用できる.

 切除平面法は, 組合せ最適化問題を研究する上で, 歴史的にも理論的にも重要な位置占めている. この方法の基本的考え方は, まず問題整数条件連続緩和した問題考える. このとき, さらに制約式の一部除去してもよい. 例えば, 巡回セールスマン問題場合, 第3番目の制約式を除いて緩和した問題は割当問題等価になる. この緩和問題を解くと, 一般に問題にとっては実行不可能な解が得られる. ここで, その解は切除するが, 元問題実行可能解切除ないよう制約生成し, それらを逐次加えていきながら, 連続緩和問題を解き続ける. その結果, 最初に出た実行可能解最適解となる.

 切除平面法正当性理論的裏付けられているが, 単独利用だけでは収束性計算機精度などにおいて難があり, 1970-80年代にはより実用的分枝限定法軍配があがっていた. しかし近年では分枝限定法中に切除平面法組み込む手法 (分枝切除法) が様々な問題成功をおさめ, 再び注目を浴びつつある.

 分枝限定法 (branch-and-bound method) は, 分割統治法一種であり, そのまま問題では規模大きすぎて解きにくいものを, 変数などを固定することにより解領域解ける程度にまで小さな問題 (子問題) に分割し, 各子問題, あるいはその緩和問題を解いて得られる情報まとめて, 元の問題最適解を得ようという考え基づいている.

 分枝限定法基本的枠組みは以下のように記述できる. ただし, ここでは最小化問題について説明しており, 上界値というのは, 最適値以上であることが分かっている値で, 通常近似解法などで得られる値をさす. また, 下界値というのは, 最適値以下であることが分かっている値で, 緩和問題などを解いて得られる値のことをいう. 最大化問題場合は, 上界値・下界値の意味が逆転することに注意されたい. 以下では, 未探査の子問題集合{\mathcal N}\, とする.


\mathbf{step1}\, \boldsymbol{x}:=\, 初期実行可能解, z:=\, 初期上界値, {\mathcal N}:=\{ P_0 \}\, (元問題).
\mathbf{step2}\, {\mathcal N}=\emptyset\, ならば現在の\boldsymbol{x}\, 最適解終了. そうでなければ, {\mathcal N}\, から適当な問題P'\, 選び{\mathcal N} := {\mathcal N} \setminus \{P'\}\, とする.
\mathbf{step3}\, P'\, 緩和問題を解き, その最適解\bar{\boldsymbol{x}}'\, , 最適値を\bar{z'}\, (この値はP'\, 下界値となる) とする. 緩和問題実行不可であればstep2へ戻る.
\mathbf{step4}\, \bar{\boldsymbol{x}}'\, が元問題実行可能解ならばstep2へ戻る. その際, z > \bar z'\, ならよりよい上界値が得られたので, \boldsymbol{x} := \bar{\boldsymbol{x}}'\, , z := \bar z'\, として更新する.
\mathbf{step5}\, \bar z' \geq z\, ならば子問題P'\, 最適解求めたとしても, \boldsymbol{x}\, 上のよい解が得られないので, step2へ戻る.
\mathbf{step6}\, P'\, 実行可能領域分割した子問題生成し, それらを{\mathcal N}\, 加え, step2 へ戻る.


 分枝限定法基本的に列挙法であり, 最悪場合考えれば全ての解を列挙してしまうこともあり得るが, 多く場合極めて効果的働き, 無駄な列挙削除することで, かなり大規模問題であっても最適解を得ることに成功している.

 無駄な列挙削除できる場合というのは, 緩和問題実行不可能のとき(step3), 緩和問題の解が実行可能のとき(step4), 緩和問題最適値が上界値と等しいか悪い (大きい) とき (step5) であるが,その中でも特にstep5の果たす役割は非常に大きい. これをうまく働かせるためには, より大きな下界値を得ることと, 近似解法などを用いてよりよい上界値を得ること (step1) が必要不可欠である. その他にも, 探索する子問題選択 (step2) や子問題分割法 (step6) も重要な役割を果たす.

 以下では, 下界値を改善する代表的方法としてラグランジュ緩和法 (Lagrangian relaxation method) と切除平面法について説明する.

 ラグランジュ緩和は, 問題緩和のため, 除去した制約ラグランジュ乗数というスカラー掛けて目的関数加えて作成する. ラグランジュ緩和作り方は, どの制約目的関数組込むかでいく通り考えられるが, 一般的に残った制約式が解きやすい問題となるものを選ぶ. 例え巡回セールスマン問題場合には, 第3番目の制約ラグランジュ緩和すると, 次の割当問題となり, この最適値は巡回セールスマン問題下界値を与える. ただし, \boldsymbol{\mu}\, ラグランジュ乗数ベクトル, 各要素\mu_S \geq 0 (S \subset V, S \neq \emptyset)\, である. 等式制約ラグランジュ緩和するときには, ラグランジュ乗数符号制約付かない.


\mbox{min.} \quad L(\boldsymbol{\mu}) = \sum_{(i,j) \in E} c_{ij} x_{ij} + \sum_S 
\mu_S \cdot (1-\sum_{i \in S}\sum_{j \in V \setminus S} x_{ij})\,


このとき, できるだけ大きな下界値を得るような\boldsymbol{\mu}\, 定めることが大切であり, それをラグランジュ最適化問題 (ラグランジュ双対問題) という. つまり, L (\boldsymbol{\mu})\, 最適値をL^*(\boldsymbol{\mu})\, とするとき,


L = \max_{\boldsymbol{\mu} \geq 0} \{L^*(\boldsymbol{\mu}) \}\,


表現される問題である. この問題を解くために, 微分不可能な区分線形関数における非線型最適化手法のひとつである 劣勾配法 (subgradient method) と呼ばれる逐次反復法が用いられることが多い. 劣勾配法による反復は, かなり少な回数打ち切っても, 十分良い下界値が求まることが様々な問題において報告されている.

 効果的下界値を算出するもう1つ方法として, 切除平面法分枝限定法組込む分枝切除法 (branch-and-cut method)が, 大規模な組合せ最適化問題を効果的に解く方法として注目を浴びつつある. これは, 切除平面法が解領域徐々に狭くしていくことから, よりよい緩和問題を解いていると捉えるのである. 特に元の問題にとっての実行不可能な解をできるだけ大きく切り落とすような, (極大面) カットよばれる不等式様々な生成法が研究されている.

 組合せ最適化問題の厳密解法において, 分枝限定法は布の縦糸のようなもので, それに横糸であるラグランジュ緩和法, 劣勾配法, 切除平面法,近似解法などを絡めることにより, 優れた解法開発されている. 分枝限定法は, 非凸領域をもつ数理計画問題や, 大域最適化問題などの解法としても注目を浴びつつある.

 組合せ最適化問題に関する文献は, 理論的なもの, 実験的なもの, 実例的なもの, 近似解法など様々な視点から, それぞれ膨大な数の優れた論文著書がある. 近年, ハンドブック的な書籍 [2, 3] 等が出ており,邦訳されたもの [4, 5] もある. 特に [1] は, 文献書評集であり, 適切な文献探すのに有用である.



参考文献

[1] M. Dell'Amico, F. Maffioli and S. Martello, eds., Annotated Bibliographies in Combinatorial Optimization, John Wiley & Sons, 1997.

[2] D.-Z. Du and P.M. Pardalos, eds.,Handbook of Combinatorial Optimization, 3 vols., Kluwer, 1998.

[3] R.L. Graham, M. Grötschel and L. Lovász, eds.,Handbook of Combinatorics, 2 vols., North-Holland, 1995.

[4] B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, Springer, 2002. 浅野孝夫, 平田富夫, 小野孝男, 浅野泰仁訳, 『組み合わせ最適化 - 理論アルゴリズム』, シュプリンガー・フェアラーク, 2005.

[5] G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J.Todd, eds.,Optimization, North-Holland, 1989. 伊理正夫, 今野浩, 刀根薫監訳, 『最適化ハンドブック』, 朝倉書店, 1995.


組合せ最適化

(組合せ最適化問題 から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/03/04 23:10 UTC 版)

組合せ最適化(くみあわせさいてきか、: combinatorial optimization組み合わせ最適化、または組み合せ最適化とも表記される)は、応用数学情報工学での組合せ論最適化問題である。オペレーションズリサーチアルゴリズム理論、計算複雑性理論と関連していて、人工知能数学、およびソフトウェア工学などの交差する位置にある。組合せ最適化では、厳密解が簡単に求まる場合もあれば、そうでない場合もある。厳密解を求めるのが難しいと思われる問題を解くために、その問題の解空間を探索する場合もあり、そのためのアルゴリズムでは、効率的に探索するために解空間を狭めたりすることもある。






「組合せ最適化」の続きの解説一覧


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

「組合せ最適化問題」の関連用語

組合せ最適化問題のお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング



組合せ最適化問題のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2018 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの組合せ最適化 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2018 Weblio RSS