A Hybrid Classical-Quantum Approach for Multi-Constrained Location Optimization Problem

• URL: http://arxiv.org/abs/2607.16277v1
• Date: Wed, 08 Jul 2026 19:44:55 GMT
• Title: A Hybrid Classical-Quantum Approach for Multi-Constrained Location Optimization Problem
• Abstract summary: The Maximal Covering Location Problem (MCLP) aims to determine the optimal facility placements that maximize total coverage.<n>It is characterized by both equality and inequality constraints, which ensure correct coverage but significantly increase the complexity of exploring the solution space as instance size grows.<n>In this work, the MCLP is formulated as a Quadratic Unconstrained Binary Optimization model, where constraint embedding plays a critical role in solution quality.
• Score: 0.19573380763700712
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Maximal Covering Location Problem (MCLP) is an NP-hard Combinatorial Optimization Problem (COP) that aims to determine the optimal facility placements that maximize total coverage. It is characterized by both equality and inequality constraints, which ensure correct coverage but significantly increase the complexity of exploring the solution space as instance size grows. Hybrid quantum-classical approaches might offer a promising alternative to classical optimization methods by enabling the exploration of complex energy landscapes through quantum superposition and probabilistic sampling. In this work, the MCLP is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) model, where constraint embedding plays a critical role in solution quality. In particular, Unbalanced Penalization (UP) is employed as an alternative to the Slack Variables (SV) for handling inequality constraints without increasing the number of variables. This study focuses on QAOA and one of its variants, the WS-QAOA, which leverages a biased initial state derived from a continuous relaxation of the problem. Additionally, a linear ramp (LR) parameter schedule is incorporated to reduce optimization complexity. The performance of these techniques is evaluated both individually and in combination, as a function of circuit depth $p$ and problem size. Results show that the combined approach of UP, LR, and WS-QAOA consistently improves solution quality and feasibility metrics, while maintaining robust performance as the problem size increases, highlighting its potential within hybrid quantum-classical optimization frameworks.

Related papers

• Decomposition-Based QAOA for Maximum Coverage Location Problem in Satellite Constellation Design [4.190898032627423]
  maximizing coverage while utilizing limited orbital resources is one of the critical design challenges for complex optimization problems.<n>The maximal covering location problem (MCLP), serves as a base for orbital coverage modeling, is NP-hard and computationally intractable for large-constellation instances.<n>This paper proposes a scalable quantum optimization framework for MCLP in satellite constellation design.
  arXiv  Detail & Related papers  (2026-07-09T04:39:44Z)
• Pure and mixed Dicke state ansatz for equality and inequality constraints in variational quantum eigensolver [0.0]
  Combinatorial optimization can be addressed with quantum computing through variational quantum algorithms.<n>A central challenge is to design an ansatz expressive enough to explore the feasible subspace of the Hilbert space where the optimal solution lies.<n>We propose the first feasibility-preserving mixed Dicke state ansatz for Hamming weight constrained optimization.
  arXiv  Detail & Related papers  (2026-06-07T08:10:09Z)
• CVaR-Assisted Custom Penalty Function for Constrained Optimization [3.652509571098291]
  Constrained optimization problems are frequently reformulated as quadratic unconstrained binary optimization (QUBO) models.<n>Standard QUBO formulations enforce inequality constraints through slack variables and quadratic penalties.<n>We propose a slack-free penalty formulation for constrained binary optimization that eliminates auxiliary slack variables.
  arXiv  Detail & Related papers  (2026-04-22T01:08:38Z)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  This paper proposes a novel combination of constraint encoding methods for the Quantum Approximate Optimization Ansatz.<n>One-hot constraints are enforced through $XY$-mixers that restrict the search space to the feasible sub-space naturally.<n>Since $XY$-mixers restrict the search space, specific state vector entries are always zero and can be omitted from the simulation, saving valuable memory and computing resources.
  arXiv  Detail & Related papers  (2025-06-03T17:46:53Z)
• SCOOP: A Quantum-Computing Framework for Constrained Combinatorial Optimization [0.0]
  We present SCOOP, a novel framework for solving constrained optimization problems.<n>SCOOP transforms a constrained problem into an unconstrained counterpart, forming SCOOP problem twins.<n>We demonstrate the framework on three NP-hard problems, Minimum Dominating Set, Minimum Maximal Matching, and Minimum Set Cover.
  arXiv  Detail & Related papers  (2025-04-15T06:17:23Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization [53.14532968909759]
  We introduce an efficient single-loop primal-dual block-coordinate algorithm called ALEXR.<n>We establish the convergence rates of ALEXR in both convex and strongly convex cases under smoothness and non-smoothness conditions.<n> Experimental results on GDRO and partial Area Under the ROC Curve for cFCCO demonstrate the promising performance of our algorithm.
  arXiv  Detail & Related papers  (2023-12-04T19:00:07Z)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  We study multi-agent reinforcement learning (MARL) for the general-sum Markov Games (MGs) under the general function approximation. We introduce a novel complexity measure called the Multi-Agent Decoupling Coefficient (MADC) for general-sum MGs. We show that our algorithm provides comparable sublinear regret to the existing works.
  arXiv  Detail & Related papers  (2023-10-10T01:39:04Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.