Hardware-Compatible Single-Shot Feasible-Space Heuristics for Solving the Quadratic Assignment Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910222793048064 |
|---|---|
| author | Im, Haesol Yang, Chan-Woo Noori, Moslem Dobrynin, Dmitrii Valiante, Elisabetta Pedretti, Giacomo Heittmann, Arne Van Vaerenbergh, Thomas Mohseni, Masoud Strachan, John Paul Strukov, Dmitri Beausoleil, Ray Rozada, Ignacio |
| author_facet | Im, Haesol Yang, Chan-Woo Noori, Moslem Dobrynin, Dmitrii Valiante, Elisabetta Pedretti, Giacomo Heittmann, Arne Van Vaerenbergh, Thomas Mohseni, Masoud Strachan, John Paul Strukov, Dmitri Beausoleil, Ray Rozada, Ignacio |
| contents | Research into the development of special-purpose computing architectures designed to solve quadratic unconstrained binary optimization (QUBO) problems has flourished in recent years. It has been demonstrated in the literature that such special-purpose solvers can outperform traditional complementary metal--oxide--semiconductor architectures by orders of magnitude with respect to timing metrics on synthetic problems. However, they face challenges with constrained problems such as the quadratic assignment problem (QAP), where mapping to binary formulations such as QUBO introduces overhead and limits parallelism. In-memory computing (IMC) devices, such as memristor-based analog Ising machines, offer significant speed-ups and efficiency gains over traditional CPU-based solvers, particularly for solving combinatorial optimization problems. In this work, we present a novel hardware-aware QAP optimization framework designed for IMC hardware. By co-designing the local search heuristic with the underlying hardware, we exploit the intrinsic massive parallelism that allows for computing of full neighbourhoods simultaneously to make update decisions. We ensure binary solutions remain feasible by selecting local moves that lead to neighbouring feasible solutions, leveraging feasible-space search heuristics and the underlying structure of a given problem. Our approach is compatible with both digital computers and analog hardware. We demonstrate its effectiveness in CPU implementations by comparing it with state-of-the-art heuristics for solving the QAP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_09676 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hardware-Compatible Single-Shot Feasible-Space Heuristics for Solving the Quadratic Assignment Problem Im, Haesol Yang, Chan-Woo Noori, Moslem Dobrynin, Dmitrii Valiante, Elisabetta Pedretti, Giacomo Heittmann, Arne Van Vaerenbergh, Thomas Mohseni, Masoud Strachan, John Paul Strukov, Dmitri Beausoleil, Ray Rozada, Ignacio Optimization and Control Hardware Architecture Research into the development of special-purpose computing architectures designed to solve quadratic unconstrained binary optimization (QUBO) problems has flourished in recent years. It has been demonstrated in the literature that such special-purpose solvers can outperform traditional complementary metal--oxide--semiconductor architectures by orders of magnitude with respect to timing metrics on synthetic problems. However, they face challenges with constrained problems such as the quadratic assignment problem (QAP), where mapping to binary formulations such as QUBO introduces overhead and limits parallelism. In-memory computing (IMC) devices, such as memristor-based analog Ising machines, offer significant speed-ups and efficiency gains over traditional CPU-based solvers, particularly for solving combinatorial optimization problems. In this work, we present a novel hardware-aware QAP optimization framework designed for IMC hardware. By co-designing the local search heuristic with the underlying hardware, we exploit the intrinsic massive parallelism that allows for computing of full neighbourhoods simultaneously to make update decisions. We ensure binary solutions remain feasible by selecting local moves that lead to neighbouring feasible solutions, leveraging feasible-space search heuristics and the underlying structure of a given problem. Our approach is compatible with both digital computers and analog hardware. We demonstrate its effectiveness in CPU implementations by comparing it with state-of-the-art heuristics for solving the QAP. |
| title | Hardware-Compatible Single-Shot Feasible-Space Heuristics for Solving the Quadratic Assignment Problem |
| topic | Optimization and Control Hardware Architecture |
| url | https://arxiv.org/abs/2503.09676 |