Branch and Win: OR tree search algorithms for solving combinatorial optimisation problems. (English) Zbl 1148.90339
Summary: Currently, most combinatorial optimisation problems have to be solved, if the optimum solution is sought, using general techniques to explore the space of feasible solutions and, more specifically, through exploratory enumerative procedures in trees and search graphs. We propose branch and win, a general formulation for understanding and synthesising the different tree search procedures that have been presented in the literature of operations research as well as in that of artificial intelligence. Several general ideas are also presented, whose application allows designing new hybrid search algorithms, in order to implement the procedure.
MSC:
| 90C27 | Combinatorial optimization |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
References:
| [1] | Barr A. and Feigenbaum E.A. (eds) (1981).The Handbook of Artificial Intelligence (Volume 1). Kaufmann. · Zbl 0509.68087 |
| [2] | Bockmayr A. and Kasper T. (1998). Branch and Infer: A Unifying Framework for Integer and Finite Domain Constraint Programming.INFORMS Journal on Computing 10, 287–300. · Zbl 1034.90517 · doi:10.1287/ijoc.10.3.287 |
| [3] | Brailsford S.C., Potts C.N. and Smith B.M. (1999). Constraint Satisfaction Problems: Algorithms and Applications.European Journal of Operational Research 119, 557–581. · Zbl 0938.90055 · doi:10.1016/S0377-2217(98)00364-6 |
| [4] | Companys R. (1975). Programación Combinatoria: Aplicación a la Ordenación de Trabajos en un Ordenador con Sistema Operativo en Discos.Symposia Mathematica XV, 83–107. |
| [5] | Corominas A. and Companys R. (1977). Procedimiento Generalizado de Branch and Bound.Qüestiió 1, 49–62. |
| [6] | Corrêa R. (1995). A Parallel Formulation for General Branch-and-Bound Algorithms.Lecture Notes in Computer Science 980, 395–409. |
| [7] | Goldengorin B., Ghosh D. and Sierksma G. (2004). Branch and Peg Algorithms for the Simple Plant Location Problem.Computers and Operations Research 31, 241–255. · Zbl 1087.90039 · doi:10.1016/S0305-0548(02)00190-9 |
| [8] | Greenberg H.J. (1996). Artificial Intelligence. In: Gass S.I. and Harris C.M. (eds),The Encyclopedia of Operations Research and Management Science. Kluwer Academic Publishers, 25–28. |
| [9] | Haralick R. and Elliott G. (1980). Increasing Tree Search Efficiency for Constraint Satisfaction Problems.Artificial Intelligence 14, 263–313. · doi:10.1016/0004-3702(80)90051-X |
| [10] | Hart P.E., Nilsson N.J. and Raphael B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths.IEEE Transactions on System Science and Cybernetics SSC-4, 100–107. · doi:10.1109/TSSC.1968.300136 |
| [11] | Helman P. (1989). A Common Schema for Dynamic Programming and Branch and Bound Algorithms.Journal of the Association for Computing Machinery 36, 97–128. · Zbl 0676.68058 |
| [12] | Hoffman K.L. and Padberg M. (1993). Solving Airline Crew Scheduling Problems by Branch-and-Cut.Management Science 39, 657–682. · Zbl 0783.90051 · doi:10.1287/mnsc.39.6.657 |
| [13] | Ibaraki T. (1988). Enumerative Approaches to Combinatorial Optimization, part I and II.Annals of Operations Research 10 and 11. · Zbl 0667.90068 |
| [14] | Korf R.E. (1990). Search. In: Shapiro S.C. (ed),Encyclopedia of Artificial Intelligence. John Wiley, 994–998. |
| [15] | Kumar V. and Kanal L. (1983a). A General Branch and Bound Formulation for Understanding and Synthesising And/Or Tree Search Procedures.Artificial Intelligence 21, 179–198. · Zbl 0507.68062 · doi:10.1016/S0004-3702(83)80009-5 |
| [16] | Kumar V. and Kanal L. (1983b). The Composite Decision Process: a Unifying Formulation for Heuristic Search, Dynamic Programming and Branch and Bound Procedures.Proceedings of the Third National Conference on Artificial Intelligence, 220–224. |
| [17] | Marsten R.E. and Morin T.L. (1978). A Hybrid Approach to Discrete Mathematical Programming.Mathematical Programming 14, 21–40. · Zbl 0388.90055 · doi:10.1007/BF01588949 |
| [18] | Nau D.S., Kumar V. and Kanal L. (1984). General Branch and Bound, and its Relation to A* and AO*.Artificial Intelligence 23, 29–58. · Zbl 0537.68064 · doi:10.1016/0004-3702(84)90004-3 |
| [19] | Nilsson N.J. (1971).Problem-Solving Methods in Artificial Intelligence. McGraw-Hill. |
| [20] | Nilsson N.J. (1980).Principles of Artificial Intelligence. Kaufmann. · Zbl 0422.68039 |
| [21] | Pastor R. (1999).Metalgoritmo de Optimización Combinatoria Mediante la Exploración de Grafos. Ph.D. Dissertation, Technology University of Catalonia. |
| [22] | Pastor R. and Corominas A. (2000). Strategies of Node Selection in Search Procedures for Solving Combinatorial Optimization Problems: A Survey and a General Formalization programming.Top 8, 111–134. · Zbl 0969.65052 · doi:10.1007/BF02564831 |
| [23] | Pearl J. (1984).Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley. |
| [24] | Rich E. and Knight K. (1991).Artificial Intelligence. McGraw-Hill. |
| [25] | Ryoo H.S. and Sahinidis N.V. (1996). A Branch-and-Reduce Approach to Global Optimization.Journal of Global Optimization 8, 107–139. · Zbl 0856.90103 · doi:10.1007/BF00138689 |
| [26] | Savelsbergh M. (1997). A Branch-and-Price Algorithm for the Generalized Assignment Problem.Operations Research 45, 831–841. · Zbl 0895.90161 · doi:10.1287/opre.45.6.831 |
| [27] | Tuy H. and Horst R. (1988). Convergence and Restart in Branch-and-Bound Algorithms for Global Optimization. Application to Concave Minimization and D.C. Optimization Problems.Mathematical Programming 41, 161–183. · Zbl 0651.90063 · doi:10.1007/BF01580762 |
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.
