A dual simplex algorithm for the canonical representation of the uncapacitated facility location problem
- 31 October 1989
- journal article
- Published by Elsevier BV in Operations Research Letters
- Vol. 8 (5), 279-286
- https://doi.org/10.1016/0167-6377(89)90054-0
Abstract
A number of algorithms have been designed for uncapacitated facility location problems. Computational experience with standard data sets seems to indicate the superiority of dual approaches, best known through efficient subgradient or dual adjustment procedures. However, linear programming algorithms provide distinct advantages, in particular direct amenability to cutting-plane techniques. A streamlined dual simplex algorithm is designed based on a covering formulation of the problem and present computational results.Keywords
This publication has 18 references indexed in Scilit:
- Simplex pivots on the set packing polytopeMathematical Programming, 1985
- A Maximum Expected Covering Location Model: Formulation, Properties and Heuristic SolutionTransportation Science, 1983
- A Primal Approach to the Simple Plant Location ProblemSIAM Journal on Algebraic Discrete Methods, 1982
- A Canonical Representation of Simple Plant Location Problems and Its ApplicationsSIAM Journal on Algebraic Discrete Methods, 1980
- A direct dual method for the mixed plant location problem with some side constraintsMathematical Programming, 1979
- A Dual-Based Procedure for Uncapacitated Facility LocationOperations Research, 1978
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate AlgorithmsManagement Science, 1977
- Algorithms for Exploiting the Structure of the Simple Plant Location ProblemPublished by Elsevier BV ,1977
- A New Algorithm for Locating Sources Among DestinationsManagement Science, 1973
- On the Set-Covering ProblemOperations Research, 1972