Implementations --------------- Parallel Branch and Bound has been implemented in OSL which is available for clusters of workstations (RS/6000 or Sun) and uses Express or PVM for communication. This is a commercial package available form IBM. Note on Bibliographies ---------------------- Bibliographies are part bibtex, part freeform. They appear just as they were sent to me; I didn't have time to reformat. Bibliography (0-1 Knapsack Specific) ------------ @article(kn:Ferreira91, author="Ferreira AG", title="A {P}arallel {T}ime/{H}ardware {T}radeoff for the {K}napsack {P}roblem", journal="IEEE Transactions on Computers", volume="40", number="2", pages="221-225", month="February", year="1991" ) @article{A008:Lee, author = {J. Lee and E. Shragowitz and S. Sahni}, journal = {Journal of Parallel and Distributed Computing}, number = {5}, pages = {438-456}, title = {A Hypercube Algorithm for the 0/1 Knapsack Problem}, year = {1988 } } @article{A006:Lin, author = {J. Lin and J. A. Storer}, journal = {Journal of Parallel and Distributed Computing}, pages = {332-337}, title = {Processor-Efficient Hypercube Algorithms for the Knapsack Problem}, volume = {11}, year = {1991 } } @conference{multi-knapsack-problem, author = {G. Plateau and C. Roucairol and I. Valabregue}, title = {Algorithm {PR2} for the Parallel Size Reduction of the 0.1 MultiKnapsack problem}, booktitle = {INRIA Rapports de Recherche}, month = Mar, year = 1988, number = 811, location = {MAG Lab papers, number 89}, topic = {B\&B}, reffedby = {sar} } @article{A007:Teng, author = {S. Teng}, journal = {Journal of Parallel and Distributed Computing}, pages = {400-406}, title = {Adaptive Parallel algorithms for integral knapsack problems}, volume = {8}, year = {1990 } } General Bibliography -------------------- @inproceedings{A037:Abdelrahman, author = {T. S. Abdelrahman and T. N. Mudge}, booktitle = {Proceedings of the 1988 ACM Conference on Lisp and Functional Pr ogramming}, journal = {unknown (ACM)}, pages = {1492-1499}, publisher = {ACM Press}, title = {Parallel Branch and Bound Algorithms on Hypercube Multiprocessors}, year = {1988 } } @article{AKL82ieeepami, TITLE = "Design and Implementation of a parallel tree search algorithm", AUTHOR = "S. G. Akl and D. T. Bernard and R. J. Jordan", JOURNAL = "IEEE Transactions on Pattern Analysis and Machine Intelligence", VOLUME = "PAMI-4", YEAR = "1982", PAGES = "192-203" } @inproceedings{ARVINDAM90frontiers, AUTHOR = "S. Arvindam and Vipin Kumar and V. Nageshwara Rao", TITLE = "Efficient Parallel Algorithms for Search Problems: Applications in VLSI CAD", BOOKTITLE = "Proceedings of the Frontiers 90 Conference on Massively Par allel Computation", YEAR = "October 1990" } @inproceedings{BHATTACHARYA89ijcai, AUTHOR = "Subir Bhattacharya and A. Bagchi", TITLE = "Searching game trees in parallel using SSS", BOOKTITLE = "Proceedings of the eleventh International Joint Conference on Artificial Intelligence", YEAR = "1989", PAGES = "42-47" } Boehning, Butler and Gillet, A parallel integer LP Algorithm, Euro. Jl. of O.R., 34 (1988), 393-398 @techreport{boffey-paper, author = {T. B. Boffey and P. Saeidi}, title = {Parallel Branch-and-Bound Using Shared Memory}, institution = {SCM Dept. University of Liverpool}, year = 1991, type = {Technical Report}, location = {MAG Lab papers, number 182}, topic = {B\&B}, reffedby = {sar} } @conference{anomalies-paper, author = {F. W. Burton and G. P. McKeown and V. J. Rayward-Smith and M. R. Sleep}, title = {Parallel Processing and Combinatorial Optimisation}, booktitle = {Proceedings of the Combinatorial Optimisation III Confe rence}, year = 1982, address = {Stirling, Great Britain}, pages = {19-36}, editor = {L. B. Wilson and C. S. Edwards and V. J. Rayward-Smith} , location = {}, topic = {B\&B}, reffedby = {sar} } @techreport{clausen2, author = {J. Clausen and J. L. Tr\"aff}, title = {Parallel Graph Partitioning using Branch-and-Bound with Dynamic Distribution of Subproblems}, institution = {Institute of Datalogy, University of Copenhagen}, year = 1988, type = {Research Report}, number = {88/13}, address = {Copenhagen}, location = {MAG Lab papers, number 170}, topic = {B\&B}, reffedby = {sar} } @article{graph-partitioning, author = {J. Clausen and J. L. Tr\"aff}, title = {Implementation of Parallel Branch-and-Bound Algorithms --- Experiences with the Graph Partitioning Problem}, journal = {Annals of Operations Research}, year = 1991, annote = {IN PRESS}, location = {MAG Lab papers, number 150}, topic = {B\&B}, reffedby = {sar} } @article{A009:deBruin, author = {A. de Bruin and A. H. G. Rinnooy Kan and H. W. J. M. Trienekens}, journal = {Mathematical Programming}, number = {42}, pages = {245-271}, title = {A Simulation Tool for the Performance Evaluation of Parallel Branch and Bound Algorithms}, year = {1988 } } @incollection{DECHTER88springerbook, AUTHOR = "R. Dechter and J. Pearl", TITLE = "Network-Based Heuristics for Constraint Satisfaction Problems", EDITOR = "Laveen Kanal and Vipin Kumar", BOOKTITLE = "Search in Artificial Intelligence", PUBLISHER = "Springer-Verlag", ADDRESS = "New York", YEAR = "1988" } @inproceedings{HUANG89ijcai, AUTHOR = "Shie-rei Huang and Larry S. Davis", TITLE = "Parallel Iterative A* Search: An Admissible Distributed Heurist ic Search Algorithm", BOOKTITLE = "Proceedings of the eleventh International Joint Conference on Artificial Intelligence", YEAR = "1989", PAGES = "23-29" } @article{HUNTBACH88infoscience, author = "M. M. Huntbach and F. Warren Burton", title = "Alpha-beta Search on Virtual Tree Machines", journal = "Information Science", volume = "44, 3-17", year = 1988 } @inproceedings{A049:Felten, author = {E. W. Felten}, address = {New York, N.Y.}, booktitle = {The Third Conference on Hypercube Concurrent Computers and Appli cations}, editor = {G. Fox}, publisher = {Association for Computing Machinery}, title = {Best-First Branch-and-Bound on a Hypercube}, year = {1988} } @incollection{FREUDER88springerbook, AUTHOR = "E. Freuder", TITLE = "Backtrack-Free and Backtrack-bounded Search", EDITOR = "Laveen Kanal and Vipin Kumar", BOOKTITLE = "Search in Artificial Intelligence", PUBLISHER = "Springer-Verlag", ADDRESS = "New York", YEAR = "1988" } @inproceedings{U001:Gengler, author = {M. Gengler and G. Coray}, booktitle = {Parallel Processing: CONPAR 92 - VAPP V}, editor = {L. Boug\'{e} and M. Cosnard and Y. Robert and D. Trystram}, month = sep, pages = {515-526}, publisher = {Springer-Verlag}, series = {LNCS 634}, title = {A Parallel Best-first B\&B with Synchronization Phases}, year = {1992} } @article{A042:Ibaraki, author = {T. Ibaraki}, journal = {Onternational Journal of Computer and Information Sciences}, number = {4}, pages = {315-344}, title = {Theoretical Comparisons of Search Strategies in Branch-and-Bound Alg orithms}, volume = {5}, year = {1976} } @article{A043:Ibaraki, author = {T. Ibaraki}, journal = {Onternational Journal of Computer and Information Sciences}, number = {4}, pages = {315-343}, title = {Depth-{\em m} Search in Branch-and-Bound Algorithms}, volume = {7}, year = {1978} } @article{ibaraki-annals-of-or, author = {T. Ibaraki}, title = {Enumerative Approaches to Combinatorial Optimisation}, journal = {Annals of Operations Research}, volume = 11, number = {1--4}, month = Jan, year = 1988, location = {Chapter 9 in MAG Lab papers, number 152}, topic = {B\&B}, reffedby = {sar} } @inproceedings{KALE90aaai, AUTHOR = "Vikram Saletore and L. V. Kale", TITLE = "Consistent Linear Speedup to a First Solution in Parallel State -Space Search", BOOKTITLE = "Proceedings of the 1990 National Conference on Artificial Intelligence", PAGES = "227--233", YEAR = "August 1990" } @inproceedings{KANAL81, AUTHOR = "Kanal, L. and Kumar, V.", TITLE = "Branch and Bound Formulation for Sequential and Parallel Game T ree Searching : Preliminary Results", BOOKTITLE = "IJCAI" , YEAR = "1981", PAGES = "569-574" } A randomized parallel branch-and-bound procedure, R. Karp and Y. Zhang, Symp. on Theory of Computing, 1988, 290-300. @TECHREPORT{KARYPIS92tr-simd, Author = "George Karypis and Vipin Kumar", Title = "{Unstructured Tree Search on SIMD Parallel Computers}", Institution = "Computer Science Department, University of Minnesota", Year = {1992}, Number = {92--21}, note = "A short version of this paper appears in the Proceedings of Supercomputi ng 1992 Conference, November 1992" @article{A001:Kawaguchi, author = {T. Kawaguchi and T. Maeda}, journal = {Systems and Computers in Japan}, number = {3}, pages = {101-108}, title = {A Parallel Branch-and-Bound Algorithm for a Torus Machine}, volume = {21}, year = {1990 } } Kindervater, Trienekins (1986), Experiments with parallel algorithm for combinatorial problems, European Journal of Operations Research 33, (1988) 65-81 . G.A.P. Kindervater & J.K. Lenstra, "Parallel Computing in Combinatorial Optimization", Annals of Oper. Res. 14 (1988) pp. 245-289. @incollection{KORF88springerbook, AUTHOR = "Richard Korf", TITLE = "Optimal Path Finding Algorithms", EDITOR = "Laveen Kanal and Vipin Kumar", BOOKTITLE = "Search in Artificial Intelligence", PUBLISHER = "Springer-Verlag", ADDRESS = "New York", YEAR = "1988" / } @book{blackwells-book, author = {L. Kronsj\"o and D. Shumsheruddin}, title = {Advances in Parallel Algorithms}, publisher = {Blackwell Scientific Publications}, year = 1992, series = {Advanced Topics in Computer Science}, address = {Oxford}, topic = {Parallel}, reffedby = {sar} } @phdthesis{kumar-thesis, author = {V. Kumar}, title = {A Unified Approach to Problem Solving Search Procedures }, type = {PhD Thesis}, location = {MAG Papers, number 85}, topic = {B\&B}, reffedby = {sar} } @article{KUMAR81ijcai, AUTHOR = "Kanal, L.N. and Vipin Kumar", TITLE = "Branch-and-Bound Formulations for Sequential and Parallel Game Tree Searching", JOURNAL = "IJCAI" , YEAR = "1981", PAGES = "569-571" } @article{KUMAR83ai, AUTHOR = "Kumar, Vipin and Kanal, Laveen", TITLE = "A General Branch-and-Bound Formulations For Understanding and S ynthesizing And/Or Tree Search Procedures", JOURNAL = "Artificial Intelligence", YEAR = 1983, VOLUME = 21, PAGES = "179-198" } @article{KUMAR84pami, AUTHOR = "Kumar, Vipin and Kanal, Laveen", TITLE = "Parallel Branch-and-Bound Formulations For And/Or Tree Search", JOURNAL = "IEEE Trans. Pattern. Anal. and Machine Intell.", YEAR = 1984, VOLUME = "PAMI--6", PAGES = "768-778" } @incollection{KUMAR87encyc-bb, AUTHOR = "Vipin Kumar", TITLE = "BRANCH-AND-BOUND SEARCH", EDITOR = "Stuart C. Shapiro", BOOKTITLE = "Encyclopaedia of Artificial Intelligence: Vol 2", YEAR = "1987", PAGES = "1000-1004", PUBLISHER = "John Wiley and Sons, Inc.", ADDRESS = "New York", NOTE = "Revised version appears in the second edition 1992" } @incollection{KUMAR88general, AUTHOR = "Vipin Kumar and Dana Nau and Laveen Kanal", TITLE = "General Branch-and-bound Formulation for AND/OR Graph and Game T ree Search", EDITOR = "Laveen Kanal and Vipin Kumar", BOOKTITLE = "Search in Artificial Intelligence", PUBLISHER = "Springer-Verlag", ADDRESS = "New York", YEAR = "1988" } @incollection{KUMAR88cdp, AUTHOR = "Vipin Kumar and Laveen Kanal", TITLE = "The CDP: A Unifying Formulation for Heuristic Search, Dynamic Pr ogramming, and Branch-and-Bound", EDITOR = "Laveen Kanal and Vipin Kumar", BOOKTITLE = "Search in Artificial Intelligence", PUBLISHER = "Springer-Verlag", ADDRESS = "New York", YEAR = "1988" } @article{A016:Lai, author = {T-H. Lai and S. Sahni}, journal = {Comm. ACM}, pages = {594-602}, title = {Anomalies in parallel branch-and-bound algortithms}, volume = {27}, year = {1984 } } @article{performance-lai-sprague, author = {T. Lai and A. Sprague}, title = {Performance of Parallel Branch-and-Bound Algorithms}, journal = {IEEE Transactions on Computers}, volume = {C-34}, number = 10, pages = {962-964}, month = Oct, year = 1985, location = {MAG Lab papers, number 33}, topic = {B\&B}, reffedby = {sar} } @article{anomalies-lai-and-sprague, author = {T. Lai and A. Sprague}, title = {A Note on Anomalies in Parallel Branch-and-Bound Algori thms With One-to-One Bounding Functions}, journal = {Information Processing Letters}, volume = 23, pages = {119-122}, year = 1986, location = {MAG Lab papers, number 26}, topic = {B\&B}, reffedby = {sar} } @article{A047:Li, author = {G. Li and B. W. Wah}, journal = {IEEE Transactions on Computers}, month = jun, number = {6}, pages = {568-573}, title = {Coping with Anomalias in Parallel Branch-and-Bound Algorithms}, volume = {C-35}, year = {1986} } @inproceedings{A051:Li, author = {G. Li and B. W. Wah}, booktitle = {Proceedings of the 1986 International Conference on Parallel Pro cessing}, editor = {K. Hwang and S. M. Jacobs and E. E. Swartzlander}, pages = {992-999}, publisher = {IEEE Computer Society Press}, title = {How Good are Parallel and Ordered Depth-first Searches}, year = {1986} } R. Luling & B. Monien, "Two strategies for solving the Vertex Cover Problem on a Transputer network", Lecture Notes in Computer Science 392, Springer, pp. 160-170. @conference{transputing91, author = {G. P. McKeown and V. J. Rayward-Smith and S. A. Rush an d H. J. Turpin}, title = {Using a Transputer Network to Solve Branch-and-Bound Pr oblems}, booktitle = {Proceedings of the TRANSPUTING '91 Conference}, month = Apr, year = 1991, address = {California}, publisher = {IOS Press}, volume = {2}, pages = {781-800}, editor = {Welch, P. and Stiles, D. and Kunii, T.L. and Bakkers, A .}, location = {S.A.R or G.P.M}, topic = {B\&B}, reffedby = {sar} } @inbook{ios-book, author = {G. P. McKeown and V. J. Rayward-Smith and S. A. Rush}, title = {The Branch-and-Bound Paradigm Implemented on a Network of Transputers}, publisher = {IOS Press}, year = 1992, address = {Amsterdam, Holland}, crossref = {ios-book-book}, topic = {Parallel}, reffedby = {sar} } @inbook{blackwells, author = {G. P. McKeown and V. J. Rayward-Smith and S. A. Rush}, title = {Parallel Branch-and-Bound}, chapter = 5, pages = {111-150}, publisher = {Blackwell Scientific Publications}, year = 1992, series = {Advanced Topics in Computer Science}, address = {Oxford}, crossref = {blackwells-book}, topic = {Parallel}, reffedby = {sar} } @article{A028:Mitten, author = {L. G. Mitten}, journal = {Operations Research}, pages = {24-34}, title = {Branch-and-bound methods: General Formulation and Properties}, volume = {18}, year = {1970 } } @incollection{MONIEN89book, author = "B. Monien and R.Feldmann and P.Mysliwietz and O.Vornberger", title = "Parrallel game tree search by dynamic tree decomposition", EDITOR = "Vipin Kumar and P. S. Gopalakrishnan and Laveen Kanal", BOOKTITLE = "Parallel Algorithms for Machine Intelligence and Vision", PUBLISHER = "Springer-Verlag", ADDRESS = "New York", YEAR = "1990" } An algorithm for singly constrained quadratic problems, by Pardalos and Kovoor, Tech Report # CS-87-06, Dept. of CS, Penn State U., University Park, PA 16802. TITLE = "A parallel branch and bound algorithm for test generation ", AUTHOR = {S. Patil and P. Banerjee}, JOURNAL = {\em IEEE Transaction on Computer-Aided Design}, VOLUME = 9, MONTH = {March}, YEAR = { 1990}, PAGES = {313--322} } Pekny, J.F. and Miller, D.L. A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems. Mathematical Programming 55 (1992) p.17-33, north-Holland @article{A033:Quinn, author = {M. J. Quinn and N. Deo}, journal = BIT, number = {26}, pages = {35-43}, title = {An Upper Bound for the Speedup of Parallel Best-Bound Branch-and-Bou nd Algorithms}, year = {1986 } } @article(kn:Quinn90, author="Quinn MJ", title="Analysis and {I}mplementation of {B}ranch and {B}ound {A}lgorithms on a {H}ypercube {M}ulticomputer", journal="IEEE Transactions on Computers", volume="39", number="3", pages="384-387", month="March", year="1990" ) @article{A003:Rao, author = {V. Nageshwara Rao and Vipin Kumar}, journal = {International Journal of Parallel Programming}, number = {6}, title = {Parallel Depth First Search. Part I. Implementation.}, volume = {16}, year = {1987 } } @article{A004:Rao, author = {V. Nageshwara Rao and Vipin Kumar}, journal = {International Journal of Parallel Programming}, number = {6}, title = {Parallel Depth First Search. Part II. Analysis}, volume = {16}, year = {1987 } } @techreport{efficiency-paper, author = {V. J. Rayward-Smith and S. A. Rush and G. P. McKeown}, title = {Efficiency Considerations in the Implementation of Para llel Branch-and-Bound}, institution = {University of East Anglia}, year = 1991, type = {Internal Report}, address = {Norwich}, annote = {IN PRESS}, location = {MAG Lab}, topic = {B\&B}, reffedby = {sar} } @article{GPSA-paper, author = {V. J. Rayward-Smith and G. P. McKeown and F. W. Burton} , title = {The General Problem Solving Algorithm and Its Implement ation}, journal = {New Generation Computing}, volume = 6, pages = {41-66}, year = 1988, location = {MAG Lab papers, number 1}, topic = {General}, reffedby = {sar} } @book{ios-book-book, author = {G. L. Reijns}, title = {Transputing for Numerical and Neural Net Applications}, publisher = {IOS Press}, year = 1992, address = {Amsterdam, Holland}, topic = {Parallel}, reffedby = {sar} } Parallel B&B Algs for Quadratic 0-1 programming, by Rodgers and Pardalos, Tech Report # CS-88-17, Dept. of CS, Penn State U., University Park, PA 16802. C. Roucairol, "A parallel Branch and Bound alg. for the QAP", Disc. App. Math. 18 (1987) pp. 211-225. @phdthesis{sar-thesis, author = {S. A. Rush}, title = {Parallel Branch-and-Bound on a Network of Transputers}, school = {School of Information Systems}, year = {1992}, address = {University of East Anglia, Norwich, NR4 7TJ , England}, reffedby = {sar} } @article{A025:Schwan, author = {K. Schwan and B. Blake and W. Bo and J. Gawkowski}, journal = {Concurrency: Practice and Experience}, month = dec, number = {2}, pages = {191-218}, title = {Global Data and Control in Multicomputers: Operating Systems Primiti ves and Experimentation with a Parallel Branch-and-Bound Algorithm}, volume = {1}, year = {1989 } } J. M. Troya, M. Ortega, "A study of parallel Branch and Bound algorithms with best bound first search", Parallel Computing 11 (1989) pp. 121-126. O. Vornberger, "Load balancing in a network of Transputers", Lecture Notes in Computer Science 312, Springer Verlag, pp. 116-126. @article{MANIP1, author = {B. W. Wah and Y. W. E. Ma}, title = {{MANIP} - A Multicomputer Architecture for Solving Comb inatorial Extremum-Search Problems}, journal = {IEEE Transactions on Computers}, volume = {C-33}, number = 5, pages = {377-390}, month = May, year = 1984, location = {MAG Lab papers, number 6}, topic = {B\&B}, reffedby = {sar} } @article{WAH85ieeecomputer, AUTHOR = "Benjamin W. Wah and G.J. Li and C. F. Yu", TITLE = "Multiprocessing of Combinatorial Search Problems", JOURNAL = "IEEE Computers", YEAR = "1985" , MONTH = "June 1985" } @article{A040:Wah, author = {B. W. Wah and C. F. Yu}, journal = {IEEE Transactions on Software Engineering}, month = sep, number = {0}, pages = {922-934}, title = {Stochastic Modeling of Branch-and-Bound Algorithms with Best-First S earch}, volume = {SE-11}, year = {1985} } G.A.P. Kindervater & J.K. Lenstra, "Parallel Computing in Combinatorial Optimization", Annals of Oper. Res. 14 (1988) pp. 245-289. @incollection{KORF88springerbook, AUTHOR = "Richard Korf", TITLE = "Optimal Path Finding Algorithms", EDITOR = "Laveen Kanal and Vipin Kumar", BOOKTITLE = "Search in Artificial Intelligence", PUBLISHER = "Springer-Verlag", ADDRESS = "New York", YEAR = "1988" / } @book{blackwells-book, author = {L. Kronsj\"o and D. Shumsheruddin}, title = {Advances in Parallel Algorithms}, publisher = {Blackwell Scientific Publications}, year = 1992, series = {Advanced Topics in Computer Science}, address = {Oxford}, topic = {Parallel}, reffedby = {sar} } @phdthesis{kumar-thesis, author = {V. Kumar}, title = {A Unified Approach to Problem Solving Search Procedures }, type = {PhD Thesis}, location = {MAG Papers, number 85}, topic = {B\&B}, reffedby = {sar} } @article{KUMAR81ijcai, AUTHOR = "Kanal, L.N. and Vipin Kumar", TITLE = "Branch-and-Bound Formulations for Sequential and Parallel Game Tree Searching", JOURNAL = "IJCAI" , YEAR = "1981", PAGES = "569-571" } @article{KUMAR83ai, AUTHOR = "Kumar, Vipin and Kanal, Laveen", TITLE = "A General Branch-and-Bound Formulations For Understanding and S ynthesizing And/Or Tree Search Procedures", JOURNAL = "Artificial Intelligence", YEAR = 1983, VOLUME = 21, PAGES = "179-198" } @article{KUMAR84pami, AUTHOR = "Kumar, Vipin and Kanal, Laveen", TITLE = "Parallel Branch-and-Bound Formulations For And/Or Tree Search", JOURNAL = "IEEE Trans. Pattern. Anal. and Machine Intell.", YEAR = 1984, VOLUME = "PAMI--6", PAGES = "768-778" } @incollection{KUMAR87encyc-bb, AUTHOR = "Vipin Kumar", TITLE = "BRANCH-AND-BOUND SEARCH", EDITOR = "Stuart C. Shapiro", BOOKTITLE = "Encyclopaedia of Artificial Intelligence: Vol 2", YEAR = "1987", PAGES = "1000-1004", PUBLISHER = "John Wiley and Sons, Inc.", ADDRESS = "New York", NOTE = "Revised version appears in the second edition 1992" } @incollection{KUMAR88general, AUTHOR = "Vipin Kumar and Dana Nau and Laveen Kanal", TITLE = "General Branch-and-bound Formulation for AND/OR Graph and Game T ree Search", EDITOR = "Laveen Kanal and Vipin Kumar", BOOKTITLE = "Search in Artificial Intelligence", PUBLISHER = "Springer-Verlag", ADDRESS = "New York", YEAR = "1988" } @incollection{KUMAR88cdp, AUTHOR = "Vipin Kumar and Laveen Kanal", TITLE = "The CDP: A Unifying Formulation for Heuristic Search, Dynamic Pr ogramming, and Branch-and-Bound", EDITOR = "Laveen Kanal and Vipin Kumar", BOOKTITLE = "Search in Artificial Intelligence", PUBLISHER = "Springer-Verlag", ADDRESS = "New York", YEAR = "1988" } @article{A016:Lai, author = {T-H. Lai and S. Sahni}, journal = {Comm. ACM}, pages = {594-602}, title = {Anomalies in parallel branch-and-bound algortithms}, volume = {27}, year = {1984 } } @article{performance-lai-sprague, author = {T. Lai and A. Sprague}, title = {Performance of Parallel Branch-and-Bound Algorithms}, journal = {IEEE Transactions on Computers}, volume = {C-34}, number = 10, pages = {962-964}, month = Oct, year = 1985, location = {MAG Lab papers, number 33}, topic = {B\&B}, reffedby = {sar} } @article{anomalies-lai-and-sprague, author = {T. Lai and A. Sprague}, title = {A Note on Anomalies in Parallel Branch-and-Bound Algori thms With One-to-One Bounding Functions}, journal = {Information Processing Letters}, volume = 23, pages = {119-122}, year = 1986, location = {MAG Lab papers, number 26}, topic = {B\&B}, reffedby = {sar} } @article{A047:Li, author = {G. Li and B. W. Wah}, journal = {IEEE Transactions on Computers}, month = jun, number = {6}, pages = {568-573}, title = {Coping with Anomalias in Parallel Branch-and-Bound Algorithms}, volume = {C-35}, year = {1986} } @inproceedings{A051:Li, author = {G. Li and B. W. Wah}, booktitle = {Proceedings of the 1986 International Conference on Parallel Pro cessing}, editor = {K. Hwang and S. M. Jacobs and E. E. Swartzlander}, pages = {992-999}, publisher = {IEEE Computer Society Press}, title = {How Good are Parallel and Ordered Depth-first Searches}, year = {1986} } R. Luling & B. Monien, "Two strategies for solving the Vertex Cover Problem on a Transputer network", Lecture Notes in Computer Science 392, Springer, pp. 160-170. @conference{transputing91, author = {G. P. McKeown and V. J. Rayward-Smith and S. A. Rush an d H. J. Turpin}, title = {Using a Transputer Network to Solve Branch-and-Bound Pr oblems}, booktitle = {Proceedings of the TRANSPUTING '91 Conference}, month = Apr, year = 1991, address = {California}, publisher = {IOS Press}, volume = {2}, pages = {781-800}, editor = {Welch, P. and Stiles, D. and Kunii, T.L. and Bakkers, A .}, location = {S.A.R or G.P.M}, topic = {B\&B}, reffedby = {sar} } @inbook{ios-book, author = {G. P. McKeown and V. J. Rayward-Smith and S. A. Rush}, title = {The Branch-and-Bound Paradigm Implemented on a Network of Transputers}, publisher = {IOS Press}, year = 1992, address = {Amsterdam, Holland}, crossref = {ios-book-book}, topic = {Parallel}, reffedby = {sar} } @inbook{blackwells, author = {G. P. McKeown and V. J. Rayward-Smith and S. A. Rush}, title = {Parallel Branch-and-Bound}, chapter = 5, pages = {111-150}, publisher = {Blackwell Scientific Publications}, year = 1992, series = {Advanced Topics in Computer Science}, address = {Oxford}, crossref = {blackwells-book}, topic = {Parallel}, reffedby = {sar} } @article{A028:Mitten, author = {L. G. Mitten}, journal = {Operations Research}, pages = {24-34}, title = {Branch-and-bound methods: General Formulation and Properties}, volume = {18}, year = {1970 } } @incollection{MONIEN89book, author = "B. Monien and R.Feldmann and P.Mysliwietz and O.Vornberger", title = "Parrallel game tree search by dynamic tree decomposition", EDITOR = "Vipin Kumar and P. S. Gopalakrishnan and Laveen Kanal", BOOKTITLE = "Parallel Algorithms for Machine Intelligence and Vision", PUBLISHER = "Springer-Verlag", ADDRESS = "New York", YEAR = "1990" } An algorithm for singly constrained quadratic problems, by Pardalos and Kovoor, Tech Report # CS-87-06, Dept. of CS, Penn State U., University Park, PA 16802. TITLE = "A parallel branch and bound algorithm for test generation ", AUTHOR = {S. Patil and P. Banerjee}, JOURNAL = {\em IEEE Transaction on Computer-Aided Design}, VOLUME = 9, MONTH = {March}, YEAR = { 1990}, PAGES = {313--322} } Pekny, J.F. and Miller, D.L. A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems. Mathematical Programming 55 (1992) p.17-33, north-Holland @article{A033:Quinn, author = {M. J. Quinn and N. Deo}, journal = BIT, number = {26}, pages = {35-43}, title = {An Upper Bound for the Speedup of Parallel Best-Bound Branch-and-Bou nd Algorithms}, year = {1986 } } @article(kn:Quinn90, author="Quinn MJ", title="Analysis and {I}mplementation of {B}ranch and {B}ound {A}lgorithms on a {H}ypercube {M}ulticomputer", journal="IEEE Transactions on Computers", volume="39", number="3", pages="384-387", month="March", year="1990" ) @article{A003:Rao, author = {V. Nageshwara Rao and Vipin Kumar}, journal = {International Journal of Parallel Programming}, number = {6}, title = {Parallel Depth First Search. Part I. Implementation.}, volume = {16}, year = {1987 } } @article{A004:Rao, author = {V. Nageshwara Rao and Vipin Kumar}, journal = {International Journal of Parallel Programming}, number = {6}, title = {Parallel Depth First Search. Part II. Analysis}, volume = {16}, year = {1987 } } @techreport{efficiency-paper, author = {V. J. Rayward-Smith and S. A. Rush and G. P. McKeown}, title = {Efficiency Considerations in the Implementation of Para llel Branch-and-Bound}, institution = {University of East Anglia}, year = 1991, type = {Internal Report}, address = {Norwich}, annote = {IN PRESS}, location = {MAG Lab}, topic = {B\&B}, reffedby = {sar} } @article{GPSA-paper, author = {V. J. Rayward-Smith and G. P. McKeown and F. W. Burton} , title = {The General Problem Solving Algorithm and Its Implement ation}, journal = {New Generation Computing}, volume = 6, pages = {41-66}, year = 1988, location = {MAG Lab papers, number 1}, topic = {General}, reffedby = {sar} } @book{ios-book-book, author = {G. L. Reijns}, title = {Transputing for Numerical and Neural Net Applications}, publisher = {IOS Press}, year = 1992, address = {Amsterdam, Holland}, topic = {Parallel}, reffedby = {sar} } Parallel B&B Algs for Quadratic 0-1 programming, by Rodgers and Pardalos, Tech Report # CS-88-17, Dept. of CS, Penn State U., University Park, PA 16802. C. Roucairol, "A parallel Branch and Bound alg. for the QAP", Disc. App. Math. 18 (1987) pp. 211-225. @phdthesis{sar-thesis, author = {S. A. Rush}, title = {Parallel Branch-and-Bound on a Network of Transputers}, school = {School of Information Systems}, year = {1992}, address = {University of East Anglia, Norwich, NR4 7TJ , England}, reffedby = {sar} } @article{A025:Schwan, author = {K. Schwan and B. Blake and W. Bo and J. Gawkowski}, journal = {Concurrency: Practice and Experience}, month = dec, number = {2}, pages = {191-218}, title = {Global Data and Control in Multicomputers: Operating Systems Primiti ves and Experimentation with a Parallel Branch-and-Bound Algorithm}, volume = {1}, year = {1989 } } J. M. Troya, M. Ortega, "A study of parallel Branch and Bound algorithms with best bound first search", Parallel Computing 11 (1989) pp. 121-126. O. Vornberger, "Load balancing in a network of Transputers", Lecture Notes in Computer Science 312, Springer Verlag, pp. 116-126. @article{MANIP1, author = {B. W. Wah and Y. W. E. Ma}, title = {{MANIP} - A Multicomputer Architecture for Solving Comb inatorial Extremum-Search Problems}, journal = {IEEE Transactions on Computers}, volume = {C-33}, number = 5, pages = {377-390}, month = May, year = 1984, location = {MAG Lab papers, number 6}, topic = {B\&B}, reffedby = {sar} } @article{WAH85ieeecomputer, AUTHOR = "Benjamin W. Wah and G.J. Li and C. F. Yu", TITLE = "Multiprocessing of Combinatorial Search Problems", JOURNAL = "IEEE Computers", YEAR = "1985" , MONTH = "June 1985" } @article{A040:Wah, author = {B. W. Wah and C. F. Yu}, journal = {IEEE Transactions on Software Engineering}, month = sep, number = {0}, pages = {922-934}, title = {Stochastic Modeling of Branch-and-Bound Algorithms with Best-First S earch}, volume = {SE-11}, year = {1985} }