整数計画問題

ウィキペディア

整数計画問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/07/26 23:17 UTC 版)

整数計画問題（せいすうけいかくもんだい）は、線型計画問題において、解ベクトル $x$

IPとLP緩和後の多面体

右の図に対する整数計画問題は以下の通りである:

${\begin{aligned}{\underset {x,y\in \mathbb {Z} }{\text{maximize}}}\quad &y\\{\text{subject to}}\quad &-x+y\leq 1\\&3x+2y\leq 12\\&2x+3y\leq 12\\&x,y\geq 0\end{aligned}}$

最適化問題では極大・極小値をとる解を求める。

非線形（制約付き）

凸最適化

組合せ最適化

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略・遺伝的アルゴリズム）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• 群知能（ACO・PSO）
• ベイスンホッピング法
• 量子焼きなまし法

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア （一覧）