×

A parallel branch and bound algorithm for the quadratic assignment problem. (English) Zbl 0632.90047

We propose a parallel branch and bound algorithm for the quadratic assignment problem; this algorithm has been implemented on an asynchronous multiprocessor machine with shared memory (the Cray X-MP). For problems with size \(n\geq 10\), the improvement in using n processors is very close to n, and moreover very good results are obtained for a classical example from the literature with size 12.

MSC:

90C10 Integer programming
65K05 Numerical mathematical programming methods
90C20 Quadratic programming
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abreu, N. N.de; Boaventura, P. O., An algebraic and combinatorial study of the quadratic assignment problem, Euro VII (June 1985), Bologne, Italy
[2] Burkard, R. E., Some recent advances in quadratic assignment problems, Math. Programming, 53-68 (1984)
[3] Burton, F. W.; Huntbach, M. M.; McKeown, G. P.; Smith, V. J.Rayward, Parallelism in branch and bound algorithms, (Mathematical Algorithms group-2, Internal report CSA/3 (1983), University of East Anglia: University of East Anglia Norwick)
[4] Dessouki, O. I.El; Huen, W. H., Distributed enumeration on network computers, IEEE Trans. Comput., 29, 818-825 (1980)
[5] Finke, G.; Burkard, R. E.; Rendl, F., Quadratic assignment problems (July 1985), School on Combinatorial Optimization: School on Combinatorial Optimization Rio de Janeiro, Brazil
[6] Fox, B.; Lenstra, J.; Rinnooy Kan, A.; Schrage, L., Branching from the largest upper bound folklore and fact, Europ. J. Oper. Res., 191-194 (1978) · Zbl 0381.90075
[7] Gilmore, P. C., Optimal and suboptimal algorithms for the quadratic assignment problem, J. SIAM, 10, 305-313 (1962) · Zbl 0118.15101
[8] Kindervater, G. A.P.; Trienekens, H. W.J. M., Experiments with parallel algorithms for combinatorial problems, (Reports OS-R8512 (Nov. 1985), Centrum voor Wiskunde en Informatica: Centrum voor Wiskunde en Informatica Amsterdam) · Zbl 0631.90052
[9] Lavallée, I.; Roucairol, C., A parallel branch and bound algorithm for asynchronous MIMD machines and computer networks, Rapport interne CNRS GR22 (avril 1983), Paris VI
[10] Lavallée, I.; Roucairol, C., Parallel branch and bound algorithms, (EURO VII Congress, Rapport interne MASI, 6 (1985), Université Paris)
[11] Laurent, P.; Verleye, C., Procedures arborescentes sur machines paralléles et réseaux de processeurs, (Mémoire d’ingénieur IIE-CNAM (1985), Evry)
[12] Mautor, T.; Savoye, D., Etudes d’heuristiques pour le probléme d’affectation quadratique, Mémoire d’ingénieur CNAM-IIE (1982)
[13] Mohan, J., A study in parallel computation: the traveling salesman problem (1982), Carnegie Mellon University, CMU-CS-82-136
[14] Nugent, C. E.; Vollmann, T. E.; Ruml, J., An experimental comparison of techniques for the assignment of facilities to locations, J. Oper. Res., 16, 150-173 (1969)
[15] Roucairol, C. E., A reduction method for quadratic assignment problem, Operations Research Verfahren/Methods of Operations Research, 32, 185-187 (1979) · Zbl 0414.90070
[16] Roucairol, C. D., An efficient branching scheme in branch and bound procedures, (Tims XXVI, Paper no. 42 (1984), Masi, Université Paris 6: Masi, Université Paris 6 Paris)
[17] Sahni, S.; Lai, Ted Hwang, Anomalies in branch and bound, Comm. ACM, 27, 6, 594-602 (1984) · Zbl 0587.68032
[18] Wah, B. W.; Ma, Y. W., Manip — a multicomputer architecture for solving combinatorial problem extremum search problems, IEEE Trans. Comput., 5, 377-389 (1984) · Zbl 0528.68005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.