極めて困難な離散最適化問題に対する厳密解法

点击翻译按钮获取中文摘要

今年度は,整数計画問題に対する厳密解法を主な研究対象とした.まず,近年提案された整数計画問題に対する主算法であるIntegral Basis Methodについて,昨年度は二次割当問題への適用を行い,問題構造を利用したアルゴリズムの提案を行ったが,今年度は一般の整数計画問題に対するアルゴリズムの効率化の検討を始めた.すでに共同研究として,緩和問題の利用と変数の選択規則による改善方法を提案したが,それらの精密化,および,プログラムの見直しによって大規模な問題を扱うことができるはずである.また,Integral Basis Method以外にも主算法が1960年代から70年代にかけて提案されていたが,これらの見直しを行った.次に,巡回セールスマン問題を対象として,整数計画問題による定式化の比較を行った.これは,近年の整数計画ソルバーの進歩により,問題固有のアルゴリズムを開発することなく,定式化を行うことによって解決できる可能性が高まっていることが背景にある.巡回セールスマン問題には,古典的な定式化に加え,最近新しい定式化が何種類か提案されている.これらを比較したところ,問題固有の解法を上回るような定式化があるわけではなく,今後,切除平面を加えるなどの工夫が必要であることがわかった.また,共同研究として,整数計画ソルバーの並列化に関する研究を行った.これも整数計画ソルバーの進歩が背景にある.既存の並列化の研究は,分枝限定法や分枝カット法のフレームワークを与えるものがほとんどであったが,この研究では,分枝カット法自体を利用するものであり,整数計画ソルバーの性能を最大限活用することを目的としている.現在実験を行っているところである.