Edge computing is a promising technology that offers a superior user experience and enables various innovative Internet of Things applications. In this paper, we present a mixed-integer linear programming (MILP) model for optimal edge server placement and workload allocation, which is known to be NP-hard. To this end, we explore the possibility of addressing this computationally challenging problem using quantum computing. However, existing quantum solvers are limited to solving unconstrained binary programming problems. To overcome this obstacle, we propose a hybrid quantum-classical solution that decomposes the original problem into a quadratic unconstrained binary optimization (QUBO) problem and a linear program (LP) subproblem. The QUBO problem can be solved by a quantum solver, while the LP subproblem can be solved using traditional LP solvers. Our numerical experiments demonstrate the practicality of leveraging quantum supremacy to solve complex optimization problems in edge computing.
Edge computing is a promising technology that offers a superior user experience and enables various innovative Internet of Things applications. In this paper, we present a mixed-integer linear programming (MILP) model for optimal edge server placement and workload allocation, which is known to be NP-hard. To this end, we explore the possibility of addressing this computationally challenging problem using quantum computing. However, existing quantum solvers are limited to solving unconstrained binary programming problems. To overcome this obstacle, we propose a hybrid quantum-classical solution that decomposes the original problem into a quadratic unconstrained binary optimization (QUBO) problem and a linear program (LP) subproblem. The QUBO problem can be solved by a quantum solver, while the LP subproblem can be solved using traditional LP solvers. Our numerical experiments demonstrate the practicality of leveraging quantum supremacy to solve complex optimization problems in edge computing.
Edge computing is a promising technology that offers a superior user experience and enables various innovative Internet of Things applications. In this paper, we present a mixed-integer linear programming (MILP) model for optimal edge server placement and workload allocation, which is known to be NP-hard. To this end, we explore the possibility of addressing this computationally challenging problem using quantum computing. However, existing quantum solvers are limited to solving unconstrained binary programming problems. To overcome this obstacle, we propose a hybrid quantum-classical solution that decomposes the original problem into a quadratic unconstrained binary optimization (QUBO) problem and a linear program (LP) subproblem. The QUBO problem can be solved by a quantum solver, while the LP subproblem can be solved using traditional LP solvers. Our numerical experiments demonstrate the practicality of leveraging quantum supremacy to solve complex optimization problems in edge computing.
Edge computing holds significant potential to revolutionize computation by providing rapid and widely accessible services to numerous devices at the network edge. For service providers, efficient service placement and workload allocation are critical to minimizing operational costs while ensuring high-quality user experiences. In this work, we formulate this problem as a mixed-integer linear program (MILP), which is computationally challenging due to its NP-hard nature. To address this, we propose an innovative hybrid quantum-classical algorithm that integrates recent advances in quantum computing with the Benders decomposition method. Specifically, the MILP is decomposed into a master problem, which, after a series of transformations, can be solved using a quantum annealer, and a linear programming subproblem handled by a classical solver. These two problems are iteratively updated and solved, with information exchanged between the quantum and classical solvers, until convergence is achieved. Numerical experiments validate the effectiveness and computational advantages of the proposed method, demonstrating its practical applicability to real-world edge computing scenarios.
Quantum computing (QC) is emerging as a new computing resource that could be superior to conventional computing (CC) for certain classes of optimization problems. However, in principle QC can only solve unconstrained binary programming problems, while mixed-integer linear programming (MIP) is of most interest in practice. We attempt to bridge the gap between the capability of QC and real-world applications by developing a new approach for MIP. The idea is decomposing the MIP into binary programming and linear programming (LP) problems, which are respectively solved by QC and conventional computing. We formalize a decomposition approach that ensures that with a sufficient number of back and forth iterations, the algorithm can reach the optimal solution of the original MIP problem. The algorithm is tested on a 2000Q D-Wave quantum processing units (QPU) and is shown to be effective for small-scaled test cases.
Quantum computing is emerging as a new computing resource that could be superior to conventional computing for certain classes of optimization problems. However, in principle, most existing approaches to quantum optimization are intended to solve unconstrained binary programming problems, while mixed-integer linear programming is of most interest in practice. We attempt to bridge the gap between the capability of quantum computing and real-world applications by developing a new approach for mixed-integer programming. The approach applies Benders decomposition to decompose the mixed-integer programming into binary programming and linear programming sub-problems, which are solved by a noisy intermediate-scale quantum processor and conventional processor, respectively. The algorithm is provably able to reach the optimal solution of the original mixed-integer programming problem. The algorithm is tested on a D-Wave 2000Q quantum processing unit and is shown to be effective for small-scaled test cases. We also test the algorithm on a mixed-integer programming inspired by power system applications. Many insights are drawn from the numerical results for both the capabilities and limitations of the proposed algorithm.
The core of this article is to construct an effective QUBO model to solve the problem of cloud edge end computing resource allocation, including two key scenarios: optimization of server maximum computing demand coverage and optimization of cloud edge server computing network layout. Each scenario provides a detailed description of the model's process from analysis, establishment to solution, overcoming several major difficulties in establishing a QUBO model, including using binary variables to express the objective function, transforming the objective function into QUBO expressions, and transforming inequality constraints. A scheme for the number of constraint relaxation factors is introduced, which effectively reduces the number of quantum bits and computational complexity. Finally, statistical analysis of the solution results, non parametric testing based on data characteristics, and detailed analysis are conducted, demonstrating the potential application of the QUBO model and quantum computing in dealing with complex combinatorial optimization problems. During the solving process, China's first optical quantum computing power cloud platform and corresponding quantum computing library Kaiwu SDK were utilized for research. Multiple solvers were used and their performance was compared to select the best performing taboo search solver, and then detailed results were calculated. The final results were fully visualized to make them more intuitive. The results indicate that quantum computing can provide an efficient, accurate, and stable solution for cloud edge end computing resource allocation. Through these studies, this article not only confirms the efficiency of quantum computing in solving specific optimization problems, but also provides some experience and reference for exploring the application of quantum computing in a wider field.
Mixed Integer Linear Programming (MILP) can be considered the backbone of the modern power system optimization process, with a large application spectrum, from Unit Commitment and Optimal Transmission Switching to verifying Neural Networks for power system applications. The main issue of these formulations is the computational complexity of the solution algorithms, as they are considered NP-Hard problems. Quantum computing can give a direct solution to this problem, as it has been experimentally shown that it can provide significant speedups in solving MILPs. In this work, we present a general framework for solving power system optimization problems with a Quantum Computer (QC), which leverages mathematical tools and QCs' sampling ability to provide accelerated solutions. Our guiding applications are the optimal transmission switching and the verification of neural networks trained to solve a DC Optimal Power Flow. Specifically, using an accelerated version of Benders Decomposition , we split a given MILP into an Integer Master Problem and a linear Subproblem and solve it through a hybrid ``quantum-classical'' approach, getting the best of both worlds. We provide 2 use cases, and benchmark the developed framework against other classical and hybrid methodologies, to demonstrate the opportunities and challenges of hybrid quantum-classical algorithms for power system mixed integer optimization problems.