非線形制約をもつ整数計画問題に対する理論保証付き近似解法の開発
【研究分野】情報学基礎
【研究キーワード】
整数計画問題 / 非線形関数 / アルゴリズム / 離散最適化 / 離散凸解析 / 非線形計画問題 / 近似アルゴリズム / 離散凸関数 / 組合せ最適化
【研究成果の概要】
本研究では,非線形な不等式制約の下で非線形関数を最大化するという整数計画問題に対し,解の精度および計算時間に関する理論的な保証を与える近似解法を開発することを目指した.本研究の主結果として,ナップサック制約の下で1つのM凹関数を最大化するという問題に対し,制約が複数個の場合でも,連続緩和アプローチを用いて任意の精度の近似解を多項式時間で求められることを示した.また,目的関数が2つのM凹関数の和の場合には,ラグランジュ緩和アプローチを用いて任意の精度の近似解が得られることを示した.
【研究代表者】
【研究種目】基盤研究(C)
【研究期間】2012-04-01 - 2016-03-31
【配分額】5,330千円 (直接経費: 4,100千円、間接経費: 1,230千円)