例えば, 目的関数を最大化するような 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 の分解法と,
分枝限定法を組み合わせて解かれる事が多い.
実務上は，必ずしも最適解が必要とは限らないことから，
実用的な計算時間である程度良い解を求める
発見的解法の研究も数多くなされている.
しかしながら, 高性能な発見的解法は,
問題の特質に着目している事が多く,
高性能の発見的解法の構築法を一般的に議論する事は困難である.
\begin{thebibliography}{99}
%---------------------------
\bibitem{A-C-01+Konno}
今野浩, 鈴木久敏編著,
『整数計画法と組合せ最適化問題』,
日科技連出版社, 1978.
%---------------------------
\bibitem{A-C-01+Ibaraki}
茨木俊秀,
『組合せ最適化 分枝限定法を中心として』,
産業図書, 1983.
%---------------------------
\bibitem{A-C-01+Nemhauser} %
G. L. Nemhauser and L. A. Wolsey,
{\it Integer and Combinatorial Optimization},
Wiley, New York, 1988.
\end{thebibliography}
%\end{document}
以下のように記述される.
\[
\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 の分解法と,
分枝限定法を組み合わせて解かれる事が多い.
実務上は，必ずしも最適解が必要とは限らないことから，
実用的な計算時間である程度良い解を求める
発見的解法の研究も数多くなされている.
しかしながら, 高性能な発見的解法は,
問題の特質に着目している事が多く,
高性能の発見的解法の構築法を一般的に議論する事は困難である.
\begin{thebibliography}{99}
%---------------------------
\bibitem{A-C-01+Konno}
今野浩, 鈴木久敏編著,
『整数計画法と組合せ最適化問題』,
日科技連出版社, 1978.
%---------------------------
\bibitem{A-C-01+Ibaraki}
茨木俊秀,
『組合せ最適化 分枝限定法を中心として』,
産業図書, 1983.
%---------------------------
\bibitem{A-C-01+Nemhauser} %
G. L. Nemhauser and L. A. Wolsey,
{\it Integer and Combinatorial Optimization},
Wiley, New York, 1988.
\end{thebibliography}
%\end{document}
