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
• Authors: Fang Gao, Dejian Huang, Ziwei Zhao, Wei Dai, Mingyu Yang, Qing Gao, Yu Pan,
• 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

• 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)
• 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.