A new exact discrete linear reformulation of the quadratic assignment problem

DOI10.1016/j.ejor.2012.02.010zbMath1253.90140OpenAlexW1969909704MaRDI QIDQ1926740

Tapio Westerlund, Axel Nyberg

Publication date: 29 December 2012

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2012.02.010

zbMATH Keywords

global optimizationcombinatorial optimizationquadratic assignment problemmixed integer programmingdiscrete linear reformulation

Mathematics Subject Classification ID

Mixed integer programming (90C11) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (9)

Facility layout problem with QAP formulation under scenario-based uncertainty ⋮ Taking advantage of symmetry in some quadratic assignment problems ⋮ A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives ⋮ New variable-length data compression scheme for solution representation of meta-heuristics ⋮ Exact algorithms for the solution of the grey pattern quadratic assignment problem ⋮ A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs ⋮ Quadratic assignment problem variants: a survey and an effective parallel memetic iterated tabu search ⋮ A linear formulation with \(O(n^2)\) variables for quadratic assignment problems with Manhattan distance matrices ⋮ The minimum flow cost Hamiltonian cycle problem: a comparison of formulations

Uses Software

• QAPLIB

Cites Work

• Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers
• Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods
• Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
• A survey for the quadratic assignment problem
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• A new relaxation framework for quadratic assignment problems based on matrix splitting
• An algorithm for the quadratic assignment problem using Benders' decomposition
• QAPLIB - a quadratic assignment problem library
• Recent advances in the solution of quadratic assignment problems
• Solving large quadratic assignment problems on computational grids
• Branching rules revisited
• Finding a cluster of points and the grey pattern quadratic assignment problem
• Assignment Problems and the Location of Economic Activities
• A new bound for the quadratic assignment problem based on convex quadratic programming

This page was built for publication: A new exact discrete linear reformulation of the quadratic assignment problem