✦ LIBER ✦

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

✍ Scribed by Suhl, Uwe H.; Hilbert, Heinrich

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 163 KB
Volume: 31
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199807)31:4<273::aid-net7>3.0.co;2-a

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

A branch and cut algorithm for the Stein

A branch and cut algorithm for the Steiner problem in graphs

✍ Lucena, A.; Beasley, J. E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB 👁 2 views

In this paper, we consider the Steiner problem in graphs, which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph with nonnegative edge costs. We use the formulation of this problem as a shortest spanning tree (SST) problem with additional constraint

A branch-and-cut algorithm for solving a

A branch-and-cut algorithm for solving an intraring synchronous optical network design problem

✍ Lee, Youngho; Sherali, Hanif D.; Han, Junghee; Kim, Seong-in 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 133 KB 👁 2 views

In this paper, we deal with a network design problem arising from the deployment of synchronous optical networks (SONET), a standard of transmission using optical fiber technology. The problem is to find an optimal clustering of traffic demands in the network such that the total number of node assig

Solving Steiner tree problems in graphs

Solving Steiner tree problems in graphs to optimality

✍ Koch, T.; Martin, A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB 👁 1 views

In this paper, we present the implementation of a branch-and-cut algorithm for solving Steiner tree problems in graphs. Our algorithm is based on an integer programming formulation for directed graphs and comprises preprocessing, separation algorithms, and primal heuristics. We are able to solve nea

A branch-and-cut algorithm for the undir

A branch-and-cut algorithm for the undirected selective traveling salesman problem

✍ Gendreau, Michel; Laporte, Gilbert; Semet, Fr�d�ric 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB 👁 2 views

The Selective Traveling Salesman Problem (STSP) is defined on a graph in which profits are associated with vertices and costs are associated with edges. Some vertices are compulsory. The aim is to construct a tour of maximal profit including all compulsory vertices and whose cost does not exceed a p

A branch-and-cut algorithm for the resou

A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem

✍ Fischetti, Matteo; Vigo, Daniele 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 2 views

In this paper, we present a branch-and-cut algorithm for the exact solution of an NP-hard extension of the well-known Minimum-Weight Arborescence (MWA) problem, in which resource constraints for each node are considered. This Resource-Constrained Minimum-Weight Arborescence (RMWA) problem arises, e.