サイト内の現在位置

大規模集合分割問題の解法についての論文を投稿しました

大規模な集合分割問題に対する従来の解法としては、列生成法が効率的な解法として知られており、実装も容易ではありますが、厳密解を得る保証は無く、多くの場合は近似解を得るにとどまります。なお、類似の集合分割問題と比較しても、制約条件が厳しいため、厳密解を得られる確率は低くなります。一方、列生成法と分枝限定法と組み合わせた分枝価格法により厳密解を得ることは可能ですが、複雑な分枝操作を必要とし、メモリ使用量も増大する課題があります。

そこで、本論文では、従来の列生成法を拡張した、「列生成消去法」と呼ぶ新たなアプローチを提案しました。生成する列を決定する条件を従来の列生成法と比較して緩和することで、厳密解獲得率や近似解の精度を向上させる一方、不要列の消去機構を組み込むことで、問題サイズの増大を抑制しています。集合分割問題としてはシンプルなケースである、コスト係数が一定の「最小乗務員問題」において、実際のバス路線のGTFSオープンデータを用いた数値実験の結果、従来の列生成法では厳密解獲得率が約3％にとどまっていたのに対し、提案手法では約99％と飛躍的に向上しました。また、変数の個数が数十万個となる様な大規模な問題においても、元の問題の約3割程度まで圧縮されることが示されました。集合分割問題としては複雑なケースである、コスト係数が不均一の場合でも、従来の列生成法と比較し、近似解の精度が改善することが示されています。

最終的に解を得るまでのトータルの計算時間の短縮という点では、まだまだ課題が残りますが、従来の列生成法を少し改良しただけで、厳密解を得る確率が飛躍的に向上する不思議な結果ではあります。将来的には、スケジュール候補などが新たに追加された場合のオンライン的な使い方（最適解を再計算により解き直す必要があるかの短時間での検証）にも使えるかもしれませんね。