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

Quafu-Qcover:Explore combinatorial optimization problems on cloud-based quantum computers

Chinese Physics B 2024年第5期33卷 104-115页

作者：许宏泽庄伟峰王正安黄凯旋时运豪马卫国李天铭陈驰通许凯冯玉龙刘培陈墨李尚书杨智鹏钱辰靳羽欣马运恒肖骁钱鹏顾炎武柴绪丹普亚南张翼鹏魏世杰增进峰李行龙桂鲁金贻荣于海峰范桁刘东胡孟军 Beijing Academy of Quantum Information Sciences Beijing 100193China State Key Laboratory of Low Dimensional Quantum Physics Department of PhysicsTsinghua UniversityBeijing 100084China Institute of Physics Chinese Academy of SciencesBeijing 100190China Frontier Science Center for Quantum Information Beijing 100184China School of Physical Sciences University of Chinese Academy of SciencesBeijing 100190China CAS Center for Excellence in Topological Quantum Computation UCASBeijing 100190China

We introduce Quafu-Qcover,an open-source cloud-based software package developed for solving combinatorial optimization problems using quantum simulators and hardware ***-Qcover provides a standardized and comprehensive workflow that utilizes the quantum approximate optimization algorithm(QAOA).It facilitates the automatic conversion of the original problem into a quadratic unconstrained binary optimization(QUBO)model and its corresponding Ising model,which can be subsequently transformed into a weight *** core of Qcover relies on a graph decomposition-based classical algorithm,which efficiently derives the optimal parameters for the shallow QAOA ***-Qcover incorporates a dedicated compiler capable of translating QAOA circuits into physical quantum circuits that can be executed on Quafu cloud quantum *** to a general-purpose compiler,our compiler demonstrates the ability to generate shorter circuit depths,while also exhibiting superior speed ***,the Qcover compiler has the capability to dynamically create a library of qubits coupling substructures in real-time,utilizing the most recent calibration data from the superconducting quantum *** ensures that computational tasks can be assigned to connected physical qubits with the highest *** Quafu-Qcover allows us to retrieve quantum computing sampling results using a task ID at any time,enabling asynchronous ***,it incorporates modules for results preprocessing and visualization,facilitating an intuitive display of solutions for combinatorial optimization *** hope that Quafu-Qcover can serve as an instructive illustration for how to explore application problems on the Quafu cloud quantum computers.

关键词： quantum cloud platform combinatorial optimization problems quantum software

来源：评论

学校读者我要写书评

暂无评论

The effect of elite pool in hybrid population-based meta-heuristics for solving combinatorial optimization problems

引用

APPLIED SOFT COMPUTING 2016年 44卷 45-56页

作者： Jaradat, Ghaith Ayob, Masri Almarashdeh, Ibrahim Jerash Univ Fac Informat Technol Dept Comp Sci Jerash 26150311 Jordan Natl Univ Malaysia Fac Informat Sci & Technol Ctr Artificial Intelligence Technol Data Min & Optimizat Res Grp Bb Bangi 43600 Selangor Malaysia Univ Dammam Coll Appl Studies & Community Serv Dept Management Informat Syst Dammam 31433 Saudi Arabia

This work investigates the effect of elite pool that has high-quality and diverse solutions in three hybrid population-based meta-heuristics with an elite pool of a hybrid Elitist-Ant System, a hybrid Big Bang-Big Crunch optimization, and a hybrid scatter search. The purpose of incorporating an elite pool in population based meta-heuristics is to maintain the diversity of the search while exploiting the solution space as in the reference set of the scatter search. This may guarantee the effectiveness and efficiency of the search, which could enhance the performance of the algorithms and generalized well across different datasets. To test the generality of these meta-heuristics via their consistency and efficiency, we use three classes of well-known combinatorial optimization problems as follows: symmetric traveling salesman problem, 0-1 multidimensional knapsack problem, and capacitated vehicle routing problem. Experimental results showed that the performance of our hybrid population-based meta-heuristics, compared to the best known results, is competitive in many instances. This finding indicates the effectiveness of utilizing an elite pool in our hybrid meta-heuristics in diversifying the search and subsequently enhances their performance over different instances and problems. (C) 2016 Published by Elsevier B.V.

关键词： Hybrid meta-heuristics Elite pool Elitist-Ant System Big Bang-Big Crunch Scatter search combinatorial optimization problems

来源：评论

学校读者我要写书评

暂无评论

Characterizing Permutation-Based combinatorial optimization problems in Fourier Space

引用

EVOLUTIONARY COMPUTATION 2023年第3期31卷 163-199页

作者： Elorza, Anne Hernando, Leticia Lozano, Jose A. Univ Basque Country UPV EHU Dept Comp Sci & Artificial Intelligence Intelligent Syst Grp San Sebastian 20018 Spain Univ Basque Country UPV EHU Dept Math Intelligent Syst Grp Leioa 48940 Spain Basque Ctr Appl Math BCAM Bilbao 48009 Spain Univ Basque Country UPV EHU Dept Comp Sci & Artificial Intelligence San Sebastian 20018 Spain

