学位報告

学位報告４
報告番号

※甲第号

主論

文の要旨

論文題目
Generation Approaches for Combinatorial Optimization Problems（組合せ最適化問題に対する生成型アプローチ）
氏

名論

文

内呉

偉

容の要

旨

近年，技術革新に伴い，大量の情報資源を有効に利用する必要性が高まってきた．
この目的において組合せ最適化は応用数学やコンピュータサイエンスなどの分野で注目を集めている．重要な課題の多くが組合せ最適化問題として定式化できるが，NP 困難性に代表されるように，多くの組合せ最適化問題に対し，問題規模が大きい場合，厳密な最適解を得ることが極めて困難であることが知られている．
組合せ最適化問題の多くは，線形計画問題，整数計画問題あるいは混合整数計画（mixed integer programming, MIP）問題として定式化できる．これらの制約は線形の等式あるいは不等式であるため，いずれも行列で表現できるが，応用上重要な問題の中にはこの行列が極めて大規模で，計算機上に保持することが可能な現実的なサイズでに収まらないものが多数存在する．このような問題を現実的に解決する方法として，行生成と列生成アプローチがある．
第２章では，代表的な行生成アルゴリズムを紹介する．ベンダーズ分解法（Bendersdecomposition）は，ある混合整数計画問題を整数部分と連続部分に分けてそれぞれを主問題と部分問題として定義し，これらを交互に解く操作を反復する方法である．
主問題では，整数部分の最適解を取得し，部分問題の入力として与える．一方部分問題では，入力された主問題の最適解を実行可能領域からカット（切除）できるかどうかを検証する．カットできる場合は，部分問題で生成された行を主問題に追加する．このように２つの問題を繰り返し解くことで最適解を見つける．また，ベンダーズ分解法の拡張として知られている論理型ベンダーズ分解法は，双対の定義を拡張することによって，部分問題が NP 困難な問題であっても適用できる．これら

学位関係に加えて，切除平面法とピボット・プローブアルゴリズム（pivot and probealgorithm, PAPA）の基本構造とアイデアを紹介する．
第３章では，列生成法の基本的な枠組みと，列生成に基づくダンツィク・ウルフ分解法（Dantzig-Wolfe decomposition）を説明する．制約条件の行列の列数が大規模である問題に対しては，列生成法が有効であることが知られている．列生成法は，列の小規模な部分集合からはじめ，線形緩和問題（主問題）に対する双対問題から得られる双対価格を重みとしてそれら重みの和を最大にする列を発見する問題（価格付け問題）を解いたのち，得られた列を列の部分集合に追加する操作を，主問題の目的関数値が改善できなくなるまで繰り返す手法である．実世界に現れる大規模問題を解く際には，目的関数や制約条件がすべて線形であっても，価格付け問題を厳密に解くのは難しい場合がある．このような問題に対して，大規模な問題を直接解くのではなく，ブロック構造を利用することにより，価格付け問題を解きやすい部分問題に分割できることがしばしばある．このような解法をダンツィク・ウルフ分解と呼ぶ．
第４章と第５章では，組合せ最適化問題に対するロバスト最適化を考え，行生成アプローチに基づく手法を提案する．最適化手法のほとんどは，入力データが既知のものであるという前提のもとにアルゴリズムが設計されている．しかし，多くの現実問題において入力データには曖昧さや不確定要素が内在している．たとえば，生産計画を立てるために最適化問題を解く段階では，需要が確定しておらず，需要予測に基づいて計画を行わなければならない．このような例では，計画の実行が終了した時点では需要ははっきり定まっており，確定した需要に基づいた実績によって計画の善し悪しが判断される．したがって，「計画段階で別の判断をしていればもっと利益が上がったのに」と後悔することのないような計画が望まれる．このような不確定要素を深く考慮せず，たとえば予測値をそのまま入力データとして既存の最適化手法を適用して得られた解を用いたのでは，入力データの変動に大きく影響されないような解を与える機能がないため，大きな後悔を招く恐れがある．たとえば，渋滞予測に基づいて平均所要時間最短のルートを選んでも最も早く着くとは限らない．このような入力データの変動に大きく影響されないようなロバストな解，すなわち変動の組合せによって生じ得るいかなる場合に対しても後悔の度合いが小さい解を得るようなアルゴリズムが望まれている．また，そのようなアルゴリズムが有用であるためには，大規模なデータに適用できることが望ましい．このような問題を解決するためのアルゴリズム設計の方法論の確立と，効率的なアルゴリズムの設計がこれらの章の研究目的である．これらの章では，組合せ最適化問題に対して，定義するデータが曖昧さあるいは不確定性を含んでいる場合にも信頼できる結果を返すモデリング技法および近似解法と厳密解法を提案する．
第４章では，最大後悔最小化基準の一般化割当問題に対する近似解法と厳密解法を提案する．この問題ではデータ変動に起因する最悪の状況を後悔の度合いで測る問題を考えているが，これは変動による最大コストを最小化する min-max 型の問題pよりさらに複雑で困難な問題であるといえる．まずロバスト一般化割当問題がΣ2 完全であること，つまり多項式階層におけるクラス NP の一つ上の階層の完全問題で38 字×23 行学位関係あることを証明する．近似解法としては，シナリオ固定法 3 種と相対代替法と名付けた方法を提案し，シナリオ固定法の 1 つが 2 近似アルゴリズムであることの証
明（近似アルゴリズムの出力する解の目的関数値と最適解の目的関数値の比（近似度）が 2 倍内に収まること）および 4 種の解法の実験的解析の結果を示す．厳密解法としては，ベンダーズ分解法と分枝カット法を提案し，初期カット生成に関する理論的性質や，動的計画法の 2 種の表を利用した釘付けテストの高速化法など，様々なアイデアを提案して高い効率を実現している．
第５章では，最大後悔最小化基準の多次元 0-1 ナップサック問題を対象とする．ナップサック問題は，ナップサックの容量と，複数の要素の各々に対して利得とサイズが与えられたとき，ナップサックに入れる要素をいくつか選び，それらのサイズの合計がナップサックの容量を超えないという条件の下で，選んだ要素の利得の合計を最大化する問題である．多次元 0-1 ナップサック問題は，ナップサック制約が複数ある問題で，積荷作業や，資金計画問題など，現実社会の問題を定式化する際に数多く見受けられ，また多くの応用問題を解く際にしばしば子問題として現れる重要な問題である．この問題を解くための最適化手法として，まず，第４章で提案した相対代替法を行生成アプローチで改善していく反復相対代替法を提案する．各反復で得られる制約は線形であり，相対代替法により，最適値に対する上界と下界の両方が得られるので，これらの値の近さを検証することで性能を評価することが出来る．また，比較対象として，第 4 章で試したシナリオ固定法，ベンダーズ分解法とそれに基づいた分枝カット法を実装し，生成した問題例に対してこれらの解法の比較実験を行った結果を示す．
第６章では，航空乗務員スケジューリング問題に対する列生成アプローチを提案する．航空乗務員スケジューリング問題とは，与えられた全てのフライトを運航するスケジュールの中で，必要な乗務員数等を最小化する問題である．一般に航空スケジューリング問題には非常に多くの制約が存在するため，すべての制約を満たしつつできるだけ良いスケジュールを作成することは極めて困難である．航空乗務員スケジューリング問題を集合被覆問題として定式し，列生成アプローチを用いる．また，列生成を高速化するために，グラフの各頂点に多次元の状態を持つ動的計画法を設計する．企業から提供されたフライトデータを用いて計算実験を行い，大規模な問題例でも提案手法が高精度の解を出力することを報告し，列生成アプローチが有効であることを示す．
本研究では，ロバスト最適化問題やスケジューリング問題など，見かけの異なる問題に対して生成型のアプローチが有効であることを示した．本研究の成果が，実世界の組合せ最適化問題に対する行生成や列生成に基づくアルゴリズムの設計開発の一助になれば幸いである．

38 字×23 行