著者

関口 恭毅

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会論文誌 (ISSN:04534514)

巻号頁・発行日

vol.24, no.1, pp.67-94, 1981

---

組合せ最適化問題を解くための代表的手法として、分岐一界値法(Branc-and-Bound Method)、動的計画法、後戻り法(Backtrack Programming)などがあげられる。しかし、これらは、解法というよりは解法開発のための接近法とでも言うのが適当で、具体的な問題に応じた効果的解法を学習しておこうとすると極めて多数のアルゴリズムを習わねばならない。一方で、各接近法の原理だけを学習しても実用的な価値が乏しいという事情がある。しかも、NP完全性の検討によって、このような事態が暫定的たものとは考え難いことが強く示唆されている。この困難を打開する一方策として、原理的解法を問題に応じて具体化する技術を体系化すること、具体的には、各種接近法を包括する統一的枠組を確立し、その特定化の内容と得られる具体的アルゴリズムの効率の関係を明らかにすることが有効と考えられる。そこで本報告では、上記3つの接近法をはじめ、完全列挙法、解析解(例えば、フローショップ問題のジョンソン規則)、整数線形計画の切除平面法などをも含む"木型計画法"なる統一的枠組を提案し、その正当性一有限性と正確性(求められる解の良さ)一の分析を行った。木型計画法は選択則(列挙の順番を定める規則)、分岐則(問題をより易しい問題に分解する規則)、上界関数(列挙の各時点での最善解を判定するための道具)、廃棄則(最善解より良い解を持たない部分問題を発見しその後の列挙の対象からはずす規則)ならびに終了条件の5つの基本要素から構成される。列挙の対象が無限集合であっても良いこと列挙に重複が許されること、廃棄則の定義が包括的であることなどが、この枠組の特色と言える。正当性の分析は最も一般性の高い場合に対して行い、有限性と正確性のための十分条件を明らかにした。結果は、有限性については選択則と分岐則が、正確性については終了条件が支配的要因であることを示している。さらに、完全列挙法、分岐一界値法、動的計画法、加算的陰伏的列挙法および切除平面法を木型計画法として完式化しなおし、提案した枠組の汎用性を例示した。

著者

関口 恭毅

出版者

中央大学商学研究会

雑誌

商学論纂 (ISSN:02867702)

巻号頁・発行日

vol.57, no.5・6, pp.209-249, 2016-03-01

著者

木瀬 洋 関口 恭毅

出版者

一般社団法人 システム制御情報学会

雑誌

システム/制御/情報 (ISSN:09161600)

巻号頁・発行日

vol.44, no.10, pp.601-608, 2000-10-15 (Released:2017-04-15)

参考文献数

14

著者

関口 恭毅 木瀬 洋

出版者

一般社団法人 システム制御情報学会

雑誌

システム/制御/情報 (ISSN:09161600)

巻号頁・発行日

vol.44, no.8, pp.468-475, 2000-08-15 (Released:2017-04-15)

参考文献数

11

著者

関口 恭毅 木瀬 洋

出版者

一般社団法人 システム制御情報学会

雑誌

システム/制御/情報 (ISSN:09161600)

巻号頁・発行日

vol.44, no.12, pp.723-731, 2000-12-15 (Released:2017-04-15)

参考文献数

21

著者

関口 恭毅

出版者

北海道大学

雑誌

基盤研究(C)

巻号頁・発行日

1997

---

(1)数理モデル作成の前段階である実際問題の整理とその記述を支援するために、汎実体一関連モデル(GERM)なる新しい情報モデルと、これに基づく問題記述法を提案し、かつ、これをデータベース化する方式を確立した。新方式をインプリメントした事例データベースのプロトタイプシステムを開発してその有効性を検証した。また、GERMによる問題記述によれば、最適化問題ばかりでなくシミュレーションの対象となる問題の記述も可能なことを明かにした。(2)教理モデルを純粋に数学的なオブジェクトとして定義し、これと対応する問題定義を「結合条件」と呼ぶ情報によって結びつける、多対多の対応付けを可能にする技術を確立した。これにより数埋モデルの再利用が容易になり、かつ、問題定義に対応する数理モデルの作成を支援する事例データベースの開発が可能になった。これらを検証する事例データベースのプロトタイプシステムを開発した。本方式では、モデル/データ独立が実現している。(3)ユーザが作成する数理モデルである「ユーザ定義モデル」とソルバーが前提とする数埋モデルである「標準モデル」およびソルバーオプションを「結合情報」によって対応づけてソルバーを起動する方式を開発するとともに、問題の数値例を上記のプロトタイプシステムに組み込む方式を開発した。これによってモデル/ソルバー独立が実現され、既存ソルバーの再利用が容易になるので、無駄な開発努力を省くことができる。(4)事例データベースのプロトタイプシステムを開発した経験から、オブジェクト型を記述の基本要素とするGERMは、ユーザにとって、その記述内容を直感的に理解することは必ずしも容易ではないことが分かった。そこで、オブジェクト・インスタンスを記述することでオブジェクト型を定義できるユーザインターフェースを提案し、その実現方法を構成した。