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

DOI10.1287/IJOC.2017.0754MaRDI QIDQ5131697zbMATH OpenOpenAlexFDO

Authors Alexandre Domingues Gonçalves, Artur Alves Pessoa, C. Bentes, Lúcia Maria de A. Drummond, 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)

Recommendations

• Level 2 Reformulation Linearization Technique–Based Parallel Algorithms for Solving Large Quadratic Assignment Problems on Graphics Processing Unit Clusters
• Solving large quadratic assignment problems in parallel
• scientific article; zbMATH DE number 714538
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• A level-3 reformulation-linearization technique-based bound for the quadratic assignment problem

Cites work

• 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
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• A level-3 reformulation-linearization technique-based 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
• A parallel shortest augmenting path algorithm for the assignment problem
• A survey 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
• Parallel synchronous and asynchronous implementations of the auction algorithm
• QAPLIB - a quadratic assignment problem library
• Solving Lift-and-Project Relaxations of Binary Integer Programs
• Solving large quadratic assignment problems in parallel
• Solving large quadratic assignment problems on computational grids
• Three Ideas for the Quadratic Assignment Problem

Cited in

(3)

• 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
• Characterizing linearizable QAPs by the level-1 reformulation-linearization technique

Describes a project that uses

Uses Software

• QAPLIB

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

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