LAGRANGIAN-BASED COLUMN GENERATION FOR THE NODE CAPACITATED IN-TREE PACKING PROBLEM(<Special Issue>SCOPE (Seminar on Computation and OPtimization for new Extensions))

DOI Web Site Web Site 参考文献24件

書誌事項

タイトル別名
  • LAGRANGIAN-BASED COLUMN GENERATION 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 is to find a subset of rooted spanning in-trees and their packing numbers, where the packing number of an in-tree is the number of times it is packed, so as to maximize the sum of packing numbers under the constraint that the total consumption of the packed in-trees at each node does not exceed the capacity of the node. This problem is known to be NP-hard. Previously, we proposed a two-phase heuristic algorithm for this problem. The algorithm generates promising candidate in-trees to be packed in the first phase and computes the packing number of each in-tree in the second phase. In this paper, we improve the first phase algorithm by using Lagrangian relaxation instead of LP (linear programming) relaxation. We conducted computational experiments on graphs used in related papers and on randomly generated instances. The results indicate that our new algorithm generates in-trees faster than our previous algorithm and obtains better solutions than existing algorithms without generating many in-trees.

収録刊行物

参考文献 (24)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