Where the Really Hard Quadratic Assignment Problems Are: the QAP-SAT
instances
- URL: http://arxiv.org/abs/2403.02783v1
- Date: Tue, 5 Mar 2024 08:56:30 GMT
- Title: Where the Really Hard Quadratic Assignment Problems Are: the QAP-SAT
instances
- Authors: S\'ebastien Verel (LISIC), Sarah Thomson, Omar Rifki (LISIC)
- Abstract summary: 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.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Quadratic Assignment Problem (QAP) is one of the major domains in the
field of evolutionary computation, and more widely in combinatorial
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, within a narrow range of the problem parameters. To approach
this phenomenon, we introduce a new QAP-SAT design of the initial problem based
on submodularity to capture its difficulty with new features. This
decomposition is studied experimentally using branch-and-bound and tabu search
solvers. A phase transition parameter is then proposed. The critical parameter
of phase transition satisfaction and that of the solving effort are shown to be
highly correlated for tabu search, thus allowing the prediction of difficult
instances.
Related papers
- Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem [27.33966993065248]
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.
arXiv Detail & Related papers (2024-06-14T10:15:03Z) - Solving Quantified Boolean Formulas with Few Existential Variables [19.221715574358207]
The quantified Boolean formula (QBF) problem is an important decision problem generally viewed as the archetype for PSPACE-completeness.
In this paper we consider a simple but overlooked parameter: the number of existentially quantified variables.
We then develop a novel FPT algorithm applicable to QBF instances in conjunctive normal form (CNF) of bounded clause length.
arXiv Detail & Related papers (2024-05-10T14:07:29Z) - The Complexity of Optimizing Atomic Congestion [14.845310803203724]
Atomic congestion games are a classic topic in network design, routing, and algorithmic game theory.
We show that the problem remains highly intractable even on extremely simple networks.
We conclude by extending our analysis towards the (even more challenging) min-max variant of the problem.
arXiv Detail & Related papers (2023-12-15T21:31:30Z) - Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
We propose textbftextitThought Propagation (TP) to enhance the complex reasoning ability of Large Language Models.
TP first prompts LLMs to propose and solve a set of analogous problems that are related to the input one.
TP reuses the results of analogous problems to directly yield a new solution or derive a knowledge-intensive plan for execution to amend the initial solution obtained from scratch.
arXiv Detail & Related papers (2023-10-06T01:40:09Z) - Fixed-Point Automatic Differentiation of Forward--Backward Splitting
Algorithms for Partly Smooth Functions [8.680676599607123]
We show that under partial smoothness, Automatic Differentiation converges to the derivative of the solution mapping.
We numerically illustrate the convergence and convergence rates of AD and FPAD on Lasso and Group Lasso problems.
arXiv Detail & Related papers (2022-08-05T11:27:55Z) - General Hamiltonian Representation of ML Detection Relying on the
Quantum Approximate Optimization Algorithm [74.6114458993128]
The quantum approximate optimization algorithm (QAOA) conceived for solving optimization problems can be run on the existing noisy intermediate-scale quantum (NISQ) devices.
We solve the maximum likelihood (ML) detection problem for general constellations by appropriately adapting the QAOA.
In particular, for an M-ary Gray-mapped quadrature amplitude modulation (MQAM) constellation, we show that the specific qubits encoding the in-phase components and those encoding the quadrature components are independent in the quantum system of interest.
arXiv Detail & Related papers (2022-04-11T14:11:24Z) - A Variational Inference Approach to Inverse Problems with Gamma
Hyperpriors [60.489902135153415]
This paper introduces a variational iterative alternating scheme for hierarchical inverse problems with gamma hyperpriors.
The proposed variational inference approach yields accurate reconstruction, provides meaningful uncertainty quantification, and is easy to implement.
arXiv Detail & Related papers (2021-11-26T06:33:29Z) - 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) - Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep
Unrolling [86.85697555068168]
Two-stage algorithmic optimization plays a critical role in various engineering and scientific applications.
There still lack efficient algorithms, especially when the long-term and short-term variables are coupled in the constraints.
We show that PDD-SSCA can achieve superior performance over existing solutions.
arXiv Detail & Related papers (2021-05-05T03:36:00Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
We propose two novel conditional gradient-based methods for solving structured convex optimization problems.
The most important feature of our framework is that only a subset of the constraints is processed at each iteration.
Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
arXiv Detail & Related papers (2020-07-07T21:26:35Z)
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.