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

概要

論文の詳細を見る
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.