情報処理学会 第74回全国大会講演要旨

本研究では，頂点容量制約付き有向全域木パッキング問題を扱う．
この問題は入力として， 有向グラフ，ルート頂点，頂点容量，
辺の始点側と終点側それぞれに消費量が与えられる．
目的はルート頂点に流入する有向全域木のパッキング回数を
最大化することである．ただし，有向全域木の各頂点に対する
消費量の合計は，頂点容量を超えてはいけない．
以前，我々はこの問題に対して2段階の発見的解法を提案した．
このアルゴリズムは，1段階目に木の候補を生成し，
2段階目に木のパッキング回数を決定する．本研究では，
ラグランジュ緩和を用いることで1段階目を改善した．計算実験により，
提案アルゴリズムは以前のアルゴリズムより速く木を生成でき，
少ない木の候補でもよい解を得ることを確認した．