Optimal Network Problem: A Branch-and-Bound Algorithm

D E Boyce, A Farhi and R Weischedel
Additional contact information
D E Boyce: Regional Science Department, University of Pennsylvania, Philadelphia, Pennsylvania 19104, USA
A Farhi: SESAME, 48 Boulevard de Latour Maubourg, 75-Paris, France
R Weischedel: Moore School of Electrical Engineering, University of Pennsylvania, Philadelphia, Pennsylvania 19104, USA

Environment and Planning A, 1973, vol. 5, issue 4, 519-533

Abstract: The problem of selecting a subset of links so as to minimize the sum of shortest path distances between all pairs of nodes, subject to a budget constraint on total length of links, may be solved by a modification of a branch-and-bound algorithm developed for optimal variable selection problems in statistics. The modified algorithm is described in detail, and encouraging computational experience on 10 node networks is reported. The use of the algorithm as a heuristic approach to solving the optimal network problem is also discussed.

Date: 1973
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://journals.sagepub.com/doi/10.1068/a050519 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:envira:v:5:y:1973:i:4:p:519-533

DOI: 10.1068/a050519

Access Statistics for this article

More articles in Environment and Planning A
Bibliographic data for series maintained by SAGE Publications ().