EFFICIENT MODULAR IMPLEMENTATION OF BRANCH-AND-BOUND ALGORITHMS *
dc.contributor.author | Johnson, Roger Vivian | en_US |
dc.date.accessioned | 2010-06-01T22:33:26Z | |
dc.date.available | 2010-06-01T22:33:26Z | |
dc.date.issued | 1988-03 | en_US |
dc.identifier.citation | Johnson, Roger V. (1988). "EFFICIENT MODULAR IMPLEMENTATION OF BRANCH-AND-BOUND ALGORITHMS * ." Decision Sciences 19(1): 17-38. <http://hdl.handle.net/2027.42/75538> | en_US |
dc.identifier.issn | 0011-7315 | en_US |
dc.identifier.issn | 1540-5915 | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/75538 | |
dc.description.abstract | This paper demonstrates how branch-and-bound algorithms can be modularized to obtain implementation efficiencies. For the manager, this advantage can be used to obtain faster implementation of algorithm results; for the scientist, it allows efficiencies in the construction of similar algorithms with different search and addressing structures for the purpose of testing to find a preferred algorithm. The demonstration in part is achieved by showing how the computer code of a central module of logic can be transported between different algorithms that have the same search strategy. Modularizations of three common searches (the best-bound search and two variants of the last-in-first-out search) with two addressing methods are detailed and contrasted. Using four assembly line balancing algorithms as examples, modularization is demonstrated and the search and addressing methods are contrasted. The application potential of modularization is broad and includes linear programming-based integer programming. Benefits and disadvantages of modularization are discussed. Computational results demonstrate the viability of the method. | en_US |
dc.format.extent | 1042989 bytes | |
dc.format.extent | 3109 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.publisher | Blackwell Publishing Ltd | en_US |
dc.rights | 1988 by the American Institute for Decision Sciences | en_US |
dc.subject.other | Discrete Programming | en_US |
dc.subject.other | Line Balancing | en_US |
dc.subject.other | Mathematical Programming | en_US |
dc.subject.other | Search Theory. | en_US |
dc.title | EFFICIENT MODULAR IMPLEMENTATION OF BRANCH-AND-BOUND ALGORITHMS * | en_US |
dc.type | Article | en_US |
dc.subject.hlbsecondlevel | Computer Science | en_US |
dc.subject.hlbsecondlevel | Mathematics | en_US |
dc.subject.hlbtoplevel | Science | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | School of Business Administration, University of Michigan, Ann Arbor, MI 48109-1234 | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/75538/1/j.1540-5915.1988.tb00251.x.pdf | |
dc.identifier.doi | 10.1111/j.1540-5915.1988.tb00251.x | en_US |
dc.identifier.source | Decision Sciences | en_US |
dc.identifier.citedreference | Balas, E. An additive algorithm for solving linear programs with zero-one variables. Operations Research, 1965, 13, 517 – 546. | en_US |
dc.identifier.citedreference | Charlton, J. M., & Death, C. C. A general method for machine scheduling. International Journal of Production Research, 1969, 7 ( 3 ), 207 – 217. | en_US |
dc.identifier.citedreference | Dakin, R. J. A tree-search algorithm for mixed integer programming problems. The Computer Journal, 1965, 8 ( 3 ), 250 – 255. | en_US |
dc.identifier.citedreference | Fox, B. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Schrage, L. E. Branching from the largest upper bound: Folklore and facts. European Journal of Operational Research, 1978, 2, 191 – 194. | en_US |
dc.identifier.citedreference | Graves, J. S. On the storage and handling of binary data using FORTRAN with applications to integer programming. Operations Research, 1979, 27, 534 – 547. | en_US |
dc.identifier.citedreference | Greenberg, H., & Hegerich, R. L. A branch search algorithm for the knapsack problem. Management Science, 1970, 16, 327 – 332. | en_US |
dc.identifier.citedreference | Johnson, R. V. Assembly line balancing algorithms: Computational comparisons. International Journal of Production Research, 1981, 19 ( 3 ), 277 – 287. | en_US |
dc.identifier.citedreference | Johnson, R. V. A branch and bound algorithm for assembly line balancing problems with formulation irregularities. Management Science, 1983, 29, 1309 – 1324. | en_US |
dc.identifier.citedreference | Johnson, R. V. Balancing large assembly lines with FABLE. Management Science, in press. | en_US |
dc.identifier.citedreference | Land, A. H., & Doig, A. G. An automatic method of solving discrete programming problems. Econometrica, 1960, 28, 497 – 520. | en_US |
dc.identifier.citedreference | Little, J. D. C., Murty, K. G., Sweeney, D. W., & Karel, C. An algorithm for the traveling salesman problem. Operations Research, 1966, 11, 972 – 989. | en_US |
dc.identifier.citedreference | Salverson, M. E. The assembly line balancing problem. Journal of Industrial Engineering, 1955, 6 ( 3 ), 18 – 25. | en_US |
dc.identifier.citedreference | Talbot, F. B. Resource-constrained project scheduling with time-resource tradeoffs: The nonpreemptive case. Management Science, 1982, 28, 1197 – 1210. | en_US |
dc.identifier.citedreference | Talbot, F. B., & Patterson, J. H. An integer programming algorithm with network cuts for solving the assembly line balancing problem. Management Science, 1984, 30, 85 – 99. | en_US |
dc.identifier.citedreference | Talbot, F. B., Patterson, J. H., & Gehrlein, W. V. A comparative evaluation of heuristic line balancing techniques. Management Science, 1986, 32, 430 – 454. | en_US |
dc.identifier.citedreference | Wee, T. S., & Magazine, M. J. An efficient branch and bound algorith—Part 1: Minimize the number of work stations (Working Paper No. 151). Unpublished manuscript, University of Waterloo, 1981. | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.