Comparing combinatorial optimization problems is a difficult task. They are defined using different criteria and terms: weights, flows, distances, etc. In spite of this apparent discrepancy, on many occasions, they tend to produce problem instances with similar properties. One avenue to compare different problems is to project them onto the same space, in order to have homogeneous representations. Expressing the problems in a unified framework could also lead to the discovery of theoretical properties or the design of new algorithms. This article proposes the use of the Fourier transform over the symmetric group as the tool to project different permutation-based combinatorial optimization problems onto the same space. Based on a previous study (Kondor, 2010), which characterized the Fourier coefficients of the quadratic assignment problem, we describe the Fourier coefficients of three other well-known problems: the symmetric and nonsymmetric traveling salesperson problem and the linear ordering problem. This transformation allows us to gain a better understanding of the intersection between the problems, as well as to bound their intrinsic dimension.

关键词： combinatorial optimization problems Fourier transform permutations representation theory intrinsic dimension

来源：评论

学校读者我要写书评

暂无评论

Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2022年第2期296卷 393-422页

作者： Karimi-Mamaghan, Maryam Mohammadi, Mehrdad Meyer, Patrick Karimi-Mamaghan, Amir Mohammad Talbi, El-Ghazali CNRS UMR 6285 IMT Atlant Lab STICC F-29238 Brest France Univ Tehran Dept Elect & Comp Engn Tehran Iran Univ Lille CNRS UMR 9189Dept Comp Sci Ctr Rech Informat Signal & Automat Lille CRIStAL F-59000 Lille France

