コラム・特集

4.5 離散形最適化問題のコンピュータ解法

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

第4章 離散形最適化

4.5 離散形最適化問題のコンピュータ解法

離散形最適化問題が定式化された後は,そのモデルを解くための,適当なコンピュータ・ソフトウェアを見つける必要がある。モデル作成者は商用の 整数計画コード (IBMのMPSX―MIPのような ), そのために特別に開発されたコード,あるいは発見的方法によるコードを利用できる。ある状況の下で, どの型のソフトウエアを用いるべきかは ,必ずしも簡単には決められない。 離散形最適化問題を解くための最も一般的な方法は, 商用の整数計画コードを使用することである。このようなコードが普及している主な理由は,それが手に入れ易いということである。大部分のコンピュータ製造業者は顧客のために整数計画ソフトウエアを開発しており,多くのコンサルティング会社が独自のソフトウェアを市場 に出している。商用のソフトウエアを使用する他の理由としては, コードの信頼性(おそらくこれらのコードは広範囲の問題に繰り返し使用されてきたことにより,得られた解を信頼できる)と ,それらが本質的に報性を持っているということがあげられる。多くの商用のコードは,分枝限定アルゴリズムを使用しており,また一部にはBenderの分割法の改良に基づいたものもある。 商用コードを使用するときの難点は,それが一般的性質を持つているために,ある特定問題を解くのにたいヘん時間がかかる場合があることである。この難点は問題が大きくなるにつれ,またモデルが複雑になるにつれて増大してくるモデルが大き過ぎて,商用のコードを使ったのでは適当な時間内に解くことができない場合には , モデル作成者は,特別に作成した専用コードや発見的なコードに頼らなければならないモデルの構造のある特性を利用した専用コードが既に存在している場合もあり, 開発しなければならない場合もある。たとえば,さまざまの型のナップザック問題や工場配置問題を,効率よく解くために作られた多くの専用コードが存在する。専用コードを開発するとすれば,いくつかの考慮しなければならない点がある。第1点は,その開発に長い時間と多くの資源を必要とする場合が多いということである。第2点に,専用の整数計画コードは基本構造の同じモデルにしか使用できないということである。

そのためモデル作成者は,専用コードを開発しようとするモデルが,限られた利用に対する大きな出費を十分是認できるほど , 実際的で重要なのかを確かめなければならない。

商用か,または専用の整数計画コードが,いまかかえている問題に適していなければ(たぶん規櫛汰きいか, そのモデルに利用できる構造が欠落しているかの理由によるが),モデル作成者は発見的コードの開発を強いられることになる。そのコードは問題の特定の部分を解くために設計された,なんらかの最適化手法を含むこともある。しかし問題の他の部分には“早くて乱暴な”泥くさいアルゴリズムを使用するか,モンテカルロ・シミュレーション技法を利用して解くことになるであろう。発見的方法の利点は,短時間でたいへん複雑な問題に対しても,解を得ることができることである。しかし発見的コードは,専用コードの不利な点と同じような欠陥に加えて,さらに発見的手法によって得られた解は必ずしも最適解ではないという問題点がある。

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

関連記事一覧

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

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

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

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