Constraint-Preserving QAOA for Personnel Rostering: Coverage-Preserving and Guarded-XY Mixer Constructions

• URL: http://arxiv.org/abs/2607.09145v1
• Date: Fri, 10 Jul 2026 06:58:45 GMT
• Title: Constraint-Preserving QAOA for Personnel Rostering: Coverage-Preserving and Guarded-XY Mixer Constructions
• Abstract summary: We develop a constraint-preserving QAOA framework for personnel rostering in which hard scheduling constraints are embedded directly into the mixer Hamiltonian.<n>To the best of our knowledge, this is the first constraint-preserving QAOA formulation for personnel rostering.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a promising framework for combinatorial optimization, but constrained problems are commonly handled using energetic penalty terms that require calibration and allow infeasible configurations to remain dynamically accessible. We develop a constraint-preserving QAOA framework for personnel rostering in which hard scheduling constraints are embedded directly into the mixer Hamiltonian. Using a binary rostering model with daily coverage and no-consecutive-duty constraints, we formulate the dynamics from a transition-graph perspective and introduce a guarded-XY mixer that confines the evolution to the fully feasible scheduling manifold. We further distinguish feasibility preservation from feasible-transition design and propose a tight-pattern extension that introduces collective feasible exchanges in saturated workload segments where local guarded exchanges alone are insufficient. Exact statevector simulations demonstrate that, compared with Penalty-X and Coverage-XY formulations under both expectation-value and Conditional Value-at-Risk optimization, the proposed approach eliminates hard-constraint penalty calibration, guarantees feasible evolution by construction, and consistently yields higher-quality output distributions with stronger concentration on optimal feasible schedules. To the best of our knowledge, this is the first constraint-preserving QAOA formulation for personnel rostering, and the transition-graph framework is readily applicable to a broad class of constrained quantum optimization problems.

Related papers

• A Hybrid Classical-Quantum Approach for Multi-Constrained Location Optimization Problem [0.19573380763700712]
  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.
  arXiv  Detail & Related papers  (2026-07-08T19:44:55Z)
• Optimality-Preserving Decomposition for Scalable QAOA in Natural-Language-Guided Multi-Drone Assignment [1.189955933770711]
  We present an end-to-end framework integrating a fine-tuned Large Language Model front-end with a highly scalable, domain-specific quantum-classical backend.<n>Our framework features a novel constraint-preserving graph partitioner and a compressed separator-based dynamic programming (DP) merge.<n> Empirical results demonstrate that this architecture circumvents classical scaling walls, recovering the global optimum on 100% of idealized cases and 96.3% under real QAOA sampling.
  arXiv  Detail & Related papers  (2026-06-12T08:31:14Z)
• 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)
• Improving Feasibility in Quantum Approximate Optimization Algorithm for Vehicle Routing via Constraint-Aware Initialization and Hybrid XY-X Mixing [2.204918347869259]
  Vehicle Routing Problem (VRP) is a core problem in logistics and transportation.<n> conventional Pauli-$X$ mixer can disrupt partial solution structures that satisfy key local constraints.<n>We propose a constraint-aware QAOA framework with two complementary components.
  arXiv  Detail & Related papers  (2026-04-08T15:39:22Z)
• Constrained Portfolio Optimization via Quantum Approximate Optimization Algorithm (QAOA) with XY-Mixers and Trotterized Initialization: A Hybrid Approach for Direct Indexing [0.0]
  This paper presents a constraint-preserving Quantum Approximate Algorithm (QAOA) formulation against Simulated Annealing (SA) and Hierarchical Risk Parity (HRP)<n>We show that our QAOA approach achieves a Sharpe Ratio of 1.81, significantly outperforming Simulated Annealing (1.31) and HRP (0.98)<n>Backtesting on a basket of 10 US equities over 2025 reveals that our QAOA approach achieves a Sharpe Ratio of 1.81, significantly outperforming Simulated Annealing (1.31) and HRP (0.98)
  arXiv  Detail & Related papers  (2026-02-16T15:19:15Z)
• Constrained Dynamic Gaussian Splatting [47.982650444869336]
  Constrained Dynamic Gaussian Splatting (CDGS) is a novel framework that formulates dynamic scene reconstruction as a budget-constrained optimization problem.<n>We show that CDGS delivers optimal rendering quality under varying capacity limits, achieving over 3x compression compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-02-03T13:53:29Z)
• Constraint-Aware Quantum Optimization via Hamming Weight Operators [1.1463843149836523]
  Constrained optimization with strict linear constraints underpins applications in drug discovery, power grids, logistics, and finance.<n>We introduce Hamming Weight Operators, a new class of constraint-aware operators that confine quantum evolution strictly within the feasible subspace.<n>We validate our approach on benchmark tasks from both finance and high-energy physics, specifically portfolio optimization and two-jet clustering with energy balance.
  arXiv  Detail & Related papers  (2026-01-04T12:58:04Z)
• Adaptive Neighborhood-Constrained Q Learning for Offline Reinforcement Learning [52.03884701766989]
  offline reinforcement learning (RL) algorithms typically impose constraints on action selection.<n>We propose a new neighborhood constraint that restricts action selection in the Bellman target to the union of neighborhoods of dataset actions.<n>We develop a simple yet effective algorithm, Adaptive Neighborhood-constrained Q learning (ANQ), to perform Q learning with target actions satisfying this constraint.
  arXiv  Detail & Related papers  (2025-11-04T13:42:05Z)
• Resilient Constrained Reinforcement Learning [87.4374430686956]
  We study a class of constrained reinforcement learning (RL) problems in which multiple constraint specifications are not identified before study. It is challenging to identify appropriate constraint specifications due to the undefined trade-off between the reward training objective and the constraint satisfaction. We propose a new constrained RL approach that searches for policy and constraint specifications together.
  arXiv  Detail & Related papers  (2023-12-28T18:28:23Z)
• Achieving Constraints in Neural Networks: A Stochastic Augmented Lagrangian Approach [49.1574468325115]
  Regularizing Deep Neural Networks (DNNs) is essential for improving generalizability and preventing overfitting. We propose a novel approach to DNN regularization by framing the training process as a constrained optimization problem. We employ the Augmented Lagrangian (SAL) method to achieve a more flexible and efficient regularization mechanism.
  arXiv  Detail & Related papers  (2023-10-25T13:55:35Z)
• 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)

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.