線形計画法双対問題に対するメッセージ伝搬法に基づく近似法

ウィキペディア小見出し辞書

線形計画法双対問題に対するメッセージ伝搬法に基づく近似法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/02 00:52 UTC 版)

「タンパク質設計」の記事における「線形計画法双対問題に対するメッセージ伝搬法に基づく近似法」の解説

ILPソルバーは、シンプレックス法やバリアベース法などの線形計画法（LP）アルゴリズムに依存して、各分岐でLP緩和を実行する。これらのLPアルゴリズムは、汎用の最適化手法として開発されたものであり、タンパク質設計問題（式（1））に最適化されたものではない。そのため、問題のサイズが大きくなると、LP緩和がILPソルバーのボトルネックになる。最近では、タンパク質設計問題のLP緩和の最適化のために、メッセージ伝搬アルゴリズム（message-passing）に基づくいくつかの代替案が設計された。これらのアルゴリズムは、整数計画の双対問題または主問題の両方を近似することができるが、最適性の保証を維持するためには、タンパク質設計問題の双対を近似するために使用するのが最も有効である。なぜなら、双対を近似することで、解を見逃さないことを保証するからである。メッセージ伝搬法に基づく近似法には、ツリー再重み付け最大積メッセージ伝搬アルゴリズム（tree reweighted max-product message passing）や、メッセージ伝搬線形計画アルゴリズム（message passing linear programming）などがある。