Linear programming insights into solvable cases of the quadratic assignment problem

DOI10.1016/j.disopt.2014.07.001zbMath1308.90085OpenAlexW2086953038MaRDI QIDQ2339831

Warren P. Adams, Lucas A. Waddell

Publication date: 9 April 2015

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2014.07.001

zbMATH Keywords

RLTlinearizationquadratic programbinary optimization

Mathematics Subject Classification ID

Integer programming (90C10) Quadratic programming (90C20) Discrete location and assignment (90B80) Boolean programming (90C09)

Related Items

Characterizing linearizable QAPs by the level-1 reformulation-linearization technique, An LP-based characterization of solvable QAP instances with chess-board and graded structures, A characterization of linearizable instances of the quadratic minimum spanning tree problem, Special cases of the quadratic shortest path problem, The linearization problem of a binary quadratic problem and its applications

Uses Software

• QAPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal sequencing of a set of positive numbers with the variance of the sequence's partial sums maximized
• The Wiener maximum quadratic assignment problem
• Two classes of quadratic assignment problems that are solvable as linear assignment problems
• A survey for the quadratic assignment problem
• A note on a polynomial time solvable case of the quadratic assignment problem
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• On lower bounds for a class of quadratic 0,1 programs
• On the quadratic assignment problem
• An algorithm for the quadratic assignment problem using Benders' decomposition
• A solvable case of the quadratic assignment problem
• A reformulation-linearization technique for solving discrete and continuous nonconvex problems
• The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
• A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
• QAPLIB - a quadratic assignment problem library
• The quadratic assignment problem. Theory and algorithms
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• Another well-solvable case of the QAP: maximizing the job completion time variance
• Solving large quadratic assignment problems on computational grids
• The Quadratic Assignment Problem
• A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem
• An O(n⁴) Algorithm for the QAP Linearization Problem
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• The Backboard Wiring Problem: A Placement Algorithm
• Assignment Problems and the Location of Economic Activities
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Benders' partitioning scheme applied to a new formulation of the quadratic assignment problem
• Scheduling Parallel Production Lines with Changeover Costs: Practical Application of a Quadratic Assignment/LP Approach
• Entwurf von Schreibmaschinentastaturen mittels quadratischer Zuordnungsprobleme
• Hospital Layout as a Quadratic Assignment Problem
• A unified approach to simple special cases of extremal permutation problems
• Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems