大規模問題の分解法

【だいきぼもんだいのぶんかいほう (decomposition method for large-scale problems)】

非常に多くの変数や制約条件をもつ最適化問題を, 一部の変数または制約条件だけから成る小さな部分問題の列に変換して解く方法. その多くは, 現実の大規模問題がしばしばもつブロック構造を利用している. 単に大規模問題が実際に解けるようになるだけでなく, もとの問題には見られなかった特徴的な構造が部分問題に現れて, 取り扱いが容易になる場合がある. 特に, 各部分問題が独立に解ける場合には, 並列アルゴリズムを構成する有力な手段となる.