{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T06:05:38Z","timestamp":1747548338329},"publisher-location":"Berlin, Heidelberg","reference-count":65,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540610434"},{"type":"electronic","value":"9783540498759"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/bfb0027123","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T11:08:23Z","timestamp":1132398503000},"page":"201-231","source":"Crossref","is-referenced-by-count":13,"title":["Building a parallel branch and bound library"],"prefix":"10.1007","author":[{"given":"Mohamed","family":"Bena\u00efchouche","sequence":"first","affiliation":[]},{"given":"Van-Dat","family":"Cung","sequence":"additional","affiliation":[]},{"given":"Salah","family":"Dowaji","sequence":"additional","affiliation":[]},{"given":"Bertrand","family":"Le Cun","sequence":"additional","affiliation":[]},{"given":"Thierry","family":"Mautor","sequence":"additional","affiliation":[]},{"given":"Catherine","family":"Roucairol","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"9_CR1","unstructured":"J. Bitwas and J. Browne. Simultaneous update of priority structures. IEEE international conference on parallel computing, pages 124\u2013131, 1987."},{"key":"9_CR2","first-page":"393","volume":"34","author":"R. B\u0153hning","year":"1988","unstructured":"R. B\u0153hning, R. Butler, and B. Gillett. A parallel integer linear programming algorithm. (34):393\u2013398, 1988.","journal-title":"A parallel integer linear programming algorithm"},{"key":"9_CR3","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0207026","volume":"7","author":"M. Brown","year":"1978","unstructured":"M. Brown. Implementation and analysis of binomial queue algorithmms. SIAM Comput., 7:298\u2013319, 1978.","journal-title":"SIAM Comput."},{"key":"9_CR4","first-page":"19","volume-title":"Combinatorial Optimization III","author":"F. Burton","year":"1982","unstructured":"F. Burton, G. Mc Keown, V. Rayward-Smith, and M. Sleep. Parallel processing and combinatorial optimization. In L. Wilson, C. Edwards, and V. Rayward-Smith, editors, Combinatorial Optimization III, pages 19\u201336. University of Stirling, U.K., 1982."},{"key":"9_CR5","unstructured":"J. Calhoun and R. Ford. Concurrency control mechanisms and the serializability of concurrent tree algorithms. In of the 3rd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, Waterloo Ontario, Apr. 1984."},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BF02023053","volume":"22","author":"T. Cannon","year":"1990","unstructured":"T. Cannon and K. Hoffman. Large-scale 0\u20131 linear programming on distributed workstations. Annals of Opns Res., 22:181\u2013217, 1990.","journal-title":"Annals of Opns Res."},{"key":"9_CR7","volume-title":"PhD thesis","author":"V.-D. Cung","year":"1994","unstructured":"V.-D. Cung. Contribution \u00e0 l'Algorithmique Non Num\u00e9rique Parall\u00e8le: Exploration d'Espaces de Recherche. PhD thesis, Universit\u00e9 Pierre et Marie Curie-Paris VI, 4, Place Jussieu, 75252 Paris Cedex 05, FRANCE, Apr. 1994. In French."},{"key":"9_CR8","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/3-540-58078-6_14","volume":"number 805","author":"V.-D. Cung","year":"1994","unstructured":"V.-D. Cung and B. Le Cun. An efficient implementation of parallel a*. In Lecture Notes in Computer Science, Parallel and Distributed computing: Theory and Practice, Canada-France Conference on Parallel Computing, number 805, pages 153\u2013168, May 1994.","journal-title":"Lecture Notes in Computer Science, Parallel and Distributed computing: Theory and Practice, Canada-France Conference on Parallel Computing"},{"key":"9_CR9","unstructured":"V.-D. Cung and C. Roucairol. Parcours parall\u00e8le d'arbres minimax. RR 1549, INRIA, Nov. 1991. In French."},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"S. Das and W.-B. Horng. Managing a parallel heap efficiently. In Proc. PARLE'91-Parallel Architectures and Languages Europe, pages 270\u2013288, 1991.","DOI":"10.1007\/978-3-662-25209-3_19"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"N. Deo. Data structures for parallel computation on shared-memory machine. In SuperComputing, pages 341\u2013345, 1989.","DOI":"10.1007\/978-3-642-75771-6_23"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"N. Deo. Data structures for parallel computation on shared memory machines. In J. Kowalik, editor, Supercomputing 89, volume F62 of NATO ASI, pages 341\u2013345. Springer-Verlag, 1990.","DOI":"10.1007\/978-3-642-75771-6_23"},{"issue":"1","key":"9_CR13","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/BF00128644","volume":"6","author":"N. Deo","year":"1992","unstructured":"N. Deo and S. Prasad. Parallel heap: An optimal parallel priority queue. Journal of Supercomputing, 6(1):87\u201398, Mar. 1992.","journal-title":"Journal of Supercomputing"},{"key":"9_CR14","doi-asserted-by":"crossref","first-page":"818","DOI":"10.1109\/TC.1980.1675681","volume":"29","author":"O. E. Dessouki","year":"1980","unstructured":"O. E. Dessouki and W. Huen. Distributed enumeration on networks computers. IEEE Tans. on Comp., (29):818\u2013825, 1980.","journal-title":"IEEE Tans. on Comp."},{"key":"9_CR15","unstructured":"M. Diamond, C. Kimbel, and S. R. C.L. Rennolet. Pico: Parallel implementation of combinatorial optimization. In Workshop on Parallel Computing of Discrete Optimization Problems. University Minneapolis \u2014 AHPC, 1991."},{"key":"9_CR16","volume-title":"First european Parallel Virtual Machine (PVM) users group meeting, Euro-Pvm'94","author":"S. Dowaji","year":"1994","unstructured":"S. Dowaji and C. Roucairol. Priority of tasks and performances of branch-and-bound load balancing strategies. In First european Parallel Virtual Machine (PVM) users group meeting, Euro-Pvm'94, Rome, Italie, 9\u201311 Oct. 1994. University of Roma."},{"key":"9_CR17","unstructured":"J. Eckstein. Parallel branch-and-bound algorithms for general mixed integer programming. TMC 257, Thinking Machine Corporation, 1993."},{"key":"9_CR18","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF00289064","volume":"14","author":"C. Ellis","year":"1980","unstructured":"C. Ellis. Concurrent search and insertion in 2\u20133 trees. Acta Informatica, 14:63\u201386, 1980.","journal-title":"Acta Informatica"},{"issue":"9","key":"9_CR19","doi-asserted-by":"crossref","first-page":"811","DOI":"10.1109\/TC.1980.1675680","volume":"C-29","author":"C. Ellis","year":"1981","unstructured":"C. Ellis. Concurrent search and insertion in avl trees. IEEE Trans. on Cumputers, C-29(9):811\u2013817, Sept. 1981.","journal-title":"IEEE Trans. on Cumputers"},{"key":"9_CR20","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1145\/22719.24067","volume":"9","author":"R. Finkel","year":"1987","unstructured":"R. Finkel and U. Manber. Dib-a distributed implementation of backtracking. ACM Trans. Programming Lang. Syst., (9):235\u2013256, 1987.","journal-title":"ACM Trans. Programming Lang. Syst."},{"key":"9_CR21","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01840439","volume":"1","author":"M. Fredman","year":"1986","unstructured":"M. Fredman, R. Sedgewick, D. Sleator, and R. Tarjan. The pairing heap: A new form of self-adjusting heap. Algorithmica, 1:111\u2013129, 1986.","journal-title":"Algorithmica"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"M. Gengler and G. Coray. A parallel best first b&b with synchronization phases. In L. Boug\u00e9 et al., editor, Proceedings of CONPAR92, pages 515\u2013526. Springer-Verlag, 1992.","DOI":"10.1007\/3-540-55895-0_450"},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"Q. Huang. An evaluation of concurrent priority queue algorithms. In Third IEEE Symposium on Parallel and Distributed Processing, pages 518\u2013525, Dec. 1991.","DOI":"10.1109\/SPDP.1991.218255"},{"issue":"320","key":"9_CR24","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1145\/5684.5686","volume":"29","author":"D. Jones","year":"1986","unstructured":"D. Jones. An empirical comparaison of priority queue and event set implementation. Comm. ACM, 29(320):191\u2013194, Apr. 1986.","journal-title":"Comm. ACM"},{"issue":"1","key":"9_CR25","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1145\/63238.63249","volume":"32","author":"D. Jones","year":"1989","unstructured":"D. Jones. Concurrent operations on priority queues. ACM, 32(1):132\u2013137, Jan. 1989.","journal-title":"ACM"},{"issue":"4","key":"9_CR26","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/BF01379360","volume":"19","author":"L. Kal\u00e9","year":"1990","unstructured":"L. Kal\u00e9 and V. A. Saletore. Parallel state-space search for a first solution with consistent linear speedups. International Journal of Parallel Programming, 19(4):251\u2013293, 1990.","journal-title":"International Journal of Parallel Programming"},{"key":"9_CR27","unstructured":"D. Knuth. The Art of Programming: Sorting and Searching, volume 3. Addison-Wesley, 1973."},{"key":"9_CR28","unstructured":"G. Kudva and J. Pekny. Dcabb: A distributed control architecture for b&b computations. In ORSA\/TIMS Conference, Ph\u0153nix, 1993."},{"key":"9_CR29","doi-asserted-by":"crossref","unstructured":"V. Kumar and A. Gupta. Analyzing the scability of parallel algorithms and architectures. In International Conference on Supercomputing, 1991.","DOI":"10.1145\/109025.109118"},{"issue":"3","key":"9_CR30","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1145\/320613.320619","volume":"5","author":"H. Kung","year":"1980","unstructured":"H. Kung and P. Lehman. Concurrent manipulation of binary search trees. ACM trans. on Database Systems, 5(3):354\u2013382, 1980.","journal-title":"ACM trans. on Database Systems"},{"key":"9_CR31","doi-asserted-by":"crossref","unstructured":"T. Lai and S. Sahni. Anomalies in parallel branch and bound algorithms. Communication ACM, (27):594\u2013602.","DOI":"10.1145\/358080.358103"},{"key":"9_CR32","unstructured":"I. Lavall\u00e9e and C. Roucairol. A parallel b&b algorithm. Technical Report 164, LRI \u2014 Universit\u00e9 d'Orsay, 1984."},{"key":"9_CR33","unstructured":"B. Le Cun, B. Mans, and C. Roucairol. Op\u00e9rations concurrentes et files de priorit\u00e9. RR 1548, INRIA-Rocquencourt, 1991."},{"key":"9_CR34","unstructured":"B. Le Cun, B. Mans, and C. Roucairol. Comparison of concurrent priority queues for branch and bound algorithms. RR 92-65, MASI Universite Pierre et Marie Curie, 1992."},{"key":"9_CR35","volume-title":"the PNN team. Bob: a unified platform for implementing branch-and-bound like algorithms. RR 95\/16","author":"B. Cun Le","year":"1995","unstructured":"B. Le Cun, C. Roucairol, and the PNN team. Bob: a unified platform for implementing branch-and-bound like algorithms. RR 95\/16, Laboratoire PRiSM, Universit\u00e9 de Versailles-Saint Quentin en Yvelines, Sept. 1995."},{"issue":"4","key":"9_CR36","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1145\/319628.319663","volume":"6","author":"P. Lehman","year":"1981","unstructured":"P. Lehman and S. Yao. Efficient locking for concurrent operation on b-tree. ACM trans. on Database Systems, 6(4):650\u2013670, Dec. 1981.","journal-title":"ACM trans. on Database Systems"},{"key":"9_CR37","unstructured":"G. Li and B. Wah. Computational efficiency of parallel approximate branch and bound algorithms. In International Conference on Parallel Processing, pages 473\u2013480, 1984."},{"key":"9_CR38","doi-asserted-by":"crossref","unstructured":"R. Luling and B. Monien. Two strategies for solving the vertex cover problem on a transputer network. In Lecture Notes in Computer Science, number 392, pages 160\u2013170. Springer Verlag, 1989.","DOI":"10.1007\/3-540-51687-5_40"},{"issue":"3","key":"9_CR39","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1016\/0377-2217(93)E0334-T","volume":"81","author":"B. Mans","year":"1995","unstructured":"B. Mans, T. Mautor, and C. Roucairol. A parallel depth first search branch and bound algorithm for the quadratic assignment problem. EJOR European Journal of Operational Research, 81(3):617\u2013628, 1995.","journal-title":"EJOR European Journal of Operational Research"},{"key":"9_CR40","unstructured":"B. Mans and C. Roucairol. Concurrency in priority queues for branch and bound algorithms. Technical Report 1311, INRIA, 1990."},{"key":"9_CR41","unstructured":"B. Mans and C. Roucairol. Characterization of data structures for parallel branch and bound algorithms. In European Congress of Operation Research, EURO'XI, Aachen, Germany, 1991."},{"key":"9_CR42","unstructured":"B. Mans and C. Roucairol. Performances of parallel branch-and-bound algorithms with best first search. In I. Lavall\u00e9e and Y. Paker, editors, OPOPAC International Workshop on Principles of Parallel Computing, pages 121\u2013139. Herm\u00e8s, 1993."},{"key":"9_CR43","volume-title":"Th\u00e8se d'universit\u00e9","author":"T. Mautor","year":"1993","unstructured":"T. Mautor. Contribution \u00e0 la r\u00e9solution des probl\u00e8mes d'implantation: algorithmes s\u00e9quentiels et parall\u00e8les pour l'affectation quadratique. Th\u00e8se d'universit\u00e9, Universit\u00e9 Paris VI, 4, place Jussieu, 75252 Paris Cedex 05, Feb. 1993."},{"key":"9_CR44","doi-asserted-by":"crossref","unstructured":"T. Mautor and C. Roucairol. Difficulties of exact methods for solving the quadratic assignment problem. In P. M. Pardalos and H. Wolkowicz, editors, Quadratic Assignment and Related Problems, volume 16 of Discrete Mathematics and Theoretical Computer Science, pages 263\u2013274. DIMACS, American Mathematical Society, May 1994.","DOI":"10.1090\/dimacs\/016\/13"},{"key":"9_CR45","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0166-218X(94)90014-0","volume":"55","author":"T. Mautor","year":"1994","unstructured":"T. Mautor and C. Roucairol. A new exact algorithm for the solution of quadratic assignment problems. Discrete Applied Mathematics, (55):281\u2013293, 1994.","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"9_CR46","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"E. M. McCreight","year":"1985","unstructured":"E. M. McCreight. Priority search trees. SIAM J Computing, 14(2):257\u2013276, May 1985.","journal-title":"SIAM J Computing"},{"key":"9_CR47","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF02073942","volume":"33","author":"G. McKeown","year":"1991","unstructured":"G. McKeown, V. Rayward-Smith, and H. Turpin. Branch and bound as a higher order function. In Annals of Operations Research, volume 33, pages 379\u2013402. 1991.","journal-title":"Annals of Operations Research"},{"key":"9_CR48","unstructured":"P. Pardalos and G. Rodgers. In Impact of Recent Computer Advances on Operational Research, chapter Parallel Branch-and-Bound Algorithms for Unconstrained Quadratic Zero-one Programming. Elsevier Sc., 1989."},{"key":"9_CR49","first-page":"1514","volume":"II","author":"R. Pargas","year":"1988","unstructured":"R. Pargas and E. Wooster. Branch-and-bound algorithms on a hypercube. In Conference on Hypercube Concurrent computers and applications, volume II, pages 1514\u20131519, 1988.","journal-title":"Conference on Hypercube Concurrent computers and applications"},{"key":"9_CR50","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF01581188","volume":"55","author":"J. Pekny","year":"1990","unstructured":"J. Pekny and D. Miller. A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems. Mathematical Programming, 55:17\u201333, 1990.","journal-title":"Mathematical Programming"},{"key":"9_CR51","volume-title":"Master's thesis","author":"E. Pruul","year":"1975","unstructured":"E. Pruul. Parallel processing and a branch and bound algorithm. Master's thesis, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, N.Y., 1975."},{"key":"9_CR52","unstructured":"M. Quinn. Implementing best first branch and bound algorithm on hypercube multicomputers. In M. Health, editor, Hypercube Multiprocessors, pages 318\u2013326. SIAM Press, 1987."},{"key":"9_CR53","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0377-2217(91)90197-4","volume":"55","author":"S. K. R. Burkard","year":"1991","unstructured":"S. K. R. Burkard and F. Rendl. Qaplib \u2014 a quadratic assignment problem library. European Journal of Operational Research, (55):115\u2013119, 1991 (Updated version \u2014 Feb. 1994).","journal-title":"European Journal of Operational Research"},{"key":"9_CR54","unstructured":"V. Rao and V. Kumar. Concurrent insertions and deletions in a priority queue. IEEE proceedings of International Conference on Parallel Processing, pages 207\u2013211, 1988."},{"key":"9_CR55","first-page":"153","volume-title":"Parallel Branch and Bound Algorithms: an Overview","author":"C. Roucairol","year":"1988","unstructured":"C. Roucairol. In Parallel and Distributed Algorithms, chapter Parallel Branch and Bound Algorithms: an Overview, pages 153\u2013163. Elsevier Science Publishers, North-Holland, 1988."},{"key":"9_CR56","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0167-7977(89)90023-3","volume":"11","author":"C. Roucairol","year":"1989","unstructured":"C. Roucairol. Parallel computing in combinatorial optimization. Computer Physics Reports, 11:195\u2013220, 1989.","journal-title":"Computer Physics Reports"},{"key":"9_CR57","volume-title":"RR M.A.S.I. 90.4","author":"C. Roucairol","year":"1990","unstructured":"C. Roucairol. Recherche arborescente en parall\u00e8le. RR M.A.S.I. 90.4, Institut Blaise Pascal-Paris VI, 1990. In French."},{"key":"9_CR58","unstructured":"C. Roucairol. Parallel processing for difficult combinatorial optimization problems. In EURO'XIII. University of Glasgow, July 1994. Tutorial presented at Glasgow, to appear in EJOR 1995, also available as technical report RR-95\/04 PRiSM, University of Versailles."},{"key":"9_CR59","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0004-3702(91)90100-X","volume":"50","author":"U. K. Sarkar","year":"1991","unstructured":"U. K. Sarkar, P. P. Charkrabarti, S. Ghose, and S. C. D. Sarkar. Reducing reexpansions in iterative-deepening search by controlling cutoff bounds. Artificial Intelligence, (50):207\u2013221, 1991.","journal-title":"Artificial Intelligence"},{"key":"9_CR60","doi-asserted-by":"crossref","unstructured":"W. Shu and L. Kal\u00e9. A dynamic scheduling strategy for the chare kernel system. In Supercomputing 89, pages 389\u2013398, 1989.","DOI":"10.1145\/76263.76306"},{"key":"9_CR61","unstructured":"J. Stasko and J. Vitter. Pairing heap: Experiments and analysis. Technical Report 600, I.N.R.I.A., Feb. 1987."},{"issue":"3","key":"9_CR62","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"R. Tarjan","year":"1985","unstructured":"R. Tarjan and D. Sleator. Self-adjusting binary search trees. Journal of ACM, 32(3):652\u2013686, 1985.","journal-title":"Journal of ACM"},{"key":"9_CR63","volume-title":"Eur-cs-89-02","author":"H. Trienekens","year":"1989","unstructured":"H. Trienekens. Computational experiments with an asynchronous parallel branch and bound algorithm. Eur-cs-89-02, Computer Science Department, Faculty of Economics, Eramus University, Rotterdam, 1989."},{"issue":"5","key":"9_CR64","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1109\/TC.1984.1676453","volume":"C-33","author":"B. Wah","year":"1984","unstructured":"B. Wah and Y. Ma. Manip-a multicomputer architecture for solving combinatorial extremum search problems. IEEE Trans. on Comp., C-33(5):377\u2013390, 1984.","journal-title":"IEEE Trans. on Comp."},{"key":"9_CR65","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J. Williams","year":"1964","unstructured":"J. Williams. Algorithm 232: Heapsort. CACM, 7:347\u2013348, 1964.","journal-title":"CACM"}],"container-title":["Lecture Notes in Computer Science","Solving Combinatorial Optimization Problems in Parallel"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0027123","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,20]],"date-time":"2021-07-20T02:24:20Z","timestamp":1626747860000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0027123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540610434","9783540498759"],"references-count":65,"URL":"https:\/\/doi.org\/10.1007\/bfb0027123","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}