整数計画問題

整数計画問題は、数理計画法における重要な問題の一つであり、線形計画問題の解に整数制約を加えたものです。具体的には、線形計画問題では解ベクトルxの各要素が実数値を取ることができますが、整数計画問題ではこれらの要素が整数値に限定されます。この制約によって、問題の難易度が大きく変化し、一般にNP困難な問題として知られています。

線形計画問題には、多項式時間で解を求めることができる効率的なアルゴリズムが存在しますが、整数計画問題に対しては、そのような効率的なアルゴリズムはまだ発見されていません。そのため、整数計画問題を解くためには、分枝限定法や切除平面法などの複雑なアルゴリズムが用いられることが一般的です。

特に、解ベクトルxの各要素を0または1の値のみに限定したものを、0-1整数計画問題と呼びます。この形式の問題は、様々な意思決定問題をモデル化する上で非常に強力なツールとなり、多くの実用的な問題に応用されています。

整数計画問題は、様々な分野で現れる組合せ最適化問題を扱う上で不可欠な手法であり、その応用範囲は非常に広いです。以下に、整数計画問題として解かれる問題の代表例をいくつか挙げます。

頂点被覆問題: 与えられたグラフにおいて、すべての辺が少なくとも一つの頂点によってカバーされるような最小の頂点集合を見つける問題。
ナップサック問題: 容量が限られたナップサックに、価値と重さが異なる品物を詰め込む際に、ナップサックの容量を超えない範囲で価値の合計を最大化する問題。
ハミルトン閉路問題: 与えられたグラフにおいて、全ての頂点を一度ずつ通る閉路を見つける問題。
巡回セールスマン問題: 与えられた都市を全て一度ずつ訪問し、出発点に戻る経路の中で総移動距離が最小となる経路を見つける問題。
集合被覆問題: 与えられた集合の要素をすべてカバーするような、部分集合の最小の組を見つける問題。
施設配置問題: 最適な施設配置を決定する問題。例えば、複数の顧客に対して、最も効率的な場所に倉庫や工場を配置する問題。
最大独立集合問題: 与えられたグラフにおいて、互いに隣接しない最大の頂点集合を見つける問題。
最小極大マッチング問題: 与えられたグラフにおいて、それ以上辺を追加できないマッチングのうち、最小のサイズのものを求める問題。
最大クリーク問題: 与えられたグラフにおいて、全ての頂点同士が隣接している最大の頂点集合を見つける問題。
支配集合問題: 与えられたグラフにおいて、すべての頂点が、その集合の頂点に隣接するか、集合に属するような、最小の頂点集合を見つける問題。
辺支配集合問題: 与えられたグラフにおいて、全ての辺が、その集合の辺に接続する頂点によって支配されるような、最小の辺集合を見つける問題。
ビンパッキング問題: 与えられたアイテムを、容量が限られたビンに詰める際に、必要なビンの数を最小化する問題。
一般化割当問題: 複数のタスクを、複数の資源に割り当てる際に、各資源の制約を満たしつつ、コストを最小化する問題。

これらの問題は、現実世界の様々な意思決定問題に現れ、その解決には整数計画法が不可欠です。整数計画問題は、その複雑さから、効率的な解法を見つけることが難しい場合がありますが、近年のコンピュータ技術の発展や、新しいアルゴリズムの研究によって、より大規模で複雑な問題も解決できるようになってきています。


参考になり得る図書

和書：
今野浩:「整数計画法」，産業図書，1981.
今野浩・鈴木久敏編：「整数計画と組合せ最適化」，日科技連，1982.
久保幹雄，田村明久，松井知己（編）：「応用数理計画ハンドブック」，朝倉書店，2002.

洋書：
(洋書については、提供された情報には記載されていませんでした。)

これらの書籍は、整数計画法の基礎から応用までを網羅しており、より深く学びたい読者にとって有益な情報源となるでしょう。

もう一度検索