整数計画法とは？離散的な意思決定を最適化する数理手法
整数計画法は、決定変数が整数値を取る制約のもとで目的関数を最適化する数理手法です。分枝限定法の仕組み、実践手順、活用場面と注意点を解説します。
整数計画法とは
整数計画法（Integer Programming、IP）とは、決定変数の一部または全部が整数値を取るという制約のもとで、目的関数を最大化または最小化する数理最適化手法です。「工場を建てるか建てないか」「トラック何台を配置するか」など、小数では意味をなさない離散的な意思決定を数学的に最適化できます。
整数計画法の理論的基礎は、1958年にラルフ・ゴモリーが切除平面法（Cutting Plane Method）を開発したことに始まります。その後、1960年代にA.H.ランドとA.G.ドイグが分枝限定法（Branch and Bound）を提唱し、実用的な解法が確立されました。現在ではCPLEX、Gurobi、SCIPなどの高性能ソルバーにより、大規模な問題も実務レベルで解けるようになっています。
整数計画法の価値は、「やるかやらないか」「何個にするか」という現実のビジネス判断を数学的に最適化できる点です。線形計画法が連続量の最適化であるのに対し、整数計画法は離散的な意思決定に対応し、より現実に即した最適解を求められます。
コンサルティングでは、施設配置の最適化、設備投資の組み合わせ決定、スケジューリング、車両配送ルートの最適化、人員配置のシフト最適化などで活用されます。
構成要素
整数計画法は以下の要素で構成されます。0-1変数（バイナリ変数）を使うことで、論理的な条件も数式に組み込めます。
| 要素 | 説明 |
|---|---|
| 決定変数 | 整数値を取る変数（全整数計画法）または一部が整数の変数（混合整数計画法） |
| 0-1変数 | 「する/しない」を表すバイナリ変数（特殊な整数変数） |
| 目的関数 | 最大化または最小化する指標 |
| 制約条件 | 決定変数が満たすべき条件 |
| LP緩和 | 整数条件を外した線形計画問題（上界・下界を提供） |
| 分枝限定法 | LP緩和を利用して整数解を効率的に探索するアルゴリズム |
混合整数計画法
実務では、一部の変数が整数で残りが連続値の「混合整数計画法」（Mixed Integer Programming、MIP）が多用されます。たとえば「工場を建てるか否か」は0-1変数、「各工場の生産量」は連続変数として扱います。
実践的な使い方
ステップ1: 離散的な意思決定を特定する
問題の中から、整数でなければ意味をなさない意思決定を特定します。施設の開設/閉鎖、機器の台数、ルートの選択など、離散的な判断が必要な箇所を明確にします。
ステップ2: 0-1変数と整数変数を定義する
「する/しない」の判断は0-1変数、「何個/何台」の判断は一般整数変数として定義します。0-1変数を使えば「AとBの少なくとも一方を選ぶ」「Cを選ぶならDも必ず選ぶ」といった論理条件も制約式として表現できます。
ステップ3: 目的関数と制約条件を定式化する
最適化する指標と制約を数式で表現します。大きなMを使った「ビッグM法」により、0-1変数と連続変数の間の条件付き制約も定式化できます。
ステップ4: ソルバーで求解する
CPLEX、Gurobi、PuLP（Python）、Excelソルバーなどを使って最適解を求めます。大規模な問題では最適解が見つかるまでに時間がかかる場合があるため、許容ギャップ（最適解との差の許容範囲）を設定して実用的な解を得ます。
ステップ5: 解の妥当性を検証し感度分析を行う
得られた解が実務的に妥当かを確認します。制約条件の変更やパラメータの変動に対する感度分析を行い、解の頑健性を評価します。
活用場面
整数計画法は以下のような場面で効果を発揮します。
- 施設配置で、複数候補地から開設する拠点の最適な組み合わせを決めたいとき
- 設備投資で、予算制約のもとで投資案件のポートフォリオを最適化したいとき
- スケジューリングで、複数のジョブを複数の機械に割り当てる最適スケジュールを作りたいとき
- 配送計画で、車両台数と配送ルートの組み合わせを最適化してコストを削減したいとき
- 人員配置で、スキル要件と勤務制約を満たすシフトを自動生成したいとき
注意点
整数計画法は問題の規模が大きくなると計算時間が指数関数的に増大する可能性があります（NP困難）。大規模な問題では「最適解」ではなく「十分に良い解」を許容するアプローチが実務的です。
計算時間の管理を行う
大規模な問題では、最適解の探索に数時間から数日かかる場合があります。許容ギャップ（MIPギャップ）の設定、計算時間の上限設定、問題の分割など、計算時間を管理する工夫が必要です。
定式化の質が計算効率を左右する
同じ問題でも定式化の仕方によって計算時間が大幅に変わります。冗長な制約の追加（カッティングプレーン）や変数の対称性の排除など、効率的な定式化のテクニックを活用してください。
LP緩和の解を四捨五入しない
線形計画法の解を単純に四捨五入して整数にしても、それが実行可能解（すべての制約を満たす解）であるとは限りません。また、最適解からかけ離れた解になる可能性もあります。
まとめ
整数計画法は、離散的な意思決定を数学的に最適化する手法です。ゴモリーの切除平面法やランドとドイグの分枝限定法を基礎に発展し、施設配置、設備投資、スケジューリング、配送計画など幅広い領域で活用されています。計算時間の管理、効率的な定式化、LP緩和との関係を理解することで、現実のビジネス判断を高い精度で最適化できます。