二変数整数計画問題の幾何学的解法
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,二変数整数計画問題を解くアルゴリズムの一つを提案する.今回のアルゴリズムではまずはじめに与えられた実行可能領域をいくつかの三角形領域に分割する.そして最適解が存在すると思われる三角形領域から順に図形を小さくして解を求める手法を用いずにこれを求める.それによってn個の制約条件式からなる問題をO(nlogn+KlogL)の手間で解くことができる.但し,Kは分割した三角形領域の中で実際に最適解を探索したものの個数であり,K=O(n)である.そしてLは与えられた問題中で最も絶対値の大きい数である.
- 一般社団法人情報処理学会の論文
- 1993-11-25