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

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.