# Branch And Bound Assignment Problem In Linear

This paper presents a new branch-and-bound algorithm for solving the quadratic assignment problem (QAP). The algorithm is based on a dual procedure (DP) similar to the Hungarian method for solving the linear assignment problem. Our DP solves the QAP in certain cases, i.e., for some small problems (*N*< 7) and for numerous larger problems (7≤ *N* ≤16) that arise as sub-problems of a larger QAP such as the Nugent 20. The DP, however, does not guarantee a solution. It is used in our algorithm to calculate lower bounds on solutions to the QAP. As a result of a number of recently developed improvements, the DP produces lower bounds that are as tight as any which might be useful in a branch-and-bound algorithm. These are produced relatively cheaply, especially on larger problems. Experimental results show that the computational complexity of our algorithm is lower than known methods, and that its actual runtime is significantly shorter than the best known algorithms for QAPLIB test instances of size 16 through 22. Our method has the potential for being improved and therefore can be expected to aid in solving even larger problems.

1.

S.H. Bokhari . *Assignment problems in parallel and distributed computing*. The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, Boston/Dordrecht/Lancaster, 1987.Google Scholar

2.

Brian Borchers and John E. Mitchell. Using an interior point method in a branch and bound algorithm for integer programming. Technical report, Rensselaer Polytechnic Institute, July 1992.Google Scholar

3.

R.E. Burkard and U. Derigs. *Assignment and matching problems: Solution methods with Fortran programs*, volume 184 of *Lecture Notes in Economics and Mathematical Systems*. Springer, Berlin, 1980.Google Scholar

4.

R.E. Burkard, S. Karisch, and F. Rendí. QAPLIB — A quadratic assignment problem library. *European Journal of Operational Research*, 55:115–119,1991. Updated version — Feb. 1994.MATHCrossRefGoogle Scholar

5.

R.E. Burkard find F. Rendl. A thermodynamically motivated simulation procedure for com-binatorial optimization problems. *European Journal of Operational Research*, 17: 169–174, 1984.Google Scholar

6.

J. Clausen . Announcement on Discrete Mathematics and Algorithms Network ( DIMANET ), Feb. 1994.Google Scholar

7.

Z. Drezner. Lower bounds based on linear programming for the quadratic assignment problem. Technical report, Dept. of Management Science, California State University, Fullerton, CA 92634, 1994. To appear in *Computational Optimization & Applications*.Google Scholar

8.

C.S. Edwards. A branch and bound algorithm for the Koopmans-Beckman quadratic assign-ment problem. *Mathematical Programming Study*, 13: 35–52, 1980.MATHGoogle Scholar

9.

C. Fleurent and J.A. Ferland. Genetic hybrids for the quadratic assignment problem. In P.M. Pardalos and H. Wolkowicz, editors, *Quadratic assignment and related problems*, volume 16 of *DIMACS Series on Discrete Mathematics and Theoretical Computer Science*, pages 173–187. American Mathematical Society, 1994.Google Scholar

10.

R. Fourer, D.M. Gay, and B.W. Kernighan. AMPL — *A modeling language for mathematical programming*. The Scientific Press, South San Francisco, CA, 1993.Google Scholar

11.

R.L. Francis and J.A. White. *Facility layout and location*. Prentice-Hall, Englewood Cliffs, N.J., 1974.Google Scholar

12.

P.C. Gilmore. Optimal and suboptimal algorithms for the quadratic assignment problem. *J. SI AM*, 10: 305–313, 1962.MathSciNetMATHGoogle Scholar

13.

L.J. Hubert . *Assignment methods in combinatorial data analysis*. Marcel Dekker, Inc., New York, NY 10016, 1987.MATHGoogle Scholar

14.

T. Ibaraki. Theoretical comparisons of search strategies in branch-and-bound algorithms. *International Journal of Computer and Information Sciences*, 5 (4): 315–344, 1976.MathSciNetMATHCrossRefGoogle Scholar

15.

N.K. Karmarkar and K.G. Ramakrishnan. Computational results of an interior point algorithm for large scale linear programming. *Mathematical Programming*, 52: 555–586, 1991.MathSciNetMATHCrossRefGoogle Scholar

16.

T.C. Koopmans and M.J. Beckmann. Assignment problems and the location of economic activities. *Econometrica*, 25: 53–76, 1957.MathSciNetMATHCrossRefGoogle Scholar

