整数計画

【せいすうけいかく (integer programming)】

概要

最適化問題において, 変数が整数値を取るという制約がいくつかの変数に付いているとき, これを整数計画と呼ぶ. 整数値を取る変数は, 整数変数と呼ばれる. 整数計画問題は, NP困難と呼ばれる問題クラスに属しており, 厳密解をいつでも効率的に求める算法の存在は, 理論的に絶望視されている. しかしながら, 様々な技法の開発と計算機の高性能化に伴い, 実用的には十分短い計算時間で解ける問題のクラスとサイズは, いまも広がり続けている.

詳説

　最適化問題において, 変数が整数値を取るという制約がいくつかの変数に付いているとき, これを整数計画(integer programming)(整数計画法, 整数計画問題)と呼ぶ. 特に, 全ての変数が0または1の値を取るものを, 0-1整数計画問題 (0-1 integer programming problem)と呼ぶ. また, 全ての変数が整数値をとるものを, 全整数計画問題 (all integer programming problem) と呼ぶ．整数値を取る変数と, 実数値を取る変数が混じっている問題は, 混合整数計画(mixed integer programming problem)と呼ばれるが, MIP（ミップ)と省略して呼ばれる事も多い.

　例えば, 目的関数を最大化するような 0-1 整数計画問題は, 以下のように記述される.

${\begin{array}{lll}{\mbox{max.}}&f(x_{1},x_{2},\ldots ,x_{n})\\{\mbox{s. t.}}&g_{i}(x_{1},x_{2},\ldots ,x_{n})\geq b_{i}&(i=1,2,\ldots ,m),\\&x_{1},x_{2},\ldots ,x_{n}\in \{0,1\}.\\\end{array}}$

整数値を取る変数は, 整数変数と呼ばれ, 0または1の値を取る変数は, 0-1変数と呼ばれる.

　整数計画問題は, NP困難と呼ばれる問題クラスに属しており, 厳密解をいつでも効率的に求める算法の存在は, 理論的に絶望視されている. しかしながら, 様々な技法の開発と計算機の高性能化に伴い, 実用的に十分短い計算時間で解ける問題のクラスとサイズは, いまも広がり続けている.

　上記の3つの問題の厳密解を求めるのは, 経験的に, 0-1整数計画問題が最も解きやすく, 次に全整数計画問題, そして混合整数計画問題が最も難しいと言われる.しかしながら, 発見的解法の作り易さは, 必ずしもこの順ではない.

　上に記述した0-1整数計画問題において，目的関数と制約式中の関数が全て線形関数であるような問題は, 数多くの研究がなされており, また市販のソフトウェアもそのような問題を解くものがほとんどである．0-1整数計画問題を解く解法は, 「0または1の値を取る」という制約を, 「0以上1以下の値を取る」という制約に緩和した問題 (線形緩和問題)を手がかりにした分枝限定法, あるいは分枝切除法を用いる事が多い.

　全整数計画問題は, 整数値を表すのに, 複数の0-1変数を使う事によって, 0-1整数計画問題に変形することができるが, このような変形は一般に解法の効率を落とす事が多い. 全整数計画問題も, 整数値をとる変数を連続変数に緩和した線形緩和問題を手がかりにした分枝限定法を用いて解くことが多い.

　混合整数計画問題は, 問題を連続変数部分と整数変数部分に分解する手続きを繰り返しながら解く Benders の分解法と, 分枝限定法を組み合わせて解かれる事が多い.

　実用的な計算時間である程度良い解を求める発見的解法の研究も数多くなされている. しかしながら, 高性能な発見的解法は, 問題の特質に着目している事が多く, 高性能の発見的解法の構築法を一般的に議論する事は困難である.

---

参考文献

[1] 今野浩, 鈴木久敏編著,『整数計画法と組合せ最適化問題』, 日科技連出版社, 1978.

[2] 茨木俊秀,『組合せ最適化 分枝限定法を中心として』,産業図書, 1983.

[3] 久保幹雄, 田村明久, 松井知己編, 『応用数理計画ハンドブック』, 朝倉書店, 2002.

[4] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, 1988.