Heuristic concentration: Two stage solution construction. (English) Zbl 0923.90107
Summary: By utilizing information from multiple runs of an interchange heuristic we construct a new solution that is generally better than the best local optimum previously found. This new, two stage, approach to combinatorial optimization is demonstrated in the context of the \(p\)-median problem. Two layers of optimization are superimposed. The first layer is a conventional heuristic the second is a heuristic or exact procedure which draws on the concentrated solution set generated by the initial heuristic. The intention is to provide an alternative heuristic procedure which, when dealing with large problems, has a higher probability of producing optimal solutions than existing methods. The procedure is fairly general and appears to be applicable to combinatorial problems in a number of contexts.
Software:
CPLEXReferences:
| [1] | Balinski, M., Integer Programming: Methods, Uses and Computations, Management Science, 12, 253-313 (1965) · Zbl 0129.12004 |
| [2] | Church, R. L.; ReVelle, C. S., Theoretical and Computational Links Between the p-Median, Location Set-covering, and the Maximal Covering Location Problem, Geographical Analysis, 8, 406-415 (1976) |
| [3] | Cornuejols, G.; Fisher, M. L.; Nemhauser, G. L., Location of Bank Accounts to Optimize Float: An Analytic Study of Exact ad Approximate Algorithms, Management Science, 23, 789-810 (1977) · Zbl 0361.90034 |
| [4] | CPLEX, Using the CPLEX Callable Library (1994), CPLEX Optimization, Inc: CPLEX Optimization, Inc Incline Village, NV |
| [5] | Densham, P. J.; Rushton, G., Strategies for Solving Large Location-Allocation Problems by Heuristic Methods, Environment and Planning, Series A, 24, 289-304 (1992) |
| [6] | Densham, P. J.; Rushton, G., A More Efficient Heuristic for Solving Large P-Median Problems, Papers in Regional Science, 71, 307-329 (1992) |
| [7] | Goodchild, M. F.; Noronha, V., Location-Allocation for Small Computers, (Monograph No. 8 (1983), Department of Geography, University of Iowa: Department of Geography, University of Iowa Iowa City, Iowa) |
| [8] | Hakimi, S. L., Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph, Operations Research, 12, 450-459 (1964) · Zbl 0123.00305 |
| [9] | Hakimi, S. L., Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems, Operations Research, 13, 462-475 (1965) · Zbl 0135.20501 |
| [10] | Hillsman, E. L., The p-Median Structure as a Unified Linear Model for Location-Allocation Analysis, Environment and Planning, Series A, 16, 305-318 (1984) |
| [11] | Hodgson, M.J., Rosing, K.E. and Storrier, A.L.G. (forthcoming). “Applying the Flow-Capturing Location-Allocation Model an Authentic Network: Edmonton, Canada.” European Journal of Operational Research; Hodgson, M.J., Rosing, K.E. and Storrier, A.L.G. (forthcoming). “Applying the Flow-Capturing Location-Allocation Model an Authentic Network: Edmonton, Canada.” European Journal of Operational Research · Zbl 0907.90129 |
| [12] | Mors, J. D., On the Extent to Which Certain FixedCharge Depot Location Problems can be Solved by LP., Journal of the Operational Research Society, 29, 71-76 (1978) |
| [13] | Pirlot, M., General Local Search Heuristics in Combinatorial Optimization: a Tutorial, Belgian Journal of Operations Research, Statistics and Computer Science, 32, 7-67 (1992) · Zbl 0768.90062 |
| [14] | ReVelle, C. S.; Swain, R., Central Facilities Location, Geographical Analysis, 2, 30-42 (1970) |
| [15] | ReVelle, C. S., Facility Siting and Integer-Friendly Programming, European Journal of Operational Research, 65, 147-158 (1993) · Zbl 0776.90047 |
| [16] | Rosing, K.E. (forthcoming).“An Empirical Investigation of the Power of a Vertex Substitution Heuristic.” Environment and Planning, B; Rosing, K.E. (forthcoming).“An Empirical Investigation of the Power of a Vertex Substitution Heuristic.” Environment and Planning, B |
| [17] | Rosing, K. E.; Hillsman, E. L.; Rosing-Vogelaar, H., A Note Comparing Optimal and Heuristic Solutions to the p-Median Problem, Geographical Analysis, 11, 86-89 (1979) |
| [18] | Rosing, K. E.; Hillsman, E. L.; Rosing-Vogelaar, H., The Robustness of two Common Heuristics for the \(p\)-Median Problem, Environment and Planning A, 11, 373-380 (1979) |
| [19] | Rosing, K. E.; ReVelle, C. S.; Rosing-Vogelaar, H., The p-Median and its Linear Programming Relaxation: An Approach to Large Problems, Journal of the Operational Research Society, 30, 815-823 (1979) · Zbl 0422.90049 |
| [20] | Rosing, K. E.; Van Dijk, J. J., Estimating the Probability of Heuristic Improvement: A Large Scale Application of Extreme Value Theory, Studies in Locational Analysis, 4, 301-304 (1993) |
| [21] | Teitz, M. B.; Bart, P., Heuristic Methods for Estimating the Generalized Vertex Median of a Weighted Graph, Operations Research, 16, 955-961 (1968) · Zbl 0165.22804 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