17.

J. Krarup and P.M. Pruzan. Computer-aided layout design. *Mathematical Programming Study*, 9: 75–94, 1978.MathSciNetGoogle Scholar

18.

E.L. Lawler. The quadratic assignment problem. *Management Science*, 9: 586–599, 1963.MathSciNetMATHCrossRefGoogle Scholar

19.

Y. Li, P.M. Pardalos, K.G. Ramakrishnan, and M.G.C. Resende. Lower bounds for the quadratic assignment problem. *Annals of Operations Research*, 50: 387–410, 1994.MathSciNetMATHCrossRefGoogle Scholar

20.

Y. Li, P.M. Pardalos, and M.G.C. Resende. A greedy randomized adaptive search procedure for the quadratic assignment problem. In P.M. Pardalos and H. Wolkowicz, editors, *Quadratic assignment and related problems*, volume 16 of *DIMACS Series on Discrete Mathematics and Theoretical Computer Science*, pages 237–261. American Mathematical Society, 1994.Google Scholar

21.

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 *DIMACS Series on Discrete Mathematics and Theoretical Computer Science*, pages 263–274. American Mathematical Society, 1994.Google Scholar

22.

T. Mautor and C. Roucairol. A new exact algorithm for the solution of quadratic assignment problems. *Discrete Applied Mathematics*, 1994. To appear.Google Scholar

23.

H. Mawengkang and B.A. Murtagh. Solving nonlinear integer programs with large-scale optimization software. *Annals of Operations Research*, 5:425–437, 1985/6.MathSciNetGoogle Scholar

24.

E.J. McCormik. *Human factors engineering*. McGraw-Hill, New York, 1970.Google Scholar

25.

John E. Mitchell . Interior point algorithms for integer programming. Technical report, Rensselaer Polytechnic Institute, June 1994. To appear in *Advances in linear and integer programming*, Oxford University Press, 1995.Google Scholar

26.

B.A. Murtagh, T.R. Jefferson, and V. Sornprasit. A heuristic procedure for solving the quadratic assignment problem. *European Journal of Operational Research*, 9: 71–76, 1982.MATHCrossRefGoogle Scholar

27.

P.M. Pardalos and J. Crouse. A parallel algorithm for the quadratic assignment problem. In *Proceedings of the Supercomputing 1989 Conference*, pages 351–360. ACM Press, 1989.CrossRefGoogle Scholar

28.

P.M. Pardalos, K.G. Ramakrishnan, M.G.C. Resende, and Y. Li. Implementation of a variance reduction based lower bound in a branch and bound algorithm for the quadratic assignment problem. Technical report, AT & T Bell Laboratories, Murray Hill, NJ 07974, 1994.Google Scholar

29.

P.M. Pardalos and H. Wolkowicz, editors. *Quadratic assignment and related problems*, volume 16 of *DIMACS Series on Discrete Mathematics and Theoretical Computer Science*. American Mathematical Society, 1994.Google Scholar

30.

M.G.C. Resende, P.M. Pardalos, and Y. Li. FORTRAN subroutines for approximate solution of dense quadratic assignment problems using GRASP. ACM *Transactions on Mathematical Software*, To appear.Google Scholar

31.

M.G.C. Resende, K.G. Ramakrishnan, and Z. Drezner. Computing lower bounds for the quadratic assignment problem with an interior point algorithm for linear programming. *Operations Research*, To appear.Google Scholar

32.

C. Roucairol. A parallel branch and bound algorithm for the quadratic assignment problem. *Discrete Applied Mathematics*, 18: 211–225, 1987.MathSciNetMATHCrossRefGoogle Scholar

33.

J. Skorin-Kapov. Tabu search applied to the quadratic assignment problem. *ORSA Journal on Computing*, 2 (l): 33–45, 1990.MATHGoogle Scholar

34.

E. Taillard. Robust tabu search for the quadratic assignment problem. *Parallel Computing*, 17: 443–455, 1991.MathSciNetCrossRefGoogle Scholar

35.

Thonemann, U.W. and Bolte, A.M. An improved simulated annealing algorithm for the quadratic assignment problem. Technical report, School of Business, Dept. of Production and Operations Research, University of Paderborn, Germany, 1994.Google Scholar

## 0 thoughts on “Branch And Bound Assignment Problem In Linear”

-->