A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems

Full text

Pdf (894 KB)

Source

ACM Annual Computer Science Conference archive
Proceedings of the 1990 ACM annual conference on Cooperation table of contents

Washington, D.C., United States

Pages: 56 - 62

Year of Publication: 1990

ISBN:0-89791-348-5

Authors

J. F. Pekny	Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA
D. L. Miller	Central Research and Development Department, E. I. du Pont de Nemours & Company Inc., Wilmington, DE

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 21, Downloads (12 Months): 112, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/100348.100358 What is a DOI?

ABSTRACT

A parallel branch and bound algorithm that solves the asymmetric traveling salesman problem to optimality is described. The algorithm uses an assignment problem based lower bounding technique, subtour elimination branching rules, and a subtour patching algorithm as an upper bounding procedure. The algorithm is organized around a new data flow framework for parallel branch and bound. Computational results are presented for problem sizes from 500 to 7500 cities with cost matrix elements randomly drawn from a uniform distribution of integers in the range [0,1000] and [0,10000].

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	E. Balas and P. Toth, "Branch and Bound Methods," in The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, ed. E. L. Lawler, I. K. Lenstra, A. H. G. Rinnooy Kart, D. B. Shmoys, John Wiley & Sons, New York, 1985.
	2	E. Balas, D. L. Miller, J. F. Pekny, and P. Toth, "A Parallel Shortest Path Algorithm for the Assignment Problem," Management Science Research Report No. MSRR-552, Carnegie Mellon University, Pittsburgh, PA,
	3	G. B. Dantzig, D. R. Fulkerson, and S. M. Iohnson, "Solution of a Large-Scale Traveling-Salesman Problem," Operations Research, vol. 2, p. 393, 1954.
	4	G.B. Dantzig, D. R. Fulkerson, and S. M. Johnson, "On a Linear-Programming, Combinatorial Approach to the Traveling-Salesman Problem," Operations Research, vol. 7, p. 58, 1959.
	5	E.L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Karl, and D. B. Shrnoys, The Traveling Salesman Problem A Guided Tour of Combinatorial Optimization, Wiley, New York, 1985.
	6	E. A. Pruul, "Parallel Processing and a Branch-and- Bound Algorithm," M.Sc. thesis, Comell University, 1975.
	7	E.A. Pruul, G. L. Nemhauser, and R. A. Rushmeier, "Branch-and-Bound and Parallel Computations: A Historical Note," Operations Research, vol. 7, no. 2, pp. 65-69, 1988.
	8	J. Mohan, "Experience with Two Parallel Programs Solving the Traveling Salesman Problem," IEEE Int. Conference on Parallel Processing, pp. 191-193, 1983.
	9	J.D.C. Little, K. G. Murty, D. W. Sweeney, and C. Kate1, "An Algorithm for the Traveling Salesman Problem," Operations Research, vol. 11, pp. 972-989, 1963.
	10	D.L. Miller and I. F. Pekny, "Results From A Parallel Branch and Bound Algorithm For Solving Large Asymmetric Traveling Salesman Problems," Operations Research Letters, vol. 8, pp. 129-135, 1989.
	11	G.A.P. Kindervater and J. K. Lenstra, "Paralld Algorithms," in Combinatorial Optimization: Annotated Bibliographies, ed. M. O'hEigeaxtaigh, J. K. Lenstra, A. H. G. Rinnooy Karl, pp. 106-128, Wiley, Chichester, 1985.
	12	C. C. Ribeiro, "Parallel Computer Models and Combinatorial Algorithms," Annals of Discrete Mathematics, vol. 3 I, pp. 325-364, 1987.
	13	M. Padberg and G. Rinaldi, "Optimization of a 532-City Symmetric Traveling Salesman Problem By Branch and Cut," Operations Research, vol. 6, no. I, pp. i-7, 1987.
	14	M. Fischetti and P. Toth, "An Additive Bounding Procedure for Combinatorial Optimization Problems," Operations Research, vol. 37, no. 2, pp. 319-328, 1989.
	15	T.H.C. Smith, V. Srinivasan, and G. L. Thompson, "Computational Performance of Three Subtour Elimination Algorithms for Solving Asymmetric Traveling Salesman Problems," Annals of Discrete Mathematics, vol. 1, pp. 495-506, 1977.
	16	G. Carpaneto and P. Toth, "Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem," Management Science, vol. 26, no. 7, pp. 736-743, 1980.
	17	E. Balas and N. Christofides, "A Restricted Lagrangean Approach to the Traveling Salesman Problem," Mathematical Programming, vol. 21, pp. 19-46, 1981.
	18	D. P. Bertsekas and W. L. Eastman, "Linear Programming with Pattern Constraints," proceeding of the 24th IEEE Conference on Decision and Control, 1958.
	19	Donald M. Shapiro, Algorithms for the solution of the optimal cost and bottle-neck travelingsalesman problems., 1966
	20	K.G. Murty, "An Algorithm For Ranking All the Assignments in Order of Increasing Cost," Operations Research, vol. 16, pp. 682-687, 1968.
	21	M. Bellmore and J. C. Malone, "Pathology of Traveling Salesman Subtour-Elimination Algorithms," Operations Research, vol. 19, pp. 278-307, 1971.
	22	R.S. Garfinkel, "On Partitioning the Feasible Set in a Branch-and-bound Algorithm for the Asymmetric Traveling-salesman Problem," Operations Research, vol. 21, pp. 340-343, 1973.
	23	S. Martello and P. Toth, "Linear Assignment Problems," Annals of Discrete Mathematics, vol. 31, pp. 259-282, 1987.
	24	Dimitri P. Bertsekas , Didier el Baz, Distributed asynchronous relaxation methods for convex network flow problems, SIAM Journal on Control and Optimization, v.25 n.1, p.74-85, Jan. 1987 [doi>10.1137/0325006]
	25	D.L. Miller, J. F. Pekny, and G. L. Thompson, "Solution of Large Dense Transportation Problems Using A Parallel Primal Method," Operations Research Letters, 1990. accepted for publication
	26	J. Kennington and Z. Wang, "Solving Dense Assignment Problems on a Shared Memory Multiprocessor," Technical Report 88-OR-16, 1988.
	27	R. M. Karp, "A Patching Algorithm for the Nonsymmetric Travelling-Salesman Problem," Siam J. Computers, vol. 8, no. 4, pp. 561-573, 1979.
	28	G. Li and B. W. Wah, Computational Eff~iency of Parallel Approximate Branch-and-Bound Algorithms, pp. 473-480, 1984.
	29	M. Bellmore and J. C. Malone, Pathology of Traveling- Salesman Subtour Elimination Algorithms, pp. 278-307, 1969.
	30	O.I. E1-Dessouki and W. H. Huen, "Distributed Enumeration on Between Computers," IEEE Transactions on Computers, vol. C-29, no. 9, pp. 818- 825, 1980.
	31	I. Lavallee and C. Roucairol, "Parallel Branch and Bound Algorithms," MASI Research Report, EURO VII, Bologna, Italy, 1985.
	32	Randall Rettberg , Robert Thomas, Contention is no obstacle to shared-memory multiprocessing, Communications of the ACM, v.29 n.12, p.1202-1212, Dec. 1986 [doi>10.1145/7902.7905]
	33	Kai Hwang , Faye A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, Inc., New York, NY, 1990
	34	B. Camahan, H. A. Luther, and J. O. Wilkes, Applied Numerical Methods, Wiley, New York, 1969.
	35	Ten-Hwang Lai , Sartaj Sahni, Anomalies in parallel branch-and-bound algorithms, Communications of the ACM, v.27 n.6, p.594-602, June 1984 [doi>10.1145/358080.358103]
	36	T H Lai , A Sprague, A note on anomalies in parallel branch-and-bound algorithms with one-to-one bounding functions, Information Processing Letters, v.23 n.3, p.119-122, Oct. 1986 [doi>10.1016/0020-0190(86)90109-2]