2024-03-28T23:02:37Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000621262023-04-27T10:00:04Z01164:02592:05623:05682
A Heuristic Algorithm for the Node Ccapacitated In-tree Packing Problem頂点容量制約付き有向全域木パッキング問題に対する近似解法enghttp://id.nii.ac.jp/1001/00062126/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=62126&item_no=1&attribute_id=1&file_no=1Copyright (c) 2009 by the Information Processing Society of Japan名古屋大学南山大学名古屋大学田中, 勇真佐々木, 美裕柳浦, 睦憲本論文では,頂点容量制約付き有向全域木パッキング問題に対する近似解法を提案する.この問題では入力として,有向グラフ,ルート頂点,頂点容量,辺の始点側と終点側にそれぞれ消費量が与えられる.目的は, ルート頂点に流入する有向全域木のパッキング回数を最大化することである.ただし,有向全域木の各頂点に対する消費量の合計は,与えられた頂点容量を超えてはいけない.この問題は NP 困難であることが知られている.提案手法ではこの問題を,(1) パッキングに用いる木の候補を探す,(2) それぞれの木に対してパッキング回数を決定する,という 2 つの段階に分けて考えている.前者に対しては,整数計画問題として定式化した後に,その線形緩和問題に対して列生成法を適用する.後者に対しては,線形緩和問題の解を修正したものに貪欲アルゴリズムを適用することを考案した.既存研究で用いられているグラフと,ランダムに生成したグラフに対して計算実験を行い,提案したアルゴリズムの効果について比較検討を行った.その結果,既存研究より良い結果が得られ,提案アルゴリズムがうまく動作していることを確認した.In this paper, we deal with the node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function and edge consumption functions for heads and tails. The problem consists of finding the maximum number of rooted in-trees such that the total consumption of the in-trees at each node does not exceed the capacity of the node. This problem is known to be NP-hard. We propose a two-phase heuristic algorithm for this problem. In the first phase, it generates candidate in-trees to be packed. The node capacitated in-tree packing problem can be formulated as an IP (integer programming) problem, and the proposed algorithm employs the delayed column generation method for the LP (linear programming)-relaxation problem of the IP to generate promising candidate in-trees. In the second phase, the algorithm computes the packing number of each in-tree. Our algorithm solves this second-phase problem by first modifying feasible solutions of the LP-relaxation problem and then improving them with a greedy algorithm. We conducted computational experiments on graphs used in related papers and on randomly generated graphs. The results indicate that our algorithm has a better performance than other existing methods.AN1009593X研究報告アルゴリズム(AL)2009-AL-12410192009-05-042009-08-19