整数線形計画法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/02 00:52 UTC 版)
詳細は「線型計画法#線型計画法」および「整数計画問題」を参照 ET を最適化する問題（式（1））は、整数線形計画（integer linear program、ILP）として簡単に定式化できる。最も強力な定式化の一つは、最終解における回転異性体とエッジの存在を表すために二値変数を使用し、各残基に対して回転異性体を正確に1つ、各残基のペアに対して1つのペアワイズ相互作用を持つように解を制約するものである。 min ∑ i ∑ r i E i ( r i ) q i ( r i ) + ∑ j ≠ i ∑ r j E i j ( r i , r j ) q i j ( r i , r j ) {\displaystyle \ \min \sum _{i}\sum _{r_{i}}E_{i}(r_{i})q_{i}(r_{i})+\sum _{j\neq i}\sum _{r_{j}}E_{ij}(r_{i},r_{j})q_{ij}(r_{i},r_{j})\,} ここに次を仮定する。 ∑ r i q i ( r i ) = 1 , ∀ i {\displaystyle \sum _{r_{i}}q_{i}(r_{i})=1,\ \forall i} ∑ r j q i j ( r i , r j ) = q i ( r i ) , ∀ i , r i , j {\displaystyle \sum _{r_{j}}q_{ij}(r_{i},r_{j})=q_{i}(r_{i}),\forall i,r_{i},j} q i , q i j ∈ { 0 , 1 } {\displaystyle q_{i},q_{ij}\in \{0,1\}} CPLEX（英語版）に代表されるILPソルバーは、タンパク質設計問題の大規模な事例に対して、正確な最適解を計算することができる。これらのソルバーは、問題の線形計画緩和（英語版）（linear programming relaxation）を使用し、qi と qij が連続した値をとることができ、ブランチ・アンド・カット（英語版）アルゴリズム（branch and cut）を組み合わせて、最適な解を求めて立体配座空間のごく一部を探索するものである。ILPソルバーは、側鎖配置問題の多くの事例を解決することが示されている。
※この「整数線形計画法」の解説は、「タンパク質設計」の解説の一部です。
「整数線形計画法」を含む「タンパク質設計」の記事については、「タンパク質設計」の概要を参照ください。
- 整数線形計画法のページへのリンク
