A Graphics Processing Unit Algorithm to Solve the Quadratic Assignment Problem Using Level-2 Reformulation-Linearization Technique

DOI10.1287/ijoc.2017.0754OpenAlexW2746585819MaRDI QIDQ5131697

Lúcia Maria de A. Drummond, Alexandre Domingues Gonçalves, Artur Alves Pessoa, C. Bentes, Ricardo L. S. Farias

Publication date: 9 November 2020

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2017.0754

zbMATH Keywords

quadratic assignment problemGPU computingreformulation linearization technique

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (3)

Characterizing linearizable QAPs by the level-1 reformulation-linearization technique ⋮ An LP-based characterization of solvable QAP instances with chess-board and graded structures ⋮ Level 2 Reformulation Linearization Technique–Based Parallel Algorithms for Solving Large Quadratic Assignment Problems on Graphics Processing Unit Clusters

Uses Software

• QAPLIB

Cites Work

• 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
• A parallel depth first search branch and bound algorithm for the quadratic assignment problem
• Parallel synchronous and asynchronous implementations of the auction algorithm
• A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method
• A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
• QAPLIB - a quadratic assignment problem library
• Solving large quadratic assignment problems in parallel
• Solving large quadratic assignment problems on computational grids
• A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem
• Three Ideas for the Quadratic Assignment Problem
• Algorithms for the Assignment and Transportation Problems
• Assignment Problems and the Location of Economic Activities
• Parallel Asynchronous Hungarian Methods for the Assignment Problem
• A parallel shortest augmenting path algorithm for the assignment problem
• Solving Lift-and-Project Relaxations of Binary Integer Programs

This page was built for publication: A Graphics Processing Unit Algorithm to Solve the Quadratic Assignment Problem Using Level-2 Reformulation-Linearization Technique