Linear programming insights into solvable cases of the quadratic assignment problem

DOI10.1016/J.DISOPT.2014.07.001zbMATH Open1308.90085OpenAlexW2086953038MaRDI QIDQ2339831FDOQ2339831

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

Recommendations

• Two classes of quadratic assignment problems that are solvable as linear assignment problems
• A contribution to quadratic assignment problems
• Special cases of the quadratic assignment problem
• A new exact discrete linear reformulation of the quadratic assignment problem
• scientific article; zbMATH DE number 1803767

zbMATH Keywords

linearizationquadratic programRLTbinary optimization

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• The linearization problem of a binary quadratic problem and its applications
• Two classes of quadratic assignment problems that are solvable as linear assignment problems
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• An LP-based characterization of solvable QAP instances with chess-board and graded structures
• Title not available (Why is that?)
• Linearizable special cases of the quadratic shortest path problem
• Revisiting some classical linearizations of the quadratic binary optimization problem and linkages with constraint aggregations
• Characterizing linearizable QAPs by the level-1 reformulation-linearization technique
• Special cases of the quadratic shortest path problem

Uses Software

• QAPLIB

This page was built for publication: Linear programming insights into solvable cases of the quadratic assignment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2339831)