大会名称
2009年 情報科学技術フォーラム(FIT)
大会コ-ド
F
開催年
2009
発行日
2009/8/20
セッション番号
4A
セッション名
最適化
講演日
2009/09/03
講演場所(会議室等)
A会場(9号館1F 911教室)
講演番号
RA-004
タイトル
An LP-Based Heuristic Algorithm for the Node Capacitated In-tree Packing Problem
著者名
田中 勇真佐々木 美裕柳浦 睦憲
キーワード
wireless ad hoc network, sensor network, LP-relaxation, delayed column generation, relaxation heuristics
抄録
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.
本文pdf
PDF download (169.4KB)