Paper Info
Title
A branch-and-cut algorithm for solving generalized multiperiod Steiner problems in graphs
Abstract
Given is an undirected graph with positive or negative edge weights which represent a profit if an investment such as installing a gas pipe takes place in a given time period. A certain part of the graph may already be piped in previous periods. The task is to extend the piped subgraph in the most profitable way over a multiperiod time horizon. In addition, there may be general side constraints limiting the extensions per period. This problem is a generalization of the Steiner problem in graphs. It is shown that the general Steiner problem in graphs is equivalent to the node-weighted Steiner problem in graphs. A branch-and-cut algorithm is presented which is based on an integer programming formulation to solve the multiperiod Steiner problem in graphs. Numerical results with real-life problems of a gas utility company show that optimal solutions can be obtained in minutes of computer time on a fast PC. (C) 1998 John Wiley & Sons, Inc. Networks 31: 273-282, 1998.
Year
DOI
Venue
1998
10.1002/(SICI)1097-0037(199807)31:4<273::AID-NET7>3.0.CO;2-A
NETWORKS
Keywords
Field
DocType
integer programming,branch-and-cut,Steiner problem in graphs,node-weighted Steiner tree problem in graphs
Indifference graph,Time horizon,Steiner tree problem,Chordal graph,Integer programming,Longest path problem,Graph theory,Discrete mathematics,Mathematical optimization,Combinatorics,Branch and cut,Algorithm,Mathematics
Journal
Volume
Issue
ISSN
31
4
0028-3045
Citations 
PageRank 
References 
2
0.37
0
Authors
2
Name
Order
Citations
PageRank
Uwe H. Suhl111822.95
Heinrich Hilbert220.37