A linear formulation with \(O(n^2)\) variables for quadratic assignment problems with Manhattan distance matrices

DOI10.1007/s13675-014-0033-4zbMath1333.90079OpenAlexW2078879373MaRDI QIDQ2516354

Serigne Gueye, Philippe Yves Paul Michelon

Publication date: 31 July 2015

Published in: EURO Journal on Computational Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s13675-014-0033-4

zbMATH Keywords

integer programmingdistancequadratic assignment problemcutting planes

Mathematics Subject Classification ID

Integer programming (90C10) Discrete location and assignment (90B80)

Uses Software

• QAPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bounds for the quadratic assignment problem using the bundle method
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• On the quadratic assignment problem
• An algorithm for the quadratic assignment problem using Benders' decomposition
• QAPLIB - a quadratic assignment problem library
• Semidefinite programming relaxations for the quadratic assignment problem
• Generating lower bounds for the linear arrangement problem
• Lower bounds for the quadratic assignment problem via triangle decompositions
• A new exact discrete linear reformulation of the quadratic assignment problem
• The Quadratic Assignment Problem
• A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem
• Laying Out Sparse Graphs with Provably Minimum Bandwidth
• Decorous Lower Bounds for Minimum Linear Arrangement
• Estimating Bounds for Quadratic Assignment Problems Associated with Hamming and Manhattan Distance Matrices Based on Semidefinite Programming
• Three Ideas for the Quadratic Assignment Problem
• On the Assignment Polytope
• Assignment Problems and the Location of Economic Activities
• A New Lower Bound for the Minimum Linear Arrangement of a Graph
• L’algebre de Boole et ses applications en recherche operationnelle
• Tabu Search Applied to the Quadratic Assignment Problem
• A New Lower Bound Via Projection for the Quadratic Assignment Problem
• Improved Linear Integer Programming Formulations of Nonlinear Integer Problems
• Comparison of iterative searches for the quadratic assignment problem
• Computing Lower Bounds for the Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming
• Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems
• Solving Lift-and-Project Relaxations of Binary Integer Programs
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
• A Theorem on Boolean Matrices