检索结果-内蒙古大学图书馆

A I I E Transactions 2024年第2期56卷

作者： Oylum Şeker Merve Bodur Hamed Pouya Department of Mechanical and Industrial Engineering University of Toronto Toronto ON Canada

Routing and wavelength assignment with protection is an important problem in telecommunications. Given an optical network and incoming connection requests, a commonly studied variant of the problem aims to grant a maximum number of requests by assigning lightpaths with minimum network resource usage, while ensuring the provided services remain functional in the case of a single-link failure through dedicated protection paths. We consider a version where alternative lightpaths for requests are assumed to be given as a precomputed set and show that it is NP-hard. We formulate the problem as an Integer Programming (IP) model and also use it as a foundation to develop a quadratic unconstrained binary optimization (QUBO) model. We present necessary and sufficient conditions on objective function parameters to prioritize request granting objective over wavelength-link usage for both models, and a sufficient condition ensuring the exactness of the QUBO model. Moreover, we implement a problem-specific branch-and-cut algorithm for the IP model and employ a new quantum-inspired technology, Digital Annealer (DA), for the QUBO model. We conduct computational experiments on a large suite of nontrivial instances to assess the efficiency and efficacy of all of these approaches as well as two problem-specific heuristics. Although the objective penalty coefficient values that guarantee the exactness of the QUBO model were outside the acceptable range for DA, it always yielded feasible solutions even with smaller values in practice. The results show that the emerging technology DA outperforms the considered techniques coupled with GUROBI in finding mostly significantly better or as good solutions in two minutes compared to two-hour run time, whereas problem-specific heuristics fail to be competitive.

关键词： Routing and wavelength assignment quadratic unconstrained binary optimization Digital Annealer integer programming

来源：评论

学校读者我要写书评

暂无评论

quadratic unconstrained binary optimization Problem Preprocessing: Theory and Empirical Analysis

引用

NETWORKS 2017年第2期70卷 79-97页

作者： Lewis, Mark Glover, Fred Missouri Western State Univ Sch Business St Joseph MO 64507 USA Univ Colorado Sch Sci & Engn Boulder CO 80309 USA

The quadratic unconstrained binary optimization problem (QUBO) has become a unifying model for representing a wide range of combinatorial optimization problems, and for linking a variety of disciplines that face these problems. A new class of quantum annealing computer that maps QUBO onto a physical qubit network structure with specific size and edge density restrictions is generating a growing interest in ways to transform the underlying QUBO structure into an equivalent graph having fewer nodes and edges. In this article, we present rules for reducing the size of the QUBO matrix by identifying variables whose value at optimality can be predetermined. We verify that the reductions improve both solution quality and time to solution and, in the case of metaheuristic methods where optimal solutions cannot be guaranteed, the quality of solutions obtained within reasonable time limits. We discuss the general QUBO structural characteristics that can take advantage of these reduction techniques and perform careful experimental design and analysis to identify and quantify the specific characteristics most affecting reduction. The rules make it possible to dramatically improve solution times on a new set of problems using both the exact Cplex solver and a tabu search metaheuristic. (C) 2017 Wiley Periodicals, Inc.

关键词： quadratic unconstrained binary optimization binary quadratic optimization preprocessing network reduction Ising model quantum annealing

来源：评论

学校读者我要写书评

暂无评论

The quantum Ising model for perfect matching and solving it with variational quantum eigensolver

引用

Science China(Information Sciences) 2024年第9期67卷 306-320页

作者： Qilin ZHENG Pingyu ZHU Chao WU Miaomiao YU Weihong LUO Ping XU Institute for Quantum Information and State Key Laboratory of High Performance Computing College of Computer Science and Technology National University of Defense Technology Hefei National Laboratory

Obtaining all perfect matchings of a graph is a tough problem in graph theory, and its complexity belongs to the #P-Complete class. The problem is closely related to combinatorics, marriage matching problems, dense subgraphs, the Gaussian boson sampling, chemical molecular structures, and dimer *** this paper, we propose a quadratic unconstrained binary optimization formula of the perfect matching problem and translate it into the quantum Ising model. We can obtain all perfect matchings by mapping them to the ground state of the quantum Ising Hamiltonian and solving it with the variational quantum eigensolver. Adjusting the model's parameters can also achieve the maximum or minimum weighted perfect matching. The experimental results on a superconducting quantum computer of the Origin Quantum Computing Technology Company show that our model can encode 2~n dimensional optimization space with only O（n） qubits consumption and achieve a high success probability of the ground state corresponding to all perfect matchings. In addition, the further simulation results show that the model can support a scale of more than 14 qubits, effectively resist the adverse effects of noise, and obtain a high success probability at a shallow variational depth. This method can be extended to other combinatorial optimization problems.

关键词： perfect matching Ising model quantum Hamiltonian variational quantum eigensolver quadratic unconstrained binary optimization

来源：评论

学校读者我要写书评

暂无评论

Solving the Minimum Sum Coloring Problem: Alternative Models, Exact Solvers, and Metaheuristics

引用

INFORMS JOURNAL ON COMPUTING 2025年第2期37卷 197-502, C2页

作者： Du, Yu Glover, Fred Kochenberger, Gary Hennig, Rick Wang, Haibo Hulandageri, Amit Univ Colorado Business Sch Denver CO 80102 USA Entanglement Inc Boulder CO 80305 USA Texas A&M Int Univ Sanchez Sch Business Laredo TX 78040 USA

The minimum sum coloring problem (MSCP), a well-known NP-hard (nondeterministic polynomial time) problem with important practical applications, has been the subject of several papers in recent years. Because of the computational challenge posed by these problems, most solution methods employed are metaheuristics designed to find high-quality solutions with no guarantee of optimality. Exact methods (like Gurobi) and metaheuristic solvers have greatly improved in recent years, enabling high-quality and often optimal solutions to be found to a growing set of MSCPs. Alternative model forms can have a significant impact on the success of exact and heuristic methods in such settings, often providing enhanced performance compared with traditional model forms. In this paper, we introduce several alternative models for MSCP, including the quadratic unconstrained binary problem plus (QUBO-Plus) model for solving problems with constraints that are not folded into the objective function of the basic quadratic unconstrained binary problem (QUBO) model. We provide a computational study using a standard set of test problems from the literature that compares the general purpose exact solver from Gurobi with the leading QUBO metaheuristic solver NGQ and a special solver called Q-Card that belongs to the QUBO-Plus class. Our results highlight the effectiveness of the QUBO and QUBO-Plus models when solved with these metaheuristic solvers on this test bed, showing that the QUBO-Plus solver Q-Card provides the best performance for finding high-quality solutions to these important problems.

关键词： minimum sum coloring problem metaheuristics combinatorial optimization quadratic unconstrained binary optimization constraint programming

来源：评论

学校读者我要写书评

暂无评论

Quantum annealing algorithm for interval uncertainty propagation analysis in structural free vibration

引用

STRUCTURES 2025年 71卷

作者： Zhu, Jiazheng Wang, Xiaojun Wang, Zhenghuan Xu, Yusheng Beihang Univ Inst Solid Mech Sch Aeronaut Sci & Engn Natl Key Lab Strength & Struct Integr Beijing 100191 Peoples R China

Quantum annealing has emerged as a focal point of research in the engineering field, celebrated for its unparalleled computational acceleration capabilities. The inherent uncertainties within structures and the intricate nature of dynamic problems call for a nuanced approach to this cutting-edge technology. This article unveils a quantum annealing-based method for propagating interval uncertainties, crafted to refine the handling of uncertain phenomena in traditional engineering domains. The proposed method initiates with the exploration of natural vibration challenges in discrete structures, setting the stage for a novel transformation relationship between qubits and uncertainty variables. By harnessing this relationship, we crafted a sophisticated quadratic unconstrained binary optimization model, thereby paving the way for leveraging quantum annealing techniques in dissecting interval uncertainty variables. The robustness of this innovative approach was rigorously validated through a series of numerical experiments executed on the state-of-the-art D-Wave platform.

关键词： Quantum annealing Uncertainty propagation quadratic unconstrained binary optimization Free vibration D -Wave

来源：评论

学校读者我要写书评

暂无评论

QUBO Formulations and Characterization of Penalty Parameters for the Multi-Knapsack Problem

引用

IEEE ACCESS 2025年 13卷 47086-47098页

作者： Guney, Evren Ehrenthal, Joachim Hanne, Thomas MEF Univ Dept Ind Engn TR-34396 Istanbul Turkiye Univ Appl Sci & Arts Northwestern Switzerland FHNW Inst Business Informat Syst Sch Business CH-5210 Windisch Switzerland

