Efficient Algorithms for Solving the Sum of Linear Ratios Problem with Lower Dimension

分数和問題(Sum Of Liner Ratios Problem,SOLR)はNP困難な問題としてよく知られており，その応用領域の広さから数多くの応用および最適解探索のための研究がなされている。実問題における幅広い問題がSOLRとして定式化することが可能であり，その多くが少数変数かつ膨大な分数比を有しているという特徴を持つ。本論文は低次元におけるSOLR問題に焦点を当てた新たな効果的アルゴリズムの提案およびその検証を行った。主な成果を以下に示す。
●低次元SOLR問題を統括的に解くための2分岐ルールに基づく分枝限定法を提案した。具体的には， SOLR問題を線形目的関数と2次および1次の制約を持つ2次計画問題へ変換し，補助変数を利用して全ての2次制約に対して線形緩和を行い2次の緩和問題を生成する。その問題に対して新たな2分岐ルールに基づく分枝限定法を適用する方法を考案し，先行研究手法（Carlsson and Shi）に対する優位性の検証を行った。数値結果より，最適解に対する解精度はもちろん，CPU時間，繰り返し回数，平均枝数などにおいても先行研究を大きく凌駕していることを明らかにした。
●提案する分枝限定法では，低次元SOLR問題を包括的に解くために新たな分岐メカニズムを採用している。本メカニズムでは，もし現在のベストを含む長方形領域が2 つのサブ長方形領域に分割された場合，現在の最良解が両方のサブ領域に属するような分岐を行う。数値実験では，異なる分岐ルールを使用した場合との比較を行い変数p ³ 30の場合において良好な平均CPU時間において解導出可能であることを示した。また，pの増加に伴いCPU時間減少率はさらに増加することも明らかにした。
●低次元SOLR問題に対してDIRECT法の適用についても検討を行った。数値結果から高い確率（99。99%）かつ少ない計算時間で解けることを確認することができた。