Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem
- URL: http://arxiv.org/abs/2406.09899v2
- Date: Thu, 20 Jun 2024 01:58:50 GMT
- Title: Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem
- Authors: Zhentao Tan, Yadong Mu,
- Abstract summary: This work focuses on learning-based solutions for efficiently solving the Quadratic Assignment Problem (QAPs)
Current research on QAPs suffer from limited scale and inefficiency.
We propose the first solution of its kind for QAP in the learn-to-improve category.
- Score: 27.33966993065248
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently various optimization problems, such as Mixed Integer Linear Programming Problems (MILPs), have undergone comprehensive investigation, leveraging the capabilities of machine learning. This work focuses on learning-based solutions for efficiently solving the Quadratic Assignment Problem (QAPs), which stands as a formidable challenge in combinatorial optimization. While many instances of simpler problems admit fully polynomial-time approximate solution (FPTAS), QAP is shown to be strongly NP-hard. Even finding a FPTAS for QAP is difficult, in the sense that the existence of a FPTAS implies $P = NP$. Current research on QAPs suffer from limited scale and computational inefficiency. To attack the aforementioned issues, we here propose the first solution of its kind for QAP in the learn-to-improve category. This work encodes facility and location nodes separately, instead of forming computationally intensive association graphs prevalent in current approaches. This design choice enables scalability to larger problem sizes. Furthermore, a \textbf{S}olution \textbf{AW}are \textbf{T}ransformer (SAWT) architecture integrates the incumbent solution matrix with the attention score to effectively capture higher-order information of the QAPs. Our model's effectiveness is validated through extensive experiments on self-generated QAP instances of varying sizes and the QAPLIB benchmark.
Related papers
- Quantum-Inspired Mean Field Probabilistic Model for Combinatorial Optimization Problems [15.435730759218776]
We develop a novel Quantum-Inspired Mean Field (QIMF) probabilistic model that approximates solutions to Quadratic Unconstrained Binary Optimization problems.
Our empirical studies demonstrate significant improvements in solution evaluation for large-scale problems of portfolio selection, the weighted maxcut problem, and the Ising model.
arXiv Detail & Related papers (2024-06-01T01:53:11Z) - Solving the QAP by Two-Stage Graph Pointer Networks and Reinforcement Learning [0.22099217573031676]
Quadratic Assignment Problem (QAP) is a practical optimization problems that has been studied for several years.
Deep reinforcement learning model called the two-stage graph pointer network (GPN) for solving QAP.
Two-stage GPN relies on GPN, which has been proposed for Euclidean Traveling Salesman Problem (TSP)
arXiv Detail & Related papers (2024-03-31T03:01:56Z) - Where the Really Hard Quadratic Assignment Problems Are: the QAP-SAT
instances [0.0]
The Quadratic Assignment Problem (QAP) is one of the major domains in the field of evolutionary computation optimization.
This paper studies the phase transition of the QAP, which can be described as a dramatic change in the problem's computational complexity and satisfiability.
arXiv Detail & Related papers (2024-03-05T08:56:30Z) - Multi-objective Quantum Annealing approach for solving flexible job shop
scheduling in manufacturing [0.0]
This paper introduces Quantum Annealing-based solving algorithm (QASA) to address Flexible Job Shop Scheduling problem.
Experiments on benchmark problems show QASA, combining tabu search, simulated annealing, and Quantum Annealing, outperforms a classical solving algorithm (CSA) in solution quality.
arXiv Detail & Related papers (2023-11-16T07:45:57Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods.
Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem.
As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
arXiv Detail & Related papers (2023-10-08T23:39:38Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms.
GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially.
In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
arXiv Detail & Related papers (2023-05-26T15:13:09Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems.
We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately.
Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
arXiv Detail & Related papers (2022-10-31T09:46:26Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time.
As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware.
We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
arXiv Detail & Related papers (2022-02-17T18:59:20Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP)
This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm.
Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
arXiv Detail & Related papers (2021-05-06T17:59:38Z) - Larger Sparse Quadratic Assignment Problem Optimization Using Quantum
Annealing and a Bit-Flip Heuristic Algorithm [0.4125187280299248]
Linear constraints reduce the size of problems that can be represented in quantum annealers.
We propose a method for solving a sparse QAP by applying a post-processing bit-flip algorithm to solutions obtained by the Ohzeki method.
We successfully solved a QAP of size 19 with high accuracy for the first time using D-Wave Advantage.
arXiv Detail & Related papers (2020-12-18T09:48:28Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
Security-constrained optimal power flow (SCOPF) is fundamental in power systems.
Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs.
This paper proposes a novel approach that combines deep learning and robust optimization techniques.
arXiv Detail & Related papers (2020-07-14T12:38:21Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.