Discovery Sagaサイレントキーワード俯瞰

最適化 / アルゴリズム / 内点法 / 線形計画問題 / 最適化問題

本研究は、大規模な数理計画問題を効率よく解くアルゴリズムを開発し、その理論的な性質と実用性を明らかにすることを目的としている。平成12年度には、そのための基礎的な研究を行った。大規模な数理計画問題では、問題に含まれる変数に自由変数、非負変数、上下限制約付きの変数の3種類がある。これらの変数を同時に、そのまま処理することが、問題を効率よく解く上で重要である。そこで、このような問題を直接解く内点法によるアルゴリズムについて研究を行った。平成13年度には、係数行列に特殊な構造を持つ大規模な最適化問題に対するアルゴリズムの研究を行った。特に、多期間の確率計画問題から派生する線形計画問題を効率よく解くアルゴリズムについて研究した。この問題は、期間の数あるいはシナリオの数が増えると、変数の数が非常に大きくなるが、係数行列の右上部分がゼロ行列という特徴を持つ。この特徴を利用し、大規模な多期間の確率計画問題を効率的に解くアルゴリズムを開発することができた。平成14年度は、大規模な線形計画問題あるいは非線形計画問題を解く新しい内点法について研究した。この方法は、問題に現れる一部の変数について対数変換を施した後に、ニュートン法を適用する点において従来のアルゴリズムと大きく異なる。変数に対数変換を施すことにより、問題の実行可能領域に横たわる複雑なセンターパスが滑らかになり、内点法により効率よくパスを追跡することが可能となることが期待される。実際、数値実験により、現実の線形計画問題において、提案したアルゴリズムにより対数変換を使わない場合に比べ反復回数を減少させることができることを確認した。

アルゴリズム / 半正定値計画 / 双向グラフ / 安定集合問題 / 最適化問題

組合せ最適化問題の中でも最も研究されているものの一つが無向グラフ上の安定集合問題である。一般にこの問題はNP完全クラスに属し、多項式時間解法はおそらく存在しないであろう。しかし、パーフェクトグラフ、クローフリーグラフなどの幾つかのグラフクラスに対しては多項式時間解法が存在する。特にパーフェクトグラフに対する多項式時間解法の特徴は、安定集合問題がその半正定値緩和問題と一致するところにある。またGrotschel-Lovasz-Schrijverは、その逆命題も成立することを証明した。すなわち、安定集合問題とその半正定値緩和問題が一致するための必要十分条件が無向グラフがパーフェクトであることを示した。
本年度の研究成果は、このGrotschel-Lovaz-Schrijverの結果の別証明を与えたことと、この結果を一般化安定集合問題へと拡張したという2つである。彼らの証明では、無向グラフの補グラフとアンチブロッカーという概念を用いている。我々は、半正定値計画問題に対する2次計画問題表現を利用することで、補グラフなどの概念を導入しない別証明を与えた。
一方、一般化安定集合問題は安定集合問題を双向グラフ上へと自然な形で拡張したものであるが、双向グラフに対しては補グラフという概念がない。そのため「双向グラフがパーフェクト」と「一般化安定集合問題とその半正定値緩和が一致」という命題が同値であることを示すには、彼らの証明法を拡張することは困難であるが、補グラフという概念を用いない我々の証明法は、拡張された命題の同値性証明まで適用できるものであった。
これらの結果は国際会議において発表し、論文としてまとめ学術雑誌に投稿した。

【研究分担者】
中田和秀	東京工業大学	大学院・社会理工学研究科	助手	(Kakenデータベース)
矢島安敏	東京工業大学	大学院・社会理工学研究科	助教授	(Kakenデータベース)
宇野毅明	国立情報学研究所	情報学基礎研究系	助教授	(Kakenデータベース)