×

New approaches for heuristic search: A bilateral linkage with artificial intelligence. (English) Zbl 0658.90079

This survey considers emerging approaches of heuristic search for solutions to combinatorially complex problems. Such problems arise in business applications, of traditional interest to operations research, such as in manufacturing operations, financial investment, capital budgeting and resource management. Artificial intelligence is a revived approach to problem-solving that requires heuristic search intrinsically in knowledge-base operations, especially for logical and analogical reasoning mechanisms. Thus, one bilateral linkage between operations research and artificial intelligence is their common interest in solving hard problems with heuristic search. That is the focus here. But longstanding methods of directed tree search with classical problem heuristics, such as for the Traveling Salesman Problem - a paradigm for combinatorially difficult problems - are not wholly satisfactory. Thus, new approaches are needed, and it is at least stimulating that some of these are inspired by natural phenomena.

MSC:

90C27 Combinatorial optimization
65K05 Numerical mathematical programming methods
68P10 Searching and sorting
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
68T99 Artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ackley, D. H., A connectionist algorithm for genetic search, (Technical Report (1987), Department of Computer Science, Carnegie-Mellon University: Department of Computer Science, Carnegie-Mellon University Pittsburgh, PA) · Zbl 0684.68095
[2] Bonomi, E.; Lutton, J.-L., The \(N\)-city travelling salesman problem: Statistical mechanics and the metropolis algorithm, SIAM Review, 26, 551-568 (1984) · Zbl 0551.90095
[3] Cerny, V., Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, Journal of Optimization Theory and Applications, 45, 41-52 (1985) · Zbl 0534.90091
[4] Crowston, W. B.; Glover, F.; Thompson, G. L.; Trawick, J. D., Probabilistic and parametric learning combinations of local job shop scheduling rules, (ONR Research Memorandum No. 117 (1963), GSIA, Carnegie-Mellon University: GSIA, Carnegie-Mellon University Pittsburg, PA)
[5] Farlow, S., Self-Organizing Methods in Modelling: GMDH Type Algorithms (1984), Marcel Dekker: Marcel Dekker New York · Zbl 0559.00029
[6] Galliant, S. I., Connectionist expert systems, Communicatins of ACM, 31, 152-169 (1988)
[7] Geman, S.; Hwang, C.-R., Diffusions for global optimization, (Technical Report (1983), Brown University: Brown University Providence, RI) · Zbl 0602.60071
[8] Glover, F., Heuristics for integer programming using surrogate constraints, Decision Sciences, 8, 156-166 (1977)
[9] Glover, F., Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, 13, 533-549 (1986) · Zbl 0615.90083
[10] Glover, F., Tabu search, (Technical Report (1987), Center for Applied Artificial Intelligence, University of Colorado: Center for Applied Artificial Intelligence, University of Colorado Boulder, CO) · Zbl 0930.90083
[11] Glover, F.; Klingman, D.; Phillips, N. V., A network-related nuclear power plant model with an intelligent branch-and-bound solution approach, (Technical Report CBDA 139 (1988), University of Texas: University of Texas Austin, TX) · Zbl 0704.90054
[12] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning (1988), Addison-Wesley
[13] Goldberg, D. E.; Lingle, R., Alleles, loci, and the traveling salesman problem, (Technical Report (1987), Department of Engineering Mechanics, The University of Alabama: Department of Engineering Mechanics, The University of Alabama University, AL) · Zbl 0674.90095
[14] Greenberg, H. J., Foundations for an intelligent mathematical programming system, (Technical Report (1988), University of Colorado at Denver: University of Colorado at Denver Denver, CO) · Zbl 0159.48701
[15] Greenberg, H. J., Learning networks, (Final Report of Mathematics Clinic for Spring 1988 (1988), University of Colorado at Denver: University of Colorado at Denver Denver, CO)
[16] Grefenstette, J., Optimization of control parameters for genetic algorithms, IEEE Transactions on Systems, Man, and Cybernetics, 16, 122-128 (1986)
[17] Grefenstette, J.; Gopal, R.; Rosmaita, B.; Van Gucht, D., Genetic algorithms for the traveling salesman problem, (Proceedings of the International Conference on Genetic Algorithms and Their Applications (1985)) · Zbl 0674.90096
[18] Gutzmann, K. M., Combinatorial optimization using a continuous state Boltzmann machine, (Proceedings of IEEE International Conference on Neural Networks, Vol. III (1987)), 721-733, (June)
[19] Hansen, P., The steepest ascent mildest descent heuristic for combinatorial programming, (presented at the Congress on Numerical Methods in Combinatorial Optimization. presented at the Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy (1986))
[20] Hansen, P.; Jaumard, B., Algorithms for the maximum satisfiability problem, (RUTCOR Research Report RR# 43-87 (1987), Rutgers: Rutgers New Brunswick, NJ) · Zbl 0716.68077
[21] Hertz, A.; Werra, D.de, Using tabu search techniques for graph coloring, Computing, 39, 345-351 (1987) · Zbl 0626.68051
[22] Hertz, A.; Werra, D.de; Widmer, M., Some new applications of tabu search, (presented at the 13th International Symposium on Mathematical Programming. presented at the 13th International Symposium on Mathematical Programming, Tokyo, Japan (1988))
[23] Hicklin, J., Application of the genetic algorithm to neural network design, (Technical Report (1987), Laguna Research Laboratory: Laguna Research Laboratory Fallbrook, CA)
[24] Holland, J. H., Adaptation in natural and artificial systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor, MI · Zbl 0317.68006
[25] Hopfield, J. J.; Tank, D. W., Neural computation of decisions in optimization problems, Biological Cybernetics, 52, 141-152 (1985) · Zbl 0572.68041
[26] Hansen, P.; Jaumard, B., Algorithms for the maximum satisfiability problem, (RUTCOR Research Report RR # 43-87 (1987), Rutgers University: Rutgers University New Brunswick, NJ) · Zbl 0716.68077
[27] Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[28] Kohonen, T., Self-Organization and Associative Memory (1987), Springer: Springer Berlin · Zbl 0528.68062
[29] McCulloch, W. S.; Pitts, W., A logical calculus of the ideas immanent in nervous activity, Bulletin of Mathematical Biophysics, 5, 115-133 (1943) · Zbl 0063.03860
[30] McEliece, R. J.; Posner, E. C.; Rodemich, E. R.; Venkatesh, S. S., The capacity of the Hopfield associative memory, IEEE Transactions on Information Theory, 33, 461-482 (1987) · Zbl 0631.94016
[31] Oliver, I. M.; Smith, D. J.; Holland, J. R.C., A study of permutation crossover operators on the traveling salesman problem, (Technical Report (1987), Texas Instruments Ltd: Texas Instruments Ltd Dallas, TX)
[32] Omohundro, S. M., Efficient algorithms with neural network behavior, (Technical Report (1987), Department of Computer Science, University of Illinois: Department of Computer Science, University of Illinois Urbana-Champaign, IL) · Zbl 0659.68101
[33] Rosenblatt, F., Principles of Neurodynamics (1962), Spartan: Spartan Washington, DC · Zbl 0143.43504
[34] Rumelhart, D. E.; McClelland, J. L., (Parallel Distributed Processing, Explorations in the Microstructure of Cognition, Volume 1: Foundations (1986), MIT Press: MIT Press Cambridge, MA)
[35] Tank, D. W.; Hopfield, J. J., Simple optimization networks: An A/D converter and a linear programming circuit, IEEE Transactions on Circuits And Systems, 33, 533-541 (1986)
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.