大会名称 |
---|
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) |