-

 

 

 




Optimization Online





 

STRONG LOWER BOUNDS FOR THE PRIZE COLLECTING STEINER PROBLEM IN GRAPHS

Abilio Lucena (lucena***at***openlink.com.br)
Mauricio G. C. Resende (mgcr***at***research.att.com)

Abstract: Given an undirected graph G with nonnegative edges costs and nonnegative vertex penalties, the prize collecting Steiner problem in graphs (PCSPG) seeks a tree of G with minimum weight. The weight of a tree is the sum of its edge costs plus the sum of the penalties of those vertices not spanned by the tree. In this paper, we present an integer programming formulation of the PCSPG and describe an algorithm to obtain lower bounds for the problem. The algorithm is based on polyhedral cutting planes and is initiated with tests that attempt to reduce the size of the input graph. Computational experiments were carried out to evaluate the strength of the formulation through its linear programming relaxation. The algorithm found optimal solutions for 99 out of the 114 instances tested. On 96 instances, integer solutions were found (thus generating optimal PCSPG solutions). On all but seven instances, lower bounds were equal to best known upper bounds (thus proving optimality of the upper bounds). Of these seven instances, four lower bounds were off by 1 of the best known upper bound. Nine new best known upper bounds were produced for the test set.

Keywords: Prize collecting Steiner problem in graphs, network design, cutting planes, lower bound

Category 1: Combinatorial Optimization

Category 2: Network Optimization

Category 3: Applications -- OR and Management Sciences (Telecommunications )

Citation: AT&T Labs Research Technical Report, Florham Park, NJ 07932 USA, October 2002.

Download: [PDF]

Entry Submitted: 10/12/2002
Entry Accepted: 10/14/2002
Entry Last Modified: 10/12/2002

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society