A branch‐and‐cut algorithm for solving generalized multiperiod Steiner problems in graphs

Journal Article


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. © 1998 John Wiley & Sons, Inc. Networks 31: 273–282, 1998

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.