Integer programming — 整数計画法

整数計画法（IP; 英語: integer programming）は、一部または全ての変数が整数値のみを取ることを要求される最適化問題を扱う、数理最適化の一分野である。

最もよく研究されている特殊なケースは整数線形計画法（ILP; 英語: integer linear programming）であり、目的関数と制約が線形である。変数が任意の実数値を取ることができる線形計画法とは異なり、整数性の要求により、整数計画法（IP）の問題は解くのが著しく困難になる。

整数計画法は、経済学、物流、生産計画など、変数が本質的に離散的である（例：生産される製品の単位数や従業員の数）多くの分野で広く応用されている。

定義と用語

一般的な整数線形計画問題は次のように記述できる：

$x$ ベクトルを見つける：

$c^{T}x$ を最大化（または最小化）する

制約条件：

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{\mathbb{Z}}}^n$（ベクトル $x$ の全ての要素が整数）

ここで $x$ は変数ベクトル、$c$ と $b$ はベクトル、$A$ は係数行列である。

変数に対する要求に応じて、以下の種類の問題が区別される：

• 純整数計画問題：全ての変数が整数でなければならない。
• 混合整数計画問題（英語: mixed-integer programming, MIP）：一部の変数のみが整数でなければならない。
• 0-1整数計画問題（ブール計画問題）：変数が0または1の値のみを取り、「はい/いいえ」のような論理的な決定をモデル化できる。

主な特性と計算複雑性

計算複雑性

一般的に、整数線形計画問題はNP困難である。これは、任意の整数計画問題に対して多項式時間で厳密な最適解を見つけることができる既知のアルゴリズムが存在しないことを意味する。この複雑さは問題の組み合わせ的な性質に起因しており、可能な整数解の数は変数の数が増えるにつれて指数関数的に増加する可能性があるためである。

線形計画法との関係（LP緩和）

任意の整数計画問題に対して、その線形計画緩和（LP緩和）を定式化することができる。これは、変数の整数性要件を撤廃した線形計画（LP）問題である。LP緩和の解は、2つの重要な特性を持つ：

1. 多項式時間で、はるかに高速に見つけることができる。
2. LP緩和の最適目的関数値は、元の整数問題の最適値に対する評価（最大化問題の場合は上限、最小化問題の場合は下限）を与える。

しかし、LP緩和の小数解を単純に最も近い整数に丸めるだけでは、通常、整数問題の最適解や実行可能解さえも得られない。

完全ユニモジュラ性

LP緩和と同じくらい容易に解ける、整数線形計画問題の重要なクラスが存在する。これらは、制約行列 $A$ が完全ユニモジュラ（すなわち、その任意の正方部分行列の行列式が0、+1、または-1に等しい）である問題である。$A$ が完全ユニモジュラ行列で、ベクトル $b$ が整数ベクトルであれば、LP緩和の実行可能領域をなす多面体の全ての頂点は自動的に整数座標を持つ。したがって、シンプレックス法によって見つけられた解は整数解となる。このような問題の例として、輸送問題や割当問題が挙げられる。

解法

完全ユニモジュラ性を持たない一般的な整数計画問題を解くために、陰的列挙の考えに基づいた厳密解法が開発されている。

• 分枝限定法（英語: Branch and Bound）：実行可能解の集合を部分集合に系統的に分割（分枝）し、最適解を含まないことが明らかな部分集合を切り捨てる（限定）ことに基づく、主要な厳密解法。部分集合の有望さを評価するためにLP緩和が用いられる。

• カット平面法（ゴモリーのカット法；英語: Cutting Plane Method）：問題に新しい線形制約（「カット」または「切除平面」）を逐次的に追加する反復的なアプローチ。これらのカットは、LP緩和の小数解を「切り取る」が、実行可能な整数解は一つも除外せず、LP緩和の実行可能領域を整数解の凸包に徐々に近づけていく。

現代のソルバーは、通常、両方のアプローチの利点を組み合わせた分枝カット法（英語: Branch and Cut）のようなハイブリッドアルゴリズムを使用する。

例と応用分野

整数計画法は、多くの古典的な組合せ最適化問題をモデル化することができる。

• ナップサック問題：総重量の制約を超えずに、合計価値が最大になるような品物の組み合わせを選択する、古典的な0-1整数計画問題。
• 巡回セールスマン問題：与えられた都市の集合を一度ずつ訪れて出発点に戻る最短経路を見つける問題。グラフの辺が最終的な経路に含まれるかどうかを表す変数を使い、整数計画問題として定式化できる。

その柔軟性から、整数計画法はオペレーションズ・リサーチにおいて最も需要の高いツールの一つであり、次のような分野で応用されている：

• 物流とサプライチェーン・マネジメント：輸送ルートの最適化、倉庫の配置、在庫管理。
• 生産計画：生産スケジュールの作成、リソースの割り当て、設備の負荷計画。
• 金融と経済：投資ポートフォリオの形成、設備投資の予算編成。
• 電気通信とエネルギー：通信ネットワークの設計、発電ユニットの運転計画。