A QUBO model-based approach for solving the computational resource allocation problem and its application analysis

Ming Chi

doi:10.54097/ccmkw312

Authors

Ming Chi

DOI:

https://doi.org/10.54097/ccmkw312

Keywords:

QUBO model, computational resource allocation, simulated annealing algorithm, CIM simulator, optimal path problem.

Abstract

This paper discusses the solution method of the computational resource allocation problem based on the QUBO model, and analyzes the application in combination with the simulated annealing algorithm and the CIM simulator. The reasons for choosing the QUBO model and its advantages in logical reasoning are first introduced, and then the core principles of the QUBO model are analyzed, including its relationship with quadratic unconstrained optimization problems. Then the principles of simulated annealing algorithm and CIM simulator and their applications in problem solving are discussed in detail. In terms of specific problem solving, taking the optimal position of base station setting and the optimal path of overhauling as examples, the problem definition, decision variables, the establishment of QUBO model, and the solving process are described respectively, and the solving process is demonstrated through flowcharts. Finally, the solution results of the base station setup and maintenance path problems are given and the model is evaluated.

Downloads

Download data is not yet available.

References

Wang Y, Li Y, Guo J, et al. Application-Aware Resource Allocation Based on Benefit-Cost Ratio in Computing Power Network with Heterogeneous Computing Resources [J]. Photonics, 2023, 10 (11).

J. Yang. Research on the theory and application of hybrid quantum optimization algorithm [D]. Chongqing University, 2009.

Liu Chang. A quantum approximation algorithm for solving constrained optimization problems [D]. Anhui University of Technology, 2022. DOI: 10.27790/d. cnki. gahgy. 2022. 000445.

Xin Zhang. Optimality conditions and combinatorial quadratic maximization problem of unconstrained optimization [D]. Beijing University of Posts and Telecommunications, 2011.

DU Weilin, LI Bin, TIAN Yu. Progress of quantum annealing algorithm [J]. Computer Research and Development, 2008, (09): 1501 - 1508.

ZHANG Zhiping, ZHOU Shude. Research on intelligent optimization methods based on quantum computing [C]// Signal Processing Expert Committee of China High-Tech Industrialization Research Association. Proceedings of the Sixth National Academic Conference on Signal and Intelligent Information Processing and Application. Air Force Command College; Institute of Electronic Science; 2012: 4.

YU Zhichao, LI Yangzhong, LIU Lei, et al. Survey of Simulation and Optimization Methods for Quantum Computing [J]. Computer Engineering, 2022, 48 (01): 1-11. DOI: 10.19678/j.issn.1000 - 3428.0061787.

Fred G, Gary K, Rick H, et al. Quantum bridge analytics I: a tutorial on formulating and using QUBO models [J]. Annals of Operations Research, 2022, 314 (1): 141 - 183.

Ryota Y, Koji N, Yasuaki I, et al. GPU-accelerated scalable solver with bit permutated cyclic-min algorithm for quadratic unconstrained binary optimization [J]. Journal of Parallel and Distributed Computing, 2022, 167 109 - 122.

Tadayoshi M, Masato T, Tadashi K. Application of QUBO solver using black-box optimization to structural design for resonance avoidance. [J]. Scientific reports, 2022, 12 (1): 12143 - 12143.