1C3 A HEURISTIC ALGORITHM FOR THE NODE CAPACITATED IN-TREE PACKING PROBLEM

概要

論文の詳細を見る
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.
一般社団法人日本機械学会の論文
2009-07-04