article

Free access

Anomalies in parallel branch-and-bound algorithms

Authors:

Sartaj SahniAuthors Info & Claims

Communications of the ACM, Volume 27, Issue 6

Pages 594 - 602

https://doi.org/10.1145/358080.358103

Published: 01 June 1984 Publication History

Abstract

We consider the effects of parallelizing branch-and-bound algorithms by expanding several live nodes simultaneously. It is shown that it is quite possible for a parallel branch-and-bound algorithm using n₂ processors to take more time than one using n₁ processors, even though n₁ < n₂. Furthermore, it is also possible to achieve speed-ups that are in excess of the ratio n₂/n₁. Experimental results with the 0/1-Knapsack and Traveling Salesman problems are also presented.

References

[1]

Agin, N. Optimum seeking with branch-and-bound. Manage. Sci. 13, pp. B176-B185.

Digital Library

[2]

Desai, B. The BPU, a staged parallel processing system to solve the zero-one problem. Proc. ICS '78, 1978, pp. 802-817.

[3]

Desai, B. A parallel microprocessing system. Proc. 1979 Int. Conf. Parallel Processing, 1979.

[4]

Desai, B. A parallel processing system to solve the 0-1 programming problem. Ph.D. dissertation, McGill University, Jan. 1977.

[5]

E1-Dessouki, O. and Huen, W. Distributed enumeration on network computers IEEE Trans. Computers C-29, 1980, pp. 818-825.

Digital Library

[6]

Fox, B., Lenstra, J., Rinnooy Kan, A. and Schrage, L. Branching from the largest upper bound: Folklore and fact. Europ. J. Op. Res. 2, 1978, pp. 191-194.

[7]

Graham, R. Bounds on multiprocessor timing anomalies. SIAM J. Applied Math. 17, 2, 1969, pp. 416-429.

[8]

Harris, J. and Smith, D. Hierarchical multiprocessor organizations. Proc. 4th Ann. Symp. Computer Architecture, 1977, pp. 41-48.

Digital Library

[9]

Held, M. and Karp, R. The traveling salesman problem and minimum spanning trees: Part II, Math. Prog. 1, 1971, pp. 6-25.

Digital Library

[10]

Horowitz. E. and Sahni. S. Fundamentals of Computer Algorithms. Computer Science Press, Inc., Bethesda, MD. 1978.

[11]

Ignall, E. and Schrage, L. Application of the branch-and-bound technique to some flow-shop scheduling problems. Oper. Res. 13, 1965, pp. 400-412.

Digital Library

[12]

Kohler, W. and Steiglitz, K. Enumerative and iterative computational approaches. In E. Coffman (ed.) Computer and Job-Shop Scheduling Theory, John Wiley and Sons, Inc., New York, 1976, pp. 229- 287.

[13]

Lawler, E. and Wood, D. Branch-and-bound methods: A survey. Oper. Res. 14, 1966, pp. 699-719.

Digital Library

[14]

Mitten, L. Branch-and-bound methods: General formulation and properties. Oper. Res. 18, 1970, pp. 24-34.

Digital Library

[15]

Nilson, N. Problem Solving Methods in Artificial Intelligence. McGraw- Hill, New York, 1971.

Digital Library

[16]

Wah, B. and Ma, Y. NANIP--A parallel computer system for implementing branch-and-bound algorithm. Proc. 8th Ann. Symp. Computer Architecture, 1982, pp. 239-262.

Digital Library

Cited By

Palkar PMahajan A(2022)Mitigating Anomalies in Parallel Branch-and-Bound Based Algorithms for Mixed-Integer Nonlinear OptimizationCombinatorial Optimization10.1007/978-3-031-18530-4_11(143-156)Online publication date: 18-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-18530-4_11
Quer SMarcelli ASquillero G(2020)The Maximum Common Subgraph Problem: A Parallel and Multi-Engine ApproachComputation10.3390/computation80200488:2(48)Online publication date: 18-May-2020
https://doi.org/10.3390/computation8020048
Kehrer SBlochinger W(2020)Equilibrium: an elasticity controller for parallel tree search in the cloudThe Journal of Supercomputing10.1007/s11227-020-03197-y76:11(9211-9245)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1007/s11227-020-03197-y
Show More Cited By

