Equivalent Mathematical Programming Formulations of Monotonic Tree Network Location Problems

E. Erkut, R. L. Francis, T. J. Lowe and A. Tamir
Additional contact information
E. Erkut: University of Alberta, Edmonton, Canada
R. L. Francis: University of Florida, Gainesville, Florida
T. J. Lowe: Purdue University, West Lafayette, Indiana
A. Tamir: New York University, New York and Tel Aviv University, Tel Aviv, Israel

Operations Research, 1989, vol. 37, issue 3, 447-461

Abstract: We consider the optimization problem of locating several new facilities on a tree network, with respect to existing facilities, and to each other. The new facilities are not restricted to be at vertices of the network, but the locations are subject to constraints. Each constraint function, and the objective function, is an arbitrary, nondecreasing function of any finite collection of tree distances between new and existing facilities, and/or between distinct pairs of new facilities, and represents some sort of transport or travel cost. The new facilities are to be located so as to minimize the objective function subject to upper bounds on the constraint functions. We show that such problems are equivalent to mathematical programming problems which, when each function is expressed using only maximization and summation operations on nonnegatively weighted arguments, are linear programming problems of polynomial dimensions. The latter problems can be solved using duality theory with special purpose column generation and shortest path algorithms for column pricing.

Keywords: facilities/equipment planning: location problems; networks/graphs; applications: network location problems; programming: linear programming applications (search for similar items in EconPapers)
Date: 1989
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.37.3.447 (application/pdf)

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:inm:oropre:v:37:y:1989:i:3:p:447-461

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().