In recent years, there has been a growing research interest in integrating machine learning techniques into meta-heuristics for solving combinatorial optimization problems. This integration aims to lead meta heuristics toward an efficient, effective, and robust search and improve their performance in terms of solution quality, convergence rate, and robustness. Since various integration methods with different purposes have been developed, there is a need to review the recent advances in using machine learning techniques to improve meta-heuristics. To the best of our knowledge, the literature is deprived of having a comprehensive yet technical review. To fill this gap, this paper provides such a review on the use of machine learning techniques in the design of different elements of meta-heuristics for different purposes including algorithm selection , fitness evaluation , initialization , evolution , parameter setting , and cooperation . First, we describe the key concepts and preliminaries of each of these ways of integration. Then, the recent advances in each way of integration are reviewed and classified based on a proposed unified taxonomy. Finally, we provide a technical discussion on the advantages, limitations, requirements, and challenges of implementing each of these integration ways, followed by promising future research directions. (c) 2021 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license ( http://***/licenses/by-nc-nd/4.0/ )

关键词： Meta-heuristics Machine learning combinatorial optimization problems State-of-the-art

来源：评论

学校读者我要写书评

暂无评论

An Evaluation of Methods for Estimating the Number of Local Optima in combinatorial optimization problems

引用

EVOLUTIONARY COMPUTATION 2013年第4期21卷 625-658页

作者： Hernando, Leticia Mendiburu, Alexander Lozano, Jose A. Univ Basque Country UPV EHU Dept Comp Sci & Artificial Intelligence Intelligent Syst Grp San Sebastian 20018 Spain

The solution of many combinatorial optimization problems is carried out by metaheuristics, which generally make use of local search algorithms. These algorithms use some kind of neighborhood structure over the search space. The performance of the algorithms strongly depends on the properties that the neighborhood imposes on the search space. One of these properties is the number of local optima. Given an instance of a combinatorial optimization problem and a neighborhood, the estimation of the number of local optima can help not only to measure the complexity of the instance, but also to choose the most convenient neighborhood to solve it. In this paper we review and evaluate several methods to estimate the number of local optima in combinatorial optimization problems. The methods reviewed not only come from the combinatorial optimization literature, but also from the statistical literature. A thorough evaluation in synthetic as well as real problems is given. We conclude by providing recommendations of methods for several scenarios.

关键词： combinatorial optimization problems local search estimation number of local optima species estimation problem traveling salesman problem flow shop scheduling problem

来源：评论

学校读者我要写书评

暂无评论

Treatment of combinatorial optimization problems using selection equations with cost terms.: Part II.: NP-hard three-dimensional assignment problems

引用

PHYSICA D 1999年第2期134卷 242-252页

作者： Starke, J Schanz, M Haken, H Univ Heidelberg Inst Angew Math D-69120 Heidelberg Germany Inst Parallele & Verteilte Hochstleistungsrechner IPVR D-70565 Stuttgart Germany Zentrum Synerget Inst Theoret Phys 1 D-70550 Stuttgart Germany

While Part I of our work (Physica D 134 (1999) 227-241) introduced the approach of coupled selection equations with cost terms in general and treated the two-dimensional assignment problem in detail, this second part presents the adaptation of the method to the NP-hard three-dimensional assignment problem. This is a special combinatorial optimization problem which occurs for example in manufacturing planning and flexible manufacturing systems. Optimal parameter settings are investigated numerically. The capability of our dynamical system approach using coupled selection equations with cost terms is demonstrated by simulation results. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： combinatorial optimization problems assignment problems selection equations penalty methods

来源：评论

学校读者我要写书评

暂无评论

Exponential Lower Bounds on the Complexity of a Class of Dynamic Programs for combinatorial optimization problems

引用

ALGORITHMICA 2012年第3-4期62卷 659-700页

作者： Bompadre, Agustin CALTECH Grad Aeronaut Labs Pasadena CA 91125 USA

We prove exponential lower bounds on the running time of Dynamic Programs (DP) of a certain class for some combinatorial optimization problems. The class of DPs for which we derive the lower bounds is general enough to include well-known DPs for combinatorial optimization problems, such as the ones developed for the Shortest Path Problem, the Knapsack Problem, or the Traveling Salesman Problem. The problems analyzed include the Traveling Salesman Problem (TSP), the Bipartite Matching Problem (BMP), the Min and the Max Cut problems (MCP), the Min Partition Problem (MPP), and the Min Cost Test Collection Problem (MCTCP). We draw a connection between Dynamic Programs and algorithms for polynomial evaluation. We then derive and use complexity results of polynomial evaluation to prove similar results for Dynamic Programs for the TSP or the BMP. We define a reduction between problems that allows us to generalize these bounds to problems for which either the TSP or the BMP transforms to. Moreover, we show that some standard transformations between problems are of this kind. In this fashion, we extend the lower bounds to other combinatorial optimization problems.

关键词： Dynamic programming combinatorial optimization problems Monotone arithmetic circuits

来源：评论

学校读者我要写书评

暂无评论

New rollout algorithms for combinatorial optimization problems

引用

optimization METHODS & SOFTWARE 2002年第4期17卷 627-654页

作者： Guerriero, F Mancini, M Musmanno, R Univ Calabria Dipartimento Elettron Informat & Sistemist I-87030 Arcavacata Di Rende CS Italy

Rollout algorithms are new computational approaches used to determine near-optimal solutions for deterministic and stochastic combinatorial optimization problems. They are built on a generic base heuristic with the aim to construct another hopefully improved heuristic. However, rollout algorithms can be very expensive from the computational point of view, so their use for practical applications can be limited. In this article, we propose modified versions of the rollout algorithms to solve deterministic optimization problems, defined in such a way to limit the computational cost, without worsening the quality of the final approximate solution obtained.

关键词： combinatorial optimization problems rollout algorithms neuro-dynamic programming local search methods construction heuristics

来源：评论

学校读者我要写书评

暂无评论

A 2 x 30k-Spin Multi-Chip Scalable CMOS Annealing Processor Based on a Processing-in-Memory Approach for Solving Large-Scale combinatorial optimization problems

引用

IEEE JOURNAL OF SOLID-STATE CIRCUITS 2020年第1期55卷 145-156页

作者： Takemoto, Takashi Hayashi, Masato Yoshimura, Chihiro Yamaoka, Masanao Hitachi Ltd Res & Dev Grp Tokyo 1858601 Japan

The world's first 2 x 30k-spin multi-chip CMOS annealing processor (AP)-based on the processing-in-memory approach for solving large-scale combinatorial optimization problem-was developed. To expand the bit width of coefficients and enhance the scalability of the AP, it has three key features: an expandable and high-accuracy spin operator for local communication, a highly integrated spin circuit using direct access to SRAM, and a low-latency inter-chip interface that does not affect the runtime or results of the annealing process. The AP is fabricated on the basis of 40-nm CMOS technology. It was experimentally demonstrated that the spin-flip ratio of the processor agrees well with theoretical values based on the Gibbs distribution over a wide temperature range. As a result, under two-chip operation with 2 x 30k spins, the AP achieves an annealing time of 22 which is 455 times and 2.6 x 10(4) times faster than those achieved by our previous CMOS-AP and a conventional CPU, respectively. Moreover, its energy efficiency is 1.75 x 10(5) times higher than that of a conventional CPU-based algorithm.

关键词： CMOS annealing processor (AP) combinatorial optimization problems Gibbs distribution inter-chip interface processing-in-memory approach SRAM

来源：评论

学校读者我要写书评

暂无评论

On the Landscape of combinatorial optimization problems

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2014年第3期18卷 420-434页

作者： Tayarani-N, Mohammad-H. Pruegel-Bennett, Adam Univ Southampton Dept Elect & Comp Sci Southampton SO17 1BJ Hants England

This paper carries out a comparison of the fitness landscape for four classic optimization problems: Max-Sat, graph-coloring, traveling salesman, and quadratic assignment. We have focused on two types of properties, local average properties of the landscape, and properties of the local optima. For the local optima we give a fairly comprehensive description of the properties, including the expected time to reach a local optimum, the number of local optima at different cost levels, the distance between optima, and the expected probability of reaching the optima. Principle component analysis is used to understand the correlations between the local optima. Most of the properties that we examine have not been studied previously, particularly those concerned with properties of the local optima. We compare and contrast the behavior of the four different problems. Although the problems are very different at the low level, many of the long-range properties exhibit a remarkable degree of similarity.

关键词： combinatorial optimization problems fitness landscape graph-coloring problem long-range correlation maximum satisfiability problem quadratic assignment problem scaling analysis traveling salesman problem (TSP)

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：