整数計画法

ウィキペディア

整数計画問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/01/16 08:00 UTC 版)

整数計画問題（せいすうけいかくもんだい）は、線型計画問題において、解ベクトルxの各要素を整数に限定した問題をいう。これはNP困難な問題に該当する。線型計画問題には多項式時間アルゴリズムが存在するのに対し、整数計画問題ではまだ見つかっていない。

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

整数計画法

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

「クラメルの公式」の記事における「整数計画法」の解説

クラメルの法則は、制約行列が完全単模 (totally unimodular) で、右辺値が整数、基本解も整数であるような整数計画問題を解くのにも利用できる。これにより整数問題を解くことが大幅に容易になる。