離散凸解析アプローチに基づく非線形整数計画問題の実用的解法の研究
【研究分野】数学一般(含確率論・統計数学)
【研究キーワード】
組合せ最適化 / 非線形関数 / 整数計画 / 離散凸関数 / 近似解法 / アルゴリズム / マトロイド / 劣モジュラ関数 / 非線形計画 / 凸解析 / 凸関数 / 離散凸解析
【研究成果の概要】
整数計画問題とは,与えられた制約条件を満たす整数ベクトルの中から,与えられた目的関数を最小化(または最大化)する解を求める問題である.一般に整数計画問題は短時間で解くことが困難である,ということが理論的にも現実的にも知られている.とくに,目的関数と条件が非線形関数で与えられる非線形整数計画問題は,解くことが最も困難な整数計画のクラスである.本研究では,様々な非線形整数計画問題に対して,その良質な近似解を短時間で求めるアルゴリズムを提案した.
【研究代表者】
【研究種目】若手研究(B)
【研究期間】2006 - 2008
【配分額】3,760千円 (直接経費: 3,400千円、間接経費: 360千円)