Efficient primal-dual heuristic for a dynamic location problem

Joana Dias, M. Eugenia Captivo and Joao Climaco
Computers & Operations Research
Volume 34, Issue 6, June 2007, Pages 1800-1823
http://dx.doi.org/10.1016/j.cor.2005.07.005

Dynamic location problem (動的施設配置問題) という問題を考察している．
これは普通の施設配置問題に時間の要素が入ったもので，施設を開いたり閉じたり，また開いたり，といったことができる．
そのときの総費用最小化を考える．
これに対して整数計画問題としての定式化を行ない，主双対法に基づく発見的解法を与えている．
またそれに基づいた分枝限定アルゴリズムも提案しランダムに生成したインスタンスに対する実験を行なっている．
主双対アルゴリズムの近似比の解析は行なっていないようで，個人的には気になる．
(誰か一緒にやってくださる方いますか？)