Recommendations

Experiments with parallel branch-and-bound algorithms for the set covering problem

We discuss the results of computational experiments using a new parallel multi-task model for integer optimization. The model is implemented in C on a BBN TC2000 computer. Eight branch-and-bound algorithms based on the use of two types of tasks, linear ...
Coping with anomalies in parallel branch-and-bound algorithms
The MIT Press scientific computation series

A general technique that can be used to solve a wide variety of discrete optimization problems is the branch-and-bound algorithm. We have adapted and extended branch-and-bound algorithms for parallel processing. The computational efficiency of these ...
Branch-and-bound algorithms for the partial inverse mixed integer linear programming problem

This paper presents branch-and-bound algorithms for the partial inverse mixed integer linear programming (PInvMILP) problem, which is to find a minimal perturbation to the objective function of a mixed integer linear program (MILP), measured by some ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 27, Issue 6

June 1984

78 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/358080

Editor:
Peter J. Denning
NASA Ames Research Center, Moffett Field, CA

Issue’s Table of Contents

Copyright © 1984 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1984

Published in CACM Volume 27, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

207
Total Citations
View Citations
997
Total Downloads

Downloads (Last 12 months)113
Downloads (Last 6 weeks)15

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Palkar PMahajan A(2022)Mitigating Anomalies in Parallel Branch-and-Bound Based Algorithms for Mixed-Integer Nonlinear OptimizationCombinatorial Optimization10.1007/978-3-031-18530-4_11(143-156)Online publication date: 18-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-18530-4_11
Quer SMarcelli ASquillero G(2020)The Maximum Common Subgraph Problem: A Parallel and Multi-Engine ApproachComputation10.3390/computation80200488:2(48)Online publication date: 18-May-2020
https://doi.org/10.3390/computation8020048
Kehrer SBlochinger W(2020)Equilibrium: an elasticity controller for parallel tree search in the cloudThe Journal of Supercomputing10.1007/s11227-020-03197-y76:11(9211-9245)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1007/s11227-020-03197-y
GENT IMIGUEL INIGHTINGALE PMCCREESH CPROSSER PMOORE NUNSWORTH C(2018)A review of literature on parallel constraint solvingTheory and Practice of Logic Programming10.1017/S147106841800034018:5-6(725-758)Online publication date: 2-Aug-2018
https://doi.org/10.1017/S1471068418000340
Archibald BMaier PMcCreesh CStewart RTrinder P(2018)Replicable parallel branch and bound searchJournal of Parallel and Distributed Computing10.1016/j.jpdc.2017.10.010113(92-114)Online publication date: Mar-2018
https://doi.org/10.1016/j.jpdc.2017.10.010
Hoffmann RMcCreesh CNdiaye SProsser PReilly CSolnon CTrimble J(2018)Observations from Parallelising Three Maximum Common (Connected) Subgraph AlgorithmsIntegration of Constraint Programming, Artificial Intelligence, and Operations Research10.1007/978-3-319-93031-2_22(298-315)Online publication date: 26-Jun-2018
https://dl.acm.org/doi/10.1007/978-3-319-93031-2_22
Barnat JBloemen VDuret-Lutz ALaarman APetrucci Lvan de Pol JRenault E(2018)Parallel Model Checking Algorithms for Linear-Time Temporal LogicHandbook of Parallel Constraint Reasoning10.1007/978-3-319-63516-3_12(457-507)Online publication date: 6-Apr-2018
https://doi.org/10.1007/978-3-319-63516-3_12
Jiang KZheng ZLi L(2017)Topological Structure Matching Measure between Two GraphsComputer-Aided Civil and Infrastructure Engineering10.1111/mice.1227032:6(515-524)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1111/mice.12270
Bajwa RColeri ERajagopal RVaraiya PFlores C(2017)Development of a Cost-Effective Wireless Vibration Weigh-In-Motion System to Estimate Axle Weights of TrucksComputer-Aided Civil and Infrastructure Engineering10.1111/mice.1226932:6(443-457)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1111/mice.12269
Wang ZHu HZhou W(2017)RFID Enabled Knowledge-Based Precast Construction Supply ChainComputer-Aided Civil and Infrastructure Engineering10.1111/mice.1225432:6(499-514)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1111/mice.12254
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents