Quantum annealing (QA) can be used to efficiently solve quadratic unconstrained binary optimization (QUBO) problems. Grid partitioning (GP), which is a classic NP-hard integer programming problem, can potentially be solved much faster using QA. However, inequality constraints in the GP optimization model are difficult to handle. In this study, a novel solution framework based on QA is proposed for GP problems. The integer slack (IS) and binary expansion methods are applied to transform GP problems into QUBO problems. Instead of introducing continuous variables in traditional slack methods, the proposed IS method can avoid complex iteration processes when using QA. The case study demonstrates that the IS method obtains accurate feasible solutions with less calculation time.
Quantum annealing (QA) can be used to efficiently solve quadratic unconstrained binary optimization (QUBO) problems. Grid partitioning (GP), which is a classic NP-hard integer programming problem, can potentially be solved much faster using QA. However, inequality constraints in the GP optimization model are difficult to handle. In this study, a novel solution framework based on QA is proposed for GP problems. The integer slack (IS) and binary expansion methods are applied to transform GP problems into QUBO problems. Instead of introducing continuous variables in traditional slack methods, the proposed IS method can avoid complex iteration processes when using QA. The case study demonstrates that the IS method obtains accurate feasible solutions with less calculation time.
As more and more controllable devices equiped in the smart grid, the inceasing scale of binary virables brings time-consuming dimension explosion problems to traditional optimizations problems. As a parallel computing method, quantum computing is valuable for exploration to accelerate the optimization computation. The classic quantum annealer (QA) only can be used for quadratic unconstraint binary optimization (QUBO) problems. This paper is to explore a novel algorithm based on the quantum annealer for grid partition problems. It is a typical large-scale Integer Quadratic Programming (IQP) problems. The proposed quantum algorithm attemped to apply Lagrangian relaxation (LR) and alternating direction method of multipliers (ADMM), to transform an IQP problem to general format of QUBO problems. Some numerical cases of the grid partition are discussed to compare the performance of the proposed algorithm with some typical methods, thus verifing the feasibility and performance of this ADMM-QA algorithm.
Quantum annealing is an optimization technique that uses quantum fluctuation effects to search for solutions and is being applied as a metaheuristic method. Quantum annealing solves a problem expressed as quadratic unconstrained binary optimization (QUBO). Many practical problems have complex constraints, and formulating them can lead to third-order or higher expressions. In such cases, higher-order expressions have been converted to QUBO by order reduction. Various order reduction methods have been used, but they have issues, such as the need to add more auxiliary variables and difficulty in obtaining optimal solutions. This paper discusses a method for formulating problems with complex constraints using inequalities. In this approach, each constraint is defined as a linear function and added together to form an inequality. The inequality is then transformed to QUBO by introducing a slack variable. The application to the quantum minimum fill-in algorithm, a fill-in reduction ordering algorithm for sparse matrices, and the maximum satisfiability problem are also presented. The results of solving these problems with a quantum-inspired annealing machine show that higher-quality solutions are obtained with fewer variables than when using higher-order expressions with order reduction.
Quantum computing approaches, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), have emerged as promising candidates for solving combinatorial optimization problems. Since these approaches typically work with Quadratic Unconstrained Binary Optimization (QUBO) problems, constraints, when present, are commonly encoded as penalty terms. Conventional approaches to incorporate inequality constraints into QUBO formulations additionally require the introduction of slack variables, increasing the required number of qubits. The Knapsack and Bin Packing problems are optimization problems with such inequality constraints. We show that the number of slack variables required to formulate the Knapsack problem as a QUBO problem can be reduced using certain properties specific to this problem. Moreover, we present two separate strategies for the Knapsack and Bin Packing problems that avoid using the costly slack variables altogether. Instead, both strategies solve several QUBO problems, with varying penalty constants, such that at least one of them is a good representation of the given optimization problem. Numerical simulations of QAOA, as well as experiments on a D-Wave quantum annealer, show that these slack-less approaches can improve performance compared to the conventional slack variable method (in terms of success probability), even when the latter is allowed to vary penalty constants too.
Quantum annealers offer an efficient way to compute high quality solutions of NP-hard problems when expressed in a QUBO (quadratic unconstrained binary optimization) or an Ising form. This is done by mapping a problem onto the physical qubits and couplers of the quantum chip, from which a solution is read after a process called quantum annealing. However, this process is subject to multiple sources of biases, including poor calibration, leakage between adjacent qubits, control biases, etc., which might negatively influence the quality of the annealing results. In this work, we aim at mitigating the effect of such biases for solving constrained optimization problems, by offering a two-step method, and apply it to Graph Partitioning. In the first step, we measure and reduce any biases that result from implementing the constraints of the problem. In the second, we add the objective function to the resulting bias-corrected implementation of the constraints, and send the problem to the quantum annealer. We apply this concept to Graph Partitioning, an important NP-hard problem, which asks to find a partition of the vertices of a graph that is balanced (the constraint) and minimizes the cut size (the objective). We first quantify the bias of the implementation of the constraint on the quantum annealer, that is, we require, in an unbiased implementation, that any two vertices have the same likelihood of being assigned to the same or to different parts of the partition. We then propose an iterative method to correct any such biases. We demonstrate that, after adding the objective, solving the resulting bias-corrected Ising problem on the quantum annealer results in a higher solution accuracy.
Quantum annealing is a model for quantum computing that is aimed at solving hard optimization problems by representing them as quadratic unconstrained binary optimization (QUBO) problems. Although many NP-hard problems can easily be formulated as binary-variable problems with a quadratic objective function, such formulations typically also include constraints, which are not allowed in a QUBO. Hence, such constraints are usually incorporated in the objective function as additive penalty terms. While there is substantial previous work on implementing linear equality constraints, the case of inequality constraints has not much been studied. In this paper, we propose a new approach for formulating and embedding inequality constraints as penalties and describe early implementation results.
Stochastic Unit Commitment (SUC) has been proposed to manage the uncertainties driven by renewable integration, but it leads to significant computational complexity. When accelerated by Benders Decomposition (BD), the master problem becomes binary integer programming, which is still NP-hard and computationally demanding for classical methods. Quantum Annealing (QA), known for efficiently solving Quadratic Unconstrained Binary Optimization (QUBO) problems, presents a potential solution. However, existing quantum algorithms rely on slack variables to handle linear binary inequality constraints, leading to increased qubit consumption and reduced computational efficiency. To solve the problem, this paper introduces the Powell-Hestenes-Rockafellar Augmented Lagrangian Multiplier (PHR-ALM) method to eliminate the need for slack variables, making qubit consumption independent of the increasing number of Benders cuts. To further reduce the qubit overhead, quantum ADMM is applied to break large-scale SUC into smaller blocks for sequential solutions, which does not scale with the number of generators. Finally, the simulation results on both 4-generator and the IEEE bus-118 systems demonstrate the feasibility and scalability of the proposed algorithm, indicating its superior qubit and runtime efficiency over classical and baseline quantum approaches on the D-Wave QPU platform.