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

Benchmarks and Recommendations for Quantum, Digital, and GPU Annealers in Combinatorial optimization

IEEE ACCESS 2024年 12卷 125014-125031页

作者： Jiang, Jehn-Ruey Shu, Yu-Chen Lin, Qiao-Yi Natl Cent Univ Dept Comp Sci & Informat Engn Taoyuan City 32001 Taiwan Natl Cheng Kung Univ Dept Math Tainan 701401 Taiwan

Annealers leverage quadratic unconstrained binary optimization (QUBO) formulas to address combinatorial optimization problems (COPs) and have shown potential to outperform classical computers. This paper examines three prominent types of annealers: quantum, digital, and GPU annealers. Quantum annealers (QAs) are exemplified by the D-Wave Advantage, which relies on the quantum tunneling phenomenon to rapidly locate the minimum-energy system state corresponding to the optimal solution to a COP. Digital annealers (DAs) are typified by the Fujitsu Digital Annealing Unit (DAU), which is based on a quantum-inspired digital architecture to perform parallel and real-time optimization calculations to solve a COP. GPU annealers (GPUAs) are exemplified by the Compal Quantix solver, which harnesses graphics processing units (GPUs) to conduct the diverse adaptive bulk search for the optimal COP solution. This paper first provides an introductory overview of the QA, DA, and GPUA, and then proceeds to benchmark their performance on solving various well-known COPs such as the subset sum, maximum cut, vertex cover, 0/1 knapsack, graph coloring, Hamiltonian cycle, traveling salesperson, and job-shop scheduling problems. Their performance is also compared with that of state-of-the-art algorithms running on classical computers. Through comprehensive performance benchmarks in terms of the solution quality and the execution time, we identify the strengths and weaknesses of each annealer. In addition, we also provide recommendations to improve the performance of each annealer. Specifically, we recommend using the genetic algorithm, the improved particle swarm optimization algorithm, and the ant colony optimization algorithm in all annealers, using quantum pausing, quenching, and reverse annealing in the QA, using built-in separated penalty terms, one-way/two-way one-hot constraints, and linear inequality constraints in the DA, and implementing some parallel algorithms in the GPUA for perf

关键词： Annealing Quantum annealing Qubit Mathematical models optimization methods Tunneling Benchmark testing Combinatorial mathematics Graphics processing units Combinatorial optimization problem digital annealer GPU annealer quantum annealer quadratic unconstrained binary optimization

来源：评论

学校读者我要写书评

暂无评论

Faster exact solution of sparse MaxCut and QUBO problems

引用

MATHEMATICAL PROGRAMMING COMPUTATION 2023年第3期15卷 445-470页

作者： Rehfeldt, Daniel Koch, Thorsten Shinano, Yuji Zuse Inst Berlin Appl Algorithm Intelligence Methods Dept Takustr 7 D-14195 Berlin Germany TU Berlin Chair Software & Algorithms Discrete Optimizat Str 17 Juni 135 D-10623 Berlin Germany

The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems-by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.

关键词： Maximum-cut quadratic unconstrained binary optimization Branch-and-cut

来源：评论

学校读者我要写书评

暂无评论

Minor-embedding in adiabatic quantum computation: I. The parameter setting problem

引用

QUANTUM INFORMATION PROCESSING 2008年第5期7卷 193-209页

作者： Choi, Vicky D Wave Syst Inc Burnaby BC V5C 6G9 Canada

We show that the NP-hard quadratic unconstrained binary optimization (QUBO) problem on a graph G can be solved using an adiabatic quantum computer that implements an Ising spin-1/2 Hamiltonian, by reduction through minor-embedding of G in the quantum hardware graph U. There are two components to this reduction: embedding and parameter setting. The embedding problem is to find a minor-embedding G (SansSerif) of a graph G in U, which is a subgraph of U such that G can be obtained from G (SansSerif) by contracting edges. The parameter setting problem is to determine the corresponding parameters, qubit biases and coupler strengths, of the embedded Ising Hamiltonian. In this paper, we focus on the parameter setting problem. As an example, we demonstrate the embedded Ising Hamiltonian for solving the maximum independent set (MIS) problem via adiabatic quantum computation (AQC) using an Ising spin-1/2 system. We close by discussing several related algorithmic problems that need to be investigated in order to facilitate the design of adiabatic algorithms and AQC architectures.

关键词： Adiabatic quantum computation Graph minor quadratic unconstrained binary optimization Ising Hamiltonian

来源：评论

学校读者我要写书评

暂无评论

What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO

引用

INFORMS JOURNAL ON COMPUTING 2018年第3期30卷 608-624页

作者： Dunning, Iain Gupta, Swati Silberholz, John DeepMind London N1C 4AG England Georgia Inst Technol Ind & Syst Engn Atlanta GA 30332 USA Univ Michigan Ross Sch Business Ann Arbor MI 48109 USA

Though empirical testing is broadly used to evaluate heuristics, there are shortcomings with how it is often applied in practice. In a systematic review of Max-Cut and quadratic unconstrained binary optimization (QUBO) heuristics papers, we found only 4% publish source code, only 14% compare heuristics with identical termination criteria, and most experiments are performed with an artificial, homogeneous set of problem instances. To address these limitations, we implement and release as open-source a code-base of 10 Max-Cut and 27 QUBO heuristics. We perform heuristic evaluation using cloud computing on a library of 3,296 instances. This large-scale evaluation provides insight into the types of problem instances for which each heuristic performs well or poorly. Because no single heuristic outperforms all others across all problem instances, we use machine learning to predict which heuristic will work best on a previously unseen problem instance, a key question facing practitioners.

关键词： computational testing reproducible research heuristics quadratic unconstrained binary optimization Max-Cut hyper-heuristics test bed interpretable machine learning

来源：评论

学校读者我要写书评

暂无评论

Mapping structural topology optimization problems to quantum annealing

引用

STRUCTURAL AND MULTIDISCIPLINARY optimization 2024年第5期67卷 74-74页

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

Quantum computing (QC) is a rapidly growing technology in the field of computation that has garnered significant attention in recent years. This emerging technology has become particularly relevant due to the increasing complexity of optimization problems and their expanding search spaces. As a result, innovative solutions that can surpass the limitations of the current optimization paradigms executed on classic computers are becoming necessary. D-wave, a specialized quantum computer, presents a novel solution for addressing intricate optimization problems with remarkable speed advantages over traditional methods. However, a major hurdle in terms of utilizing the D-wave platform for topology optimization design is the conversion of an optimization problem into formulas that can be comprehended by a quantum annealing machine. This is because the D-wave platform is limited to solving quadratic unconstrained binary optimization problems or Ising model problems, making it necessary to find a way to adapt the task of interest to these specific types of optimization problems. This paper examines the current reality concerning the extremely limited availability of quantum computing resources. We focus on small-scale discrete structural topology optimization problems as a starting point and establish a mapping relationship between quantum bits and the cross-sectional area variables of truss elements. Utilizing this mapping, a quadratic unconstrained binary optimization model is developed with these variables. We propose a nested optimization process with dynamically adjusted cross-sectional areas, which enables the development of a quantum annealing approach for optimizing the topology of discrete variables. Our method is validated through numerical experiments, demonstrating its efficiency.

关键词： Quantum computing D-wave Structural topology optimization quadratic unconstrained binary optimization Ising model

来源：评论

学校读者我要写书评

暂无评论

Integration of Simulated Quantum Annealing in Parallel Tempering and Population Annealing for Heterogeneous-Profile QUBO Exploration

引用

IEEE ACCESS 2023年 11卷 30390-30441页

作者： Volpe, Deborah Cirillo, Giovanni Amedeo Zamboni, Maurizio Turvani, Giovanna Politecn Torino Dept Elect & Telecommun I-10129 Turin Italy

Simulated Quantum Annealing (SQA) is a heuristic algorithm which can solve quadratic unconstrained binary optimization (QUBO) problems by emulating the exploration of the solution space done by a quantum annealer. It mimics the quantum superposition and tunnelling effects through a set of correlated replicas of the spins system representing the problem to be solved and performing Monte Carlo steps. However, the effectiveness of SQA over a classical algorithm strictly depends on the cost/energy profile of the target problem. In fact, quantum annealing only performs well in exploring functions with high and narrow peaks, while classical annealing is better in overcoming flat and wide energy-profile barriers. Unfortunately, real-world problems have a heterogeneous solution space and the probability of success of each solver depends on the size of the energy profile region compatible with its exploration mechanism. Therefore, significant advantages could be obtained by exploiting hybrid solvers, which combine SQA and classical algorithms. This work proposes four new quantum-classical algorithms: Simulated Quantum Parallel Tempering (SQPT), Simulated Quantum Population Annealing (SQPA), Simulated Quantum Parallel Tempering - Population Annealing v1 (SQPTPA1) and Simulated Quantum Parallel Tempering - Population Annealing v2 (SQPTPA2). They are obtained by combining SQA, Parallel Tempering (PT), and Population Annealing (PA). Their results are compared with those provided by SQA, considering benchmark QUBO problems, characterized by different profiles. Even though this work is preliminary, the obtained results are encouraging and prove hybrid solvers' potential in solving a generic optimization problem.

关键词： Quantum annealing Simulated annealing Statistics Sociology optimization Annealing MIMICs Simulated quantum annealing parallel tempering population annealing hybrid quantum-classical algorithms optimization problems quadratic unconstrained binary optimization Ising machine cost function energy profile

来源：评论

学校读者我要写书评

暂无评论

The set partitioning problem in a quantum context

引用

optimization LETTERS 2024年第1期18卷 1-17页

作者： Cacao, Rafael Cortez, Lucas R. C. T. Forner, Jackson Validi, Hamidreza de Farias, Ismael R. Hicks, Illya V. Texas Tech Univ Ind Mfg & Syst Engn Lubbock TX 79409 USA Southern Methodist Univ Operat Res & Engn Management Dallas TX USA Rice Univ Computat Appl Math & Operat Res Houston TX USA

The set partitioning problem and its decision variant (i.e., the exact cover problem) are combinatorial optimization problems that were historically crucial in the quantum optimization community. This problem is also employed in the main problem of the branch-and-price approach in many real-world optimization problems, including, but not limited to, redistricting and scheduling. Motivated by recent claims on the capability of quantum computers in "solving" hard combinatorial optimization problems, we propose a quadratic unconstrained binary optimization ( QUBO) formulation for the set partitioning problem with penalty coefficients that are at least as tight as the existing naive ones. We also employ five reduction techniques of Garfinkel and Nemhauser (Operations Research 17(5):848-856, 1969) to reduce the size of an existing set of benchmark instances. We finally use variational quantum eigensolver ( VQE) as a heuristic to find feasible solutions for the problem. Our computational experiments show the efficacy of employing the proposed penalty coefficients and the existing classical reduction techniques in the quantum context. Our codes and data are available on GitHub.

关键词： The set partitioning problem quadratic unconstrained binary optimization Penalty coefficients Variational quantum eigensolver

来源：评论

学校读者我要写书评

暂无评论

Building an iterative heuristic solver for a quantum annealer

引用

COMPUTATIONAL optimization AND APPLICATIONS 2016年第3期65卷 845-869页

作者： Rosenberg, Gili Vazifeh, Mohammad Woods, Brad Haber, Eldad 1QB Informat Technol 1QBit 458-550 Burrard St Vancouver BC V6C 2B5 Canada Univ British Columbia Dept Math & Earth & Ocean Sci Vancouver BC V6T 1Z2 Canada

A quantum annealer heuristically minimizes quadratic unconstrained binary optimization (QUBO) problems, but is limited by the physical hardware in the size and density of the problems it can handle. We have developed a meta-heuristic solver that utilizes D-Wave Systems' quantum annealer (or any other QUBO problem optimizer) to solve larger or denser problems, by iteratively solving subproblems, while keeping the rest of the variables fixed. We present our algorithm, several variants, and the results for the optimization of standard QUBO problem instances from OR-Library of sizes 500 and 2500 as well as the Palubeckis instances of sizes 3000-7000. For practical use of the solver, we show the dependence of the time to best solution on the desired gap to the best known solution. In addition, we study the dependence of the gap and the time to best solution on the size of the problems solved by the underlying optimizer. Our results were obtained by simulation, using a tabu 1-opt solver, due to the huge number of runs required and limited quantum annealer time availability.

关键词： Quantum annealing quadratic unconstrained binary optimization Combinatoric optimization k-opt Local search Iterative heuristic solver

来源：评论

学校读者我要写书评

暂无评论

Capacitated Clustering via Majorization-Minimization and Collaborative Neurodynamic optimization

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2024年第5期35卷 6679-6692页

作者： Li, Hongzong Wang, Jun City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China City Univ Hong Kong Sch Data Sci Hong Kong Peoples R China

This paper addresses capacitated clustering based on majorization-minimization and collaborative neurodynamic optimization (CNO). Capacitated clustering is formulated as a combinatorial optimization problem. Its objective function consists of fractional terms with intra-cluster similarities in their numerators and cluster cardinalities in their denominators as normalized cluster compactness measures. To obviate the difficulty in optimizing the objective function with factional terms, the combinatorial optimization problem is reformulated as an iteratively reweighted quadratic unconstrained binary optimization problem with a surrogate function and a penalty function in a majorization-minimization framework. A clustering algorithm is developed based on CNO for solving the reformulated problem. It employs multiple Boltzmann machines operating concurrently for local searches and a particle swarm optimization rule for repositioning neuronal states upon their local convergence. Experimental results on ten benchmark datasets are elaborated to demonstrate the superior clustering performance of the proposed approaches against seven baseline algorithms in terms of 21 internal cluster validity criteria.

关键词： Capacitated clustering collaborative neurodynamic optimization (CNO) iteratively reweighted optimization majorization-minimization quadratic unconstrained binary optimization

来源：评论

学校读者我要写书评

暂无评论

The potential of quantum annealing for rapid solution structure identification

引用

CONSTRAINTS 2021年第1-4期26卷 1-25页

作者： Pang, Yuchen Coffrin, Carleton Lokhov, Andrey Y. Vuffray, Marc Univ Illinois Dept Comp Sci Champaign IL 61801 USA Los Alamos Natl Lab Adv Network Sci Initiat Los Alamos NM 87545 USA

The recent emergence of novel computational devices, such as quantum computers, coherent Ising machines, and digital annealers presents new opportunities for hardware-accelerated hybrid optimization algorithms. Unfortunately, demonstrations of unquestionable performance gains leveraging novel hardware platforms have faced significant obstacles. One key challenge is understanding the algorithmic properties that distinguish such devices from established optimization approaches. Through the careful design of contrived optimization tasks, this work provides new insights into the computation properties of quantum annealing and suggests that this model has the potential to quickly identify the structure of high-quality solutions. A meticulous comparison to a variety of algorithms spanning both complete and local search suggests that quantum annealing's performance on the proposed optimization tasks is distinct. This result provides new insights into the time scales and types of optimization problems where quantum annealing has the potential to provide notable performance gains over established optimization algorithms and suggests the development of hybrid algorithms that combine the best features of quantum annealing and state-of-the-art classical approaches.

关键词： Discrete optimization Ising model quadratic unconstrained binary optimization Local search Quantum annealing Large neighborhood search Integer programming Belief propagation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：