O(1) Deltapart part computation technique for the quadratic assignment problem
AbstractThe quadratic assignment problem is rightfully considered to be one of the most challenging problems of combinatorial optimization. Since this problem is NP-hard, the use of heuristic algorithms is the only way to find in a reasonable time a solution that is close to optimal. One of the most effective heuristic algorithms is the Robust Tabu Search, which is the basis of many subsequent metaheuristic algorithms. The paper describes a novel approach to scanning the neighborhood of the current solution that allows reducing by half the number of delta values that were required to be computed with complexity in most of the heuristics for the quadratic assignment problem. Using the correlation between the old and new delta values, obtained in this work, a new formula of complexity is proposed. The results obtained leads up to 25% performance increase as compared to such well-known algorithms as the Robust Tabu Search and others based on it. The formula obtained in this paper may be successfully applied to other heuristics using a full scan of the solution neighborhood.
Koopmans T.C., Beckmann M.J. Assignment problems and the location of economic activities // Econometrica. — 1957. — № 25. — P. 53–76.
Sahni S., Gonzalez T. P-complete approximation problems // Journal of the Association of Computing Machinery. — 1976. — № 23. — P. 555–565.
Taillard E. Robust tabu search for the quadratic assignment problem // Parallel Computing. — 1991. — № 17. — P. 443–455.
Tate D.M., Smith A.E. A genetic approach to the quadratic assignment problem // Computers and Operations Research. — 1995. — № 22. — P. 73–83.
Colorni A., Maniezzo V. The ant system applied to the quadratic assignment problem // IEEE Transactions on Knowledge and Data Engineering. — 1999. — 11. — P. 769–778.
Battiti R., Tecchiolli G. The reactive tabu search // ORSA Journal on Computing. — 1994. — № 6. — P. 126–140.
Paul G. An efficient implementation of the robust tabu search heuristic for sparse quadratic assignment problems // European Journal of Operational Research. — 2011. — № 209. — P. 215–218.
Kothari R., Ghosh D. Insertion based Lin-Kernighan heuristic for single row facility layout // Computers & Operations Research. — 2013. — № 40(1). — P. 129–136.