組合せ最適化問題

【くみあわせさいてきかもんだい (combinatorial optimization problem)】

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