In this paper, a methodology for finding the optimal solution by building a QUBO (Quadratic Unconstrained Binary Optimisation) model and using a combination of the Simulated Annealing algorithm and the CIM (Coherent Equivalent Machine) simulator in the Open Matter SDK will be presented. Firstly, the QUBO model was chosen because of its significant advantages in dealing with logical inference and combinatorial optimisation problems. The QUBO model provides an efficient solution method by transforming the problem into a quadratic unconstrained binary optimisation problem. In solving this problem, the first step is to define the objective and constraints of the problem, where the objective is to satisfy the relevant requirements and make the best of them, and the constraints are the relevant parameters provided by the data, and to build a mathematical model that matches the QUBO model. Next, a simulated annealing algorithm and a CIM simulator were used to solve this QUBO problem. By combining the QUBO model with these two algorithms, the optimal solution can be searched efficiently. Finally, the optimal solution is derived from the solution results. These scenarios not only satisfy the constraints but also achieve the given objective by optimising the combination of decision variables.
In this paper, a methodology for finding the optimal solution by building a QUBO (Quadratic Unconstrained Binary Optimisation) model and using a combination of the Simulated Annealing algorithm and the CIM (Coherent Equivalent Machine) simulator in the Open Matter SDK will be presented. Firstly, the QUBO model was chosen because of its significant advantages in dealing with logical inference and combinatorial optimisation problems. The QUBO model provides an efficient solution method by transforming the problem into a quadratic unconstrained binary optimisation problem. In solving this problem, the first step is to define the objective and constraints of the problem, where the objective is to satisfy the relevant requirements and make the best of them, and the constraints are the relevant parameters provided by the data, and to build a mathematical model that matches the QUBO model. Next, a simulated annealing algorithm and a CIM simulator were used to solve this QUBO problem. By combining the QUBO model with these two algorithms, the optimal solution can be searched efficiently. Finally, the optimal solution is derived from the solution results. These scenarios not only satisfy the constraints but also achieve the given objective by optimising the combination of decision variables.
This paper analyzes the equipment configuration of the smart mine, builds the corresponding Quadratic Unconstrained Binary Optimization (QUBO) model according to different application scenarios, and analyzes and solves the QUBO model by using the simulated annealing solver and the CIM simulator, to explore the optimal operation scheme of the smart mine under different scenarios. Firstly, under the budget constraint, the objective function is to maximize the sum of the discounted long-term profits of various excavators, and at the same time to meet the constraints such as budget limitation and type limitation, the mathematical model is established and transformed into the QUBO model, and then analytically solved to derive the optimal operation plan of the smart mine under this scenario. Subsequently, the mathematical model is reconstructed to derive the optimal operation scenario and expected profit, taking into account the factor of years of life. In terms of the solution method, kaiwu sdk shows good performance for small-scale problems, but it is limited by memory and less effective when facing large-scale problems. Therefore, this paper proposes the subQUBO method, which combines quantum and classical computing, as a potential improvement path. This study not only provides an optimization solution for the operation of smart mines, but also provides new ideas for solving similar large-scale optimization problems.
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.
Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu's Digital Annealer (DA) and D-Wave's Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum. We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.
Combinatorial optimization problems are of great significance in many fields, and this paper explores the application of quantum annealing-based QUBO (Quadratic Unconstrained Binary Optimization) model to combinatorial optimization problems, including the 0/1 knapsack problem, the traveler's problem, the maximum cut problem, and the graph coloring problem. The quantum annealing algorithm can effectively avoid falling into local optimal solutions by virtue of its unique quantum tunneling advantage, and shows significant advantages in solving complex combinatorial optimization problems, especially in dealing with large-scale data and multiple constraints, quantum annealing provides an efficient solution.
Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu’s Digital Annealer (DA) and D-Wave’s Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum.We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.
Recent advances in quantum computing have shown great potential for solving combinatorial optimization problems. A notable example is the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum-inspired algorithms require Quadratic Unconstrained Binary Optimization (QUBO) formulations. Transforming constrained optimization into QUBO impacts the algorithms' speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess them by using Simulated Annealing (SA), and find that three of our approaches outperform existing methods in terms of execution time as well as quality and quantity of feasible solutions found. Also, we tested these transformations on a quantum annealer, which was unable to solve even small instances, due to limitations in connectivity and error rates. In general, our results highlight the advantages of the new approaches, which reduce the number of variables in the QUBO representation.