The Multi-Knapsack Problem (MKP) is a fundamental challenge in operations research and combinatorial optimization. Quantum computing introduces new possibilities for solving MKP using quadratic unconstrained binary optimization (QUBO) models. However, a key challenge in QUBO formulations is the selection of penalty parameters, which directly influence solution feasibility and algorithm performance. In this work, we develop QUBO formulations for two MKP variants-the Multidimensional Knapsack Problem (MDKP) and the Multiple Knapsack Problem (MUKP)-and provide an algebraic characterization of their penalty parameters. We systematically evaluate their impact through quantum simulation experiments and compare the performance of the two leading quantum optimization approaches: Quantum Approximate optimization Algorithm (QAOA) and quantum annealing, alongside a state-of-the-art classical solver. Our results indicate that while classical solvers remain superior, careful tuning of penalty parameters has a strong impact on quantum optimization outcomes. QAOA is highly sensitive to parameter choices, whereas quantum annealing produces more stable results on small to mid-sized instances. Further, our results reveal that MDKP instances can maintain feasibility at penalty values below theoretical bounds, while MUKP instances show greater sensitivity to penalty reductions. Finally, we outline directions for future research in solving MKP, including adaptive penalty parameter tuning, hybrid quantum-classical approaches, and practical optimization strategies for QAOA, as well as real-hardware evaluations.

关键词： optimization Quantum computing Logic gates Quantum annealing Annealing Qubit Noise Approximation algorithms Tuning Quantum state Multi-dimensional knapsack problem multiple knapsack problem quadratic unconstrained binary optimization quantum annealing quantum approximate optimization algorithm penalty parameters

来源：评论

学校读者我要写书评

暂无评论

Qoolchain: A QUBO Preprocessing Toolchain for Enhancing Quantum optimization

引用

ADVANCED QUANTUM TECHNOLOGIES 2025年第5期8卷

作者： Orlandi, Giacomo Volpe, Deborah Graziano, Mariagrazia Turvani, Giovanna Politecn Torino Dept Elect & Telecommun I-10129 Turin Italy Dept Appl Sci & Technol I-10129 Turin Italy

Solving combinatorial optimization problems is crucial in research and industry but still challenging since these problems are usually NP-hard or NP-complete. Classical solvers struggle with their non-polynomial complexity. Although heuristic algorithms are widely used, they often fall short in execution time and accuracy, increasing the interest in quantum computing alternatives using quadratic unconstrained binary optimization (QUBO) formulations. However, current Noisy Intermediate-Scale Quantum (NISQ) computers and future early fault-tolerant quantum devices face limitations in qubit availability and circuit depth, necessitating preprocessing to reduce problem complexity. This study introduces Qoolchain, a QUBO preprocessing toolchain designed to reduce problem size and enhance solver performance. Developed in Cython, Qoolchain is compatible with major quantum frameworks and optimized for the Grover Adaptive Search (GAS) algorithm. It includes steps like persistency identification, decomposition, and probing to estimate function bounds, all with polynomial complexity. Qoolchain also proposes using the Grover Search algorithm for problem segments whose optimal value is known a priori from graph theory and Shannon decomposition to reduce QUBO problem complexity further. Evaluated against the D-Wave preprocessing toolchain on various problems, Qoolchain demonstrates higher efficiency and accuracy. It represents a significant advancement in enabling practical quantum solvers, addressing hardware limitations, and solving complex industry-relevant problems.

关键词： grover adaptive search grover search preprocessing quantum computing quadratic unconstrained binary optimization

来源：评论

学校读者我要写书评

暂无评论

Integrating quantum computing into building-to-grid control framework: Application of benders decomposition in mixed-integer nonlinear programming

引用

BUILDING SIMULATION 2025年第5期18卷 1163-1178页

作者： Deng, Zhipeng Wang, Xuezheng Dong, Bing Univ Cent Florida Coll Engn & Comp Sci Dept Mech & Aerosp Engn Orlando FL USA Syracuse Univ Dept Mech & Aerosp Engn Syracuse NY 13244 USA

Buildings use a large amount of energy in the United States. It is important to optimally manage and coordinate the resources across building and power distribution networks to improve overall efficiency. Optimizing the power grid with discrete variables was very challenging for traditional computers and algorithms, as it is an NP-hard problem. In this study, we developed a new optimization solution based on quantum computing for BTG integration. We first used MPC for building loads connected with a commercial distribution grid for cost reduction. Then we used discretization and Benders Decomposition methods to reformulate the problem and decompose the continuous and discrete variables, respectively. We used D-Wave quantum computer to solve dual problems and used conventional algorithm for primal problems. We applied the proposed method to an IEEE 9-bus network with 3 commercial buildings and over 300 residential buildings to evaluate the feasibility and effectiveness. Compared with traditional optimization methods, we obtained similar solutions with some fluctuations and improved computational speed from hours to seconds. The time of quantum computing was greatly reduced to less than 1% of traditional optimization algorithm and software such as MATLAB. Quantum computing has proved the potential to solve large-scale discrete optimization problems for urban energy systems.

关键词： smart grid model predictive control IEEE 9-bus quadratic unconstrained binary optimization quantum annealing

来源：评论

学校读者我要写书评

暂无评论

Combinatorial optimization with quantum computers

引用

ENGINEERING optimization 2025年第1期57卷 208-233页

作者： Chicano, Francisco Luque, Gabiel Dahi, Zakaria Abdelmoiz Gil-Merino, Rodrigo Univ Malaga ITIS Software Malaga Spain Univ Lille BONUS Res Team CNRS Inria Lille France Int Univ Rioja UNIR Sch Engn & Technol Logrono Spain

Quantum computers leverage the principles of quantum mechanics to do computation with a potential advantage over classical computers. Though a single classical computer transforms one particular binary input into an output after applying one operator to the input, a quantum computer can apply the operator to a superposition of binary strings to provide a superposition of binary outputs, performing computations apparently in parallel. This feature allows quantum computers to speed up the computation compared to classical algorithms. Unsurprisingly, quantum algorithms have been proposed to solve optimization problems in quantum computers. Furthermore, a family of quantum machines called quantum annealers is specially designed to solve optimization problems. This article provides an introduction to quantum optimization from a practical point of view. It introduces the reader to the use of quantum annealers and quantum gate-based machines to solve optimization problems.

关键词： Quantum optimization quantum computing quantum annealer quadratic unconstrained binary optimization

来源：评论

学校读者我要写书评

暂无评论

A conflict clique mitigation method for large-scale satellite mission planning based on heterogeneous graph learning

引用

ADVANCED ENGINEERING INFORMATICS 2024年 62卷

作者： Feng, Xiaoen Xu, Minqiang Li, Yuqing Harbin Inst Technol Deep Space Explorat Res Ctr Harbin 150001 Peoples R China

For the large-scale and intensive demands of satellite remote sensing observation, the complexity of constraint relationships grows explosively with expansion of satellite task scale. How to efficiently deal with the complex and temporal varying constraint conflicts, and mine the implicit knowledge existing among satellite mission constraints, which is significant to enhance scheduling efficiency, however, is also a core difficulty in the satellite scheduling problem. In this paper, we propose a conflict clique mitigation method based on dynamic taskconstrained heterogeneous graph learning to solve large-scale satellite mission scheduling. The method exploits the advantage of heterogeneous graphs to characterize multiple unstructured relationships, and projects the temporal-varying features of constraint conflicts to the spatial topology of multiple nodes and edges in a heterogeneous graph. Thus, a dynamic constraints heterogeneous graph model for satellite tasks based on sampling critical conflict cliques is developed. And an improved heterogeneous attention network with quadratic unconstrained binary optimization (HAN-QUBO) is proposed, which is able to deal with the heterogeneous graphs and attempts to represent the implicit principles of multiple constraints of satellite missions, so that the valuable strategies and experiences of conflict mitigation can be extracted. The simulation experiments demonstrate that the method can provide effective empirical guidance for multi-satellite scheduling, greatly relieve the pressure of cumbersome constraint conflict checking process for large-scale tasks. The average number of conflict resolutions has been reduced by about 73.48 % for EOSSPs with tens of thousands tasks, while the quality of solutions is maintained at the same time, which significantly improves the efficiency of multisatellite scheduling.

关键词： Earth observation satellite scheduling problem (EOSSP) Large-scale multi-satellite missions Heterogeneous graph Heterogeneous attention network (HAN) quadratic unconstrained binary optimization (QUBO)

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：