Characterizing linearizable QAPs by the level-1 reformulation-linearization technique

DOI10.1016/j.disopt.2023.100812OpenAlexW4388850884MaRDI QIDQ6122081

Lucas A. Waddell, Warren P. Adams

Publication date: 27 March 2024

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

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

zbMATH Keywords

RLTquadratic assignment problemlinearizable

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linearizable special cases of the QAP
• The Wiener maximum quadratic assignment problem
• Two classes of quadratic assignment problems that are solvable as linear assignment problems
• Mixed-integer bilinear programming problems
• A hierarchy of relaxations leading to the convex hull representation for general discrete optimization 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
• 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
• 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
• The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
• Solving large quadratic assignment problems on computational grids
• The linearization problem of a binary quadratic problem and its applications
• Dynamic sparsification for quadratic assignment problems
• Linear programming insights into solvable cases of the quadratic assignment problem
• A revised reformulation-linearization technique for the quadratic assignment problem
• Well-solvable cases of the QAP with block-structured matrices
• 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
• 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 Graphics Processing Unit Algorithm to Solve the Quadratic Assignment Problem Using Level-2 Reformulation-Linearization Technique
• Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems