Fully and partially distributed Quantum Generalized Benders Decomposition for Unit Commitment Problems

• URL: http://arxiv.org/abs/2210.06678v2
• Date: Sun, 15 Dec 2024 03:27:36 GMT
• Title: Fully and partially distributed Quantum Generalized Benders Decomposition for Unit Commitment Problems
• Abstract summary: Hybrid quantum-classical generalized Benders decomposition (GBD) algorithms are proposed to address unit commitment (UC) problems.<n>In the centralized approach, the quantum GBD transforms the master problem (MP) into a quadratic unconstrained binary optimization form suitable for quantum computing.<n>For distributed systems, the distributed consensus quantum GBD employs an average consensus strategy to reformulate subproblems into local subproblems.
• Score: 12.20904743817675
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A series of hybrid quantum-classical generalized Benders decomposition (GBD) algorithms are proposed to address unit commitment (UC) problems under centralized, distributed, and partially distributed frameworks. In the centralized approach, the quantum GBD transforms the master problem (MP) into a quadratic unconstrained binary optimization form suitable for quantum computing. For distributed systems, the distributed consensus quantum GBD employs an average consensus strategy to reformulate subproblems into local subproblems. By leveraging the dual information, local cutting planes are constructed to decompose the MP into local master problems (LMPs). This approach reduces the qubit overhead and addresses the partitioning requirements. The consensus-inspired quantum GBD (CIQGBD) and its partially distributed variant, D-CIQGBD are proposed based on optimizing the allocation of relaxation variables directly, the algorithms construct more rational cutting planes, thereby enhancing the minimum eigenenergy gap of the system Hamiltonian during quantum annealing and improving the computational efficiency. Extensive experiments under various UC scenarios validate the performance of the above-mentioned hybrid algorithms. Compared to the classical solver Gurobi, D-CIQGBD demonstrates a speed advantage in solving the security-constrained UC problem on the IEEE-RTS 24-bus system. These results provide new perspectives on leveraging quantum computing for the distributed optimization of power systems.

Related papers

• DQAOA-GPT: AI-Accelerated Distributed Quantum Optimization for Combinatorial Problems [1.0380578526859343]
  Variational quantum algorithms offer a promising route for tackling exponentially large search spaces.<n>In this work, we introduce DQAOA-GPT, a hybrid framework that integrates the distributed quantum approximate optimization algorithm (DQAOA)<n>Rather than relying on iterative variational optimization, the proposed approach uses a trained generative model to directly generate high-quality quantum circuits for the sub-problems.
  arXiv  Detail & Related papers  (2026-07-22T14:46:33Z)
• Entanglement Rate Maximization for Dual-Connectivity Wireless Quantum Networks [9.619596495371793]
  This paper investigates the problem of entanglement rate in a dual-connectivity (DC) wireless quantum network comprising multiple quantum base stations (Ss)<n>Under the DC architecture, each QU can associate with up to two QBSs, thereby enhancing resource utilization compared to conventional single-connectivity schemes.<n>An alternating optimization algorithm is developed, which decomposes the original formulation into entanglement rate allocation and association subproblems.
  arXiv  Detail & Related papers  (2026-04-05T15:07:41Z)
• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  We introduce a structure-aware framework for distributed quantum optimization.<n>We find that for a search space of size $N$, our framework achieves $O(sqrtN)$ query complexity up to processors and separator dependent factors.<n>We show that structure-aware decomposition delivers a practical path to scalable distributed quantum optimization on quantum networks.
  arXiv  Detail & Related papers  (2026-03-08T15:15:52Z)
• Joint Optimization of Model Partitioning and Resource Allocation for Anti-Jamming Collaborative Inference Systems [52.842088497389746]
  This letter focuses on an anti-jamming collaborative inference system in the presence of a malicious jammer.<n>We first analyze the effects of jamming and DNN partitioning on inference accuracy via data regression.<n>We propose an efficient alternating optimization-based algorithm, which decomposes the problem into three subproblems.
  arXiv  Detail & Related papers  (2026-03-03T03:52:52Z)
• Tensor Network Assisted Distributed Variational Quantum Algorithm for Large Scale Combinatorial Optimization Problem [19.046113542182436]
  We propose the Distributed Variational Quantum Algorithm (DVQA) for solving Combinatorial Optimization Problems (COPs)<n>A key innovation of DVQA is its use of the truncated higher-order singular value decomposition to preserve inter-variable dependencies without relying on complex long-range entanglement.<n> Empirically, DVQA achieves state-of-the-art performance in simulations and has been experimentally validated on the Wu Kong quantum computer for portfolio optimization.
  arXiv  Detail & Related papers  (2026-01-20T13:31:02Z)
• Backscatter Device-aided Integrated Sensing and Communication: A Pareto Optimization Framework [59.30060797118097]
  Integrated sensing and communication (ISAC) systems potentially encounter significant performance degradation in densely obstructed urban non-line-of-sight scenarios.<n>This paper proposes a backscatter approximation (BD)-assisted ISAC system, which leverages passive BDs naturally distributed in environments of enhancement.
  arXiv  Detail & Related papers  (2025-07-12T17:11:06Z)
• Decentralized Optimization on Compact Submanifolds by Quantized Riemannian Gradient Tracking [45.147301546565316]
  This paper considers the problem of decentralized optimization on compact submanifolds.<n>We propose an algorithm where agents update variables using quantized variables.<n>To the best of our knowledge, this is the first algorithm to achieve an $mathcalO (1/K)$ convergence rate in the presence of quantization.
  arXiv  Detail & Related papers  (2025-06-09T01:57:25Z)
• Qubit-Efficient Quantum Annealing for Stochastic Unit Commitment [4.2251752131402585]
  Unit Commitment (SUC) has been proposed to manage the uncertainties driven by the integration of renewable energy sources. This paper introduces the Powell-Hestenes-Rockafellar Augmented Lagrangian Multiplier (PHR-ALM) method to eliminate the need for slack variables. To further reduce the qubit overhead, quantum ADMM is applied to break large-scale SUC into smaller blocks and enables a sequential solution.
  arXiv  Detail & Related papers  (2025-02-21T20:15:40Z)
• Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection [3.6021182997326022]
  We formulate a Quadratic Unconstrained Binary Optimization (QUBO) problem suitable for solving using quantum computationcolorblue. The formulation aims to find communities with maximal self-sufficiency and minimal power flowing between them. We benchmark the solution quality for multiple approaches: D-Wave's hybrid quantum-classical solvers, classicals, and a branch-and-bound solver.
  arXiv  Detail & Related papers  (2024-07-09T11:44:58Z)
• Quantum Speedup of the Dispersion and Codebook Design Problems [6.735173690339397]
  Dispersion problems are optimization problems classified as NP-hard. We propose new formulations of max-sum and max-min dispersion problems that enable solutions via the Grover adaptive search (GAS) quantum algorithm.
  arXiv  Detail & Related papers  (2024-06-11T12:00:50Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• Computing Low-Entropy Couplings for Large-Support Distributions [53.00113867130712]
  Minimum-entropy coupling has applications in areas such as causality and steganography. Existing algorithms are either computationally intractable for large-support distributions or limited to specific distribution types. This work addresses these limitations by unifying a prior family of iterative MEC approaches into a generalized partition-based formalism.
  arXiv  Detail & Related papers  (2024-05-29T21:54:51Z)
• Mixed Integer Linear Programming Solver Using Benders Decomposition Assisted by Neutral Atom Quantum Processor [0.0]
  This paper presents a new hybrid classical-quantum approach to solve Mixed Linear Programming (MILP) We apply Benders decomposition (BD) to segment MILPs into a master problem (MP) and a subproblem (SP) Our MILP to QUBO conversion tightens the upper bounds of the involved continuous variables, positively impacting the required qubit count, and the convergence of the algorithm.
  arXiv  Detail & Related papers  (2024-02-08T15:33:09Z)
• Hungarian Qubit Assignment for Optimized Mapping of Quantum Circuits on Multi-Core Architectures [1.1288814203214292]
  Quantum computers are expected to adopt a modular approach, featuring clusters of tightly connected quantum bits with sparser connections between these clusters. Efficiently distributing qubits across multiple processing cores is critical for improving quantum computing systems' performance and scalability. We propose the Hungarian Qubit Assignment (HQA) algorithm, which leverages the Hungarian algorithm to improve qubit-to-core assignment.
  arXiv  Detail & Related papers  (2023-09-21T15:48:45Z)
• Near-Term Distributed Quantum Computation using Mean-Field Corrections and Auxiliary Qubits [77.04894470683776]
  We propose near-term distributed quantum computing that involve limited information transfer and conservative entanglement production. We build upon these concepts to produce an approximate circuit-cutting technique for the fragmented pre-training of variational quantum algorithms.
  arXiv  Detail & Related papers  (2023-09-11T18:00:00Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Multi-Resource Allocation for On-Device Distributed Federated Learning Systems [79.02994855744848]
  This work poses a distributed multi-resource allocation scheme for minimizing the weighted sum of latency and energy consumption in the on-device distributed federated learning (FL) system. Each mobile device in the system engages the model training process within the specified area and allocates its computation and communication resources for deriving and uploading parameters, respectively.
  arXiv  Detail & Related papers  (2022-11-01T14:16:05Z)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
  arXiv  Detail & Related papers  (2022-11-01T07:52:47Z)
• Shuffle-QUDIO: accelerate distributed VQE with trainability enhancement and measurement reduction [77.97248520278123]
  We propose Shuffle-QUDIO to involve shuffle operations into local Hamiltonians during the quantum distributed optimization. Compared with QUDIO, Shuffle-QUDIO significantly reduces the communication frequency among quantum processors and simultaneously achieves better trainability.
  arXiv  Detail & Related papers  (2022-09-26T06:51:20Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Hybrid Quantum-Classical Unit Commitment [0.0]
  This paper proposes a hybrid quantum-classical algorithm to solve a fundamental power system problem called unit commitment (UC) Using Qiskit on the IBM Q system as the simulation environment, simulation results demonstrate the validity of the proposed algorithm to solve the UC problem.
  arXiv  Detail & Related papers  (2022-01-07T01:48:58Z)
• Hybrid Quantum-Classical Multi-cut Benders Approach with a Power System Application [0.0]
  A quantum-classical (HQC) solution to the Unit Commitment (UC) problem is presented. The validity and computational viability of the proposed approach are demonstrated using the D-Wave Advantage 4.1 quantum annealer.
  arXiv  Detail & Related papers  (2021-12-10T16:16:09Z)
• Accelerating variational quantum algorithms with multiple quantum processors [78.36566711543476]
  Variational quantum algorithms (VQAs) have the potential of utilizing near-term quantum machines to gain certain computational advantages. Modern VQAs suffer from cumbersome computational overhead, hampered by the tradition of employing a solitary quantum processor to handle large data. Here we devise an efficient distributed optimization scheme, called QUDIO, to address this issue.
  arXiv  Detail & Related papers  (2021-06-24T08:18:42Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Distributed Learning and Democratic Embeddings: Polynomial-Time Source Coding Schemes Can Achieve Minimax Lower Bounds for Distributed Gradient Descent under Communication Constraints [46.17631511884969]
  We consider the problem of compressing a vector in the n-dimensional Euclidean space, subject to a bit-budget of R-bits per dimension. We show that Democratic and Near-Democratic source-coding schemes are (near) optimal in the sense that the covering efficiency of the resulting quantizer is either dimension independent, or has a very weak logarithmic dependence. We propose a distributed optimization algorithm: DGD-DEF, which employs our proposed coding strategy, and achieves the minimax optimal convergence rate to within (near) constant factors.
  arXiv  Detail & Related papers  (2021-03-13T00:04:11Z)
• Quantum Permutation Synchronization [88.4588059792167]
  We present QuantumSync, the quantum algorithm for solving a quantum vision problem in the context of computer vision. We show how to insert permutation constraints into a QUBO problem and to solve the constrained QUBO problem on the current generation of the abatic quantum DWave computer.
  arXiv  Detail & Related papers  (2021-01-19T17:51:02Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Accelerating Generalized Benders Decomposition for Wireless Resource Allocation [40.75748765274763]
  Generalized Benders decomposition (GBD) is a globally optimal algorithm for mixed integer nonlinear programming (MINLP) problems. We propose to leverage machine learning (ML) techniques to accelerate GBD aiming at decreasing the complexity of the master problem.
  arXiv  Detail & Related papers  (2020-03-03T02:11:42Z)

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.