@misc{oai:ir.soken.ac.jp:00003139, author = {乾, 伸雄 and イヌイ, ノブオ and INUI, Nobuo}, month = {2016-02-17, 2016-02-17}, note = {本論文は，組合せ最適化問題の効率的な厳密解法に関するものである． 背景として，近年のハードウェア・ソフトウェア技術の非常な進歩が 挙げられる．これらの進歩に伴って，混合整数線形計画問題(MILP) や充足可能性問題(SAT) などを解くためのソルバーの性能が飛躍的に 向上した．その結果，これまで解くことが出来なかった問題が実用的 な時間内に解けたり，厳密解がわからなかった問題の厳密解がわかる ようになってきた．そのため，ソルバーは幅広い分野で使われ始めて いる． しかし，ソルバーを使って問題を解こうとしても，問題によって解を 得るまでの時間にばらつきがあったり，非常に時間がかかることがあ る．得られた解が問題の厳密解であることを保証している問題記述で あっても，このようなことは問題記述が効率的に厳密解を求めるのに は不十分である場合に起きる．本論文ではこの点に着目し，計算時間 に特化して組合せ最適化問題を効率的に解くための手法を研究した． 本論文では三つの重要な既存問題に関して，次の二点を研究した． 1. ソルバーの違いによる効率性の比較 2. 計算時間的効率性を重視した問題記述 ソルバーの違いに関しては，特に近年の性能向上が著しい二つのソル バー，MILP ソルバーとSAT ソルバー，を個々の問題に適用し，問題記 述の効率性を比較する．そして，問題記述独自の効率化手法を開発す ることで，さらに効率的に問題を解くための手法を確立する． 本論文は6章からなる．1 章では本研究の動機について述べ，2 章では 関連研究について述べる．3章から5章が具体的な研究成果となる．そ して，6 章では本論文の研究成果をまとめる． 3章では決定性有限状態オートマトン(DFA)の学習問題の一つである最 小無矛盾DFA生成問題を取り上げる．この問題は古典的な研究問題であ り，正・負のラベルが与えられた二つの文字列集合に無矛盾な状態数 最小のDFA を求めることが目的である．この問題については，近年SAT によるアプローチが提案され，現在最も効率的な手法であると考えら れるが，文字列集合が疎な場合は解くことが難しい問題となってしま う．本章ではMILPとSATによる適用を評価し，SAT が効果的であること を実験的に明らかにした．この結果から，SATを使ったアプローチを 更に改善するため，変数の削減，対称性除去制約，ハイパーエッジ彩 色問題制約などの新たな問題記述法を導入した．そして，これらの手 法について，ベンチマーク問題を使って計算時間を評価した．その結 果，提案手法を用いることによって，特に従来手法によって解くこと が難しい問題を高速に解くことができるようになった． 4章では，走査型半導体露光装置における移動順最適化問題を取り上げ る．この問題は，ウェハ上のすべての所定の位置に回路パタンを露光 する最短経路を決定する問題である．ウェハ一枚の露光時間が少しで も短いと一日の生産量を高めることができ，コスト削減に寄与する． 走査型半導体露光装置では一枚のウェハ上の複数箇所に回路パタンを走 査露光するので，走査方向が上と下の場合，ある露光位置から別の露 光位置までの移動時間には（上上，上下，下上，下下）の４種類が存在 し，最短経路では高々一つの移動時間が選ばれることになる．このよう な移動順最適化問題は巡回セールスマン問題(TSP)の一種と考えること ができるが，TSP による表現方法は過去に提案されてなく，厳密解を得 ることが難しい問題であった．まず，MILPソルバーとMaxSATソルバーの TSP に対する適用可能性を予備実験により評価し，MILP ソルバーの適 用が適切であると判断した．次にTSP ソルバーを適用するため，二つの 所定位置間の移動時間に対して３種類の表現方法を提案し，実用に近い 問題で評価した．その結果，MILP で記述するよりも，TSP ソルバーを 用いた提案手法によって最短時間の厳密解が効率よく得られることが わかった． 5章ではナーススケジューリング問題を取り上げる．ナーススケジューリ ング問題は，病院の看護師の勤務スケジュールを決定する問題であり， 病院での勤務体制の効率化のために実用的に重要な研究である． 勤務に関する制約条件を満たす解の中から最も看護師数に対する要求を 満たす解(ペナルティ最小化)を求める問題である．この問題で は，非常に多くの変数カウントが現れるが，MILPソルバーで解くことは 難しいベンチマーク問題が存在した．そこで，SATによる記述を行った． SATので変数カウントについて二つの方法を提案し，実験的に効果を検証 した．この結果，ペナルティが小さい問題に対しては，MILP ソルバーが 解けない問題でもSATソルバーを使うことによって高速に解が求まること がわかった． 6 章では，個々の問題に関する研究成果をまとめる．最小無矛盾DFA生成 問題はSATによるアプローチが有効であり，移動順最適化問題はMILPによる アプローチが有効であった．また，ナーススケジューリング問題は問題に よってSATが有効であったり，MILPが有効である問題であったが，効率的に 厳密解を得るための手法をまとめる． 本論文の成果として，三つの既存問題に関して，問題を分析することに よって得られるアドホックな条件に関する新規の提案を行い，実験的に それらの条件の計算時間短縮への寄与を確認した．そして，MILPとSATに よる問題記述を行い，実験結果から問題記述の適用可能性を検討した． そこから，組合せ最適化問題の厳密解法に対して効率的な記述方法を示した．, application/pdf, 総研大甲第1512号}, title = {組み合わせ最適化問題に対する効率的な厳密解法のための問題の記述法に関する研究}, year = {} }