コラム・特集

4.4 離散形最適化のアルゴリズム

IEハンドブック
第14部 インダストリアル・エンジニアリングの最適化

第4章 離散形最適化

4.4 離散形最適化のアルゴリズム

離散形最適化問題を解くのに開発されたアルゴリズムは,次の種類に分類できる。

1.列挙的アルゴリ ズム
2.切除平面アルゴリズム
3.群論的アルゴリズム 詳細の程度は異なるが,それぞれの種類ごとに説明しておこう

列挙的アルゴリズム
すべての列挙的アルゴリズムの背後にある中心的な考え方は,各整数可能解を1つずつ調べあげることをしなくても,すべての可能解を理論的に探索することができるということである。このようなアルゴリズムは,通常 “分割し支配する”と呼ばれている戦略を適用すること により,たくさんの可能解を,考慮の対象から外そうとしている。 最も広く知られている列挙的アリゴリズムは,おそらく ,「分枝限定アルゴリズム」として知られているもので,一般的MIP問題を解くにあたって,LandとDoigが提案し た基本アルゴリズムを,Dakinが手直ししたものである。 分枝限定法の基本的な原理は,次の例によって最もよく例示できよう。

アルゴリズムはまず始めにx1, x2の整数制約を無視しx2て,このMIP問題を線形計画問題として解く,この線 形計画問題LP-1のグラフによる解を図表14.4.1に示すx1=1.5, x2=2の最適解において,x2の整数制約は満たされているが, x1に関しては満たされていないことが分かる。この段階で,MIP問題の目的関数の最適値の上限が, 9.5になっていることに注意しておこう。

x1を整数値にするために,LP-1に新しい制約を付け加えることによって,LP-2とLP-3の2つの新しい線形計画問題をつくる。この新しい制約は,LP―1の最適解がLP-2や LP-3ではもはや許容ではなく ,しかも,すべての整数許容解がそのまま許容されているようなものでなければならない。LP-1に制約条件x1≧ 2を付け加えてLP-3をつくり,また ,x1≦ 1を LP-1に付け加えてLP-2をつくる。LP-2 とLP-3の解を,それぞれ 図表14.4.2図表14.4.3に示す。 LP-2の最適解x1=1,x2=2は MIPに対して許容である。ここで,MIPの目的関数の最適値の下限 z*≧ 9を 得ることができる。LP-2からはもう枝分れを行う必要はない。

 

LP-3の最適解x1=2,x2=1.83はx2の整数制約を破っている。 LP-3にx2≦ 1と x2≧2の 制約式を加えることにより, LP-4とLP-5をつくり, これらのLPを解く.読者はLP-4が x1=3,x2=1の 最適解を持ち, z=7でMIPに対して許容になること, LP-5は非許容となることを確かめてもらいたい。

図表14.4.4に示されているような樹状図を使って, このMIPを解くときの解法過程を示すことができる。この過程は“分割し支配する”の基本的な戦略を反映したものである。

Balasによって,0-1整数計画に対する特殊な列挙的アルゴリズムが開発されている。通常これは「陰的列挙法」として知られている。彼のアルゴリズムでは,間題が次のような大枠に沿って定式化されていることが必要である。

1.目的関数の最小化問題である。
2.すべての目的関数の係数が非負でなければならない。
3.すべての制約式が≧の形でなければならない。この形に問題を変換する手順は PlaneとMcMillanが与えている。

Balasのアルゴリズムの背景にある考え方は,始めにすべてのxjを0と置き,順次1回に一変数を1と置き換えながら,許容解が見つかるまでこれを続ける。次にアルゴリズムは,他の可能解を調べるために“後民り探索”を行い,すべての可能な組み合わせが陽的にあるいは陰的に探索しつくされるまで続ける。代理制約を使うというような,この基本アルゴリズムに対する各種の改良がGeoffrionとMarstenの文献で詳細に述べられている。

切除平面アルゴリズム
整数計画問題を解くための最初の方法はGomoryによって与られた。彼のアルゴリズムの着想は,毎回その前の線形計画問題の最適解を切除するような制約条件を付加した,新たな線形計画問題を逐次的に解くことによって,最適整数解に到達できないだろうかという点にある。この付加された制約式は「切除平面」,あるいは簡単に「カット」と呼ばれている。次の例でこの方法を示す。

ここでS1とS2は原問題の制約式に対応したスラック変数で,S3はこのカットによって生じた新しいスラック変数である。このカットは 図表14.4.5に破線で示してある。

この例題により,すべてのカットが持つ2つの重要な性質が示されている。

1.それまでのLP最適解はカットの制約を満足しない。
2.すべての整数許容解は新しいカットを満足する。アルゴリズムはカットの付加された線形計画問題を解き,さらに新しいカットをつけ加え, この手順をこれらの問題のうちの1つの最適解が整数制約を満足するまで続ける。最後に得られた最適解が元の整数計画問題の最適解となる。例題では,次に示す形のもう1つのカットが追加された後に,最適解に到達している。

-1/2S1-1/2S3+S4=-1/2

問題がMIPからPIPに変わった場合に必要な修正を含む, さまざまの切除平面アルゴリズムの詳細につい ては ,Garinkelと Nemhauserを参照された。

群論的アルゴリズム
整数計画を解くアルゴリズムのもう1つの種類は一一これは最近広く注目を受けているものである一一 最初にGomonyによって名付けられ,Shapiroによって大きく拡張された群論的方法である。群論的方法は数学的な内容がたいへんに複雑なので,ここでは詳細については述べない。ここではMIP問題に,この手法を適用しようと試みると計算上の困難が生じるため,主にPIP問題に使用されていると言うにとどめておく。 最後に,整数計画法の解法を論じる上で,どうしてもいくつかの発見的方法に触れなくてはならない。特殊なクラスの整数計画法のための発見的方法が,最近の研究で数多く開発されている。この中には,ナップザック間題や工場配置問題が含まれている。発見的方法は,より大規模で現実的な整数計画モデルを解くためのアルゴリズムの開発に重要な役割を演じている。整数計画アルゴリズムの現状に関する。すぐれ論文としては,GeoffrionとMarstenを参照するとよい。

 本コラムは絶版となっている「IEハンドブック(サルベンティ編・日本能率協会訳・1986)」をアーカイブとして掲載するものです。このハンドブックの各章は多くの事例と理論を通して生産性向上に対するアイデアを提供するべく専門家によって執筆されています。基盤をなしているIEの考え方・原則はインダストリアル・エンジニアリングにかかわるすべてのひとに有用でしょう。

関連記事一覧

2019ものづくり公開セミナーガイド

B2Bデジタルマーケティングセミナー

ものづくり人材育成ソリューション

マーケティング分野オンラインセミナー