首页 | 本学科首页   官方微博 | 高级检索  
     


Steiner tree packing revisited
Authors:Nam-D?ng Hoàng  Thorsten Koch
Affiliation:1. Faculty of Mathematics, Mechanics, and Informatics, Vietnam National University, 334 Nguyen Trai Str., Hanoi, Vietnam
2. Zuse Institute Berlin, Takustr. 7, 14195, Berlin, Germany
Abstract:The Steiner tree packing problem (STPP) in graphs is a long studied problem in combinatorial optimization. In contrast to many other problems, where there have been tremendous advances in practical problem solving, STPP remains very difficult. Most heuristics schemes are ineffective and even finding feasible solutions is already NP-hard. What makes this problem special is that in order to reach the overall optimal solution non-optimal solutions to the underlying NP-hard Steiner tree problems must be used. Any non-global approach to the STPP is likely to fail. Integer programming is currently the best approach for computing optimal solutions. In this paper we review some ??classical?? STPP instances which model the underlying real world application only in a reduced form. Through improved modelling, including some new cutting planes, and by employing recent advances in solver technology we are for the first time able to solve those instances in the original 3D grid graphs to optimimality.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号