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

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

来源：评论

学校读者我要写书评

暂无评论

quadratic unconstrained binary optimization for the Automotive Paint Shop Problem

引用

IEEE ACCESS 2023年 11卷 97769-97777页

作者： Debevere, Pieter Sugimura, Masahiko Parizy, Matthieu Fujitsu Ltd Kawasaki 2118588 Japan

The binary Paint Shop Problem (BPSP) is a combinatorial optimization problem which draws inspiration from the automotive paint shop. Its binary nature, making it a good fit for quadratic unconstrained binary optimization (QUBO) solvers, has been well studied but its industrial applications are limited. In this paper, in order to expand the industrial applications, QUBO formulations for two generalizations of the BPSP, which are the Multi-Car Paint Shop Problem (MCPSP) and the Multi-Car Multi-Color Paint Shop Problem (MCMCPSP), are proposed. Given the multiple colors, the MCMCPSP is no longer natively binary which increases the problem size and introduces additional constraint factors in the QUBO formulation. Resulting QUBOs are solved using Scatter Search (SS). Furthermore, extensions of the SS that can exploit k-hot constrained structures within the formulations are proposed to compensate the additional complexity introduced by formulating non-binary problems into QUBO. Since no public benchmark database currently exists, random problem instances are generated. Viability of the proposed QUBO solving methods for the MCPSP and MCMCPSP, is highlighted through comparison with an integer-based Random Parallel Multi-start Tabu Search (RPMTS) and a greedy heuristic for the problems. The greedy heuristic has negligible computational requirements and therefore serves as a lower bound on the desired performance. The results for both problems show that better results can be obtained than the greedy heuristic and integer-based RPMTS, by using the novel k-hot extensions of the SS to solve the problems as QUBO.

关键词： Paints Automobiles Color Image color analysis optimization Automotive engineering Mathematical models quadratic programming Automotive paint shop evolutionary algorithms k-hot constraints quadratic unconstrained binary optimization scatter search

来源：评论

学校读者我要写书评

暂无评论

Analyzing quadratic unconstrained binary optimization problems via multicommodity flows

引用

DISCRETE APPLIED MATHEMATICS 2009年第18期157卷 3746-3753页

作者： Wang, Di Kleinberg, Robert Cornell Univ Dept Comp Sci Ithaca NY 14853 USA

quadratic unconstrained binary optimization (QUBO) problems concern the minimization of quadratic polynomials in n{0, 1}-valued variables. These problems are NP-complete, but prior work has identified a sequence of polynomial-time computable lower bounds on the minimum value, denoted by C-2, C-3, C-4,.... It is known that C-2 can be computed by solving a maximum flow problem, whereas the only previously known algorithms for computing C-k (k > 2) require solving a linear program. In this paper we prove that C-3 can be computed by solving a maximum multicommodity flow problem in a graph constructed from the quadratic function. In addition to providing a lower bound on the minimum value of the quadratic function on {0, 1}(n), this multicommodity flow problem also provides some information about the coordinates of the point where this minimum is achieved. By looking at the edges that are never saturated in any maximum multicommodity flow, we can identify relational persistencies: pairs of variables that must have the same or different values in any minimizing assignment. We furthermore show that all of these persistencies can be detected by solving single-commodity flow problems in the same network. (C) 2009 Elsevier B.V. All rights reserved.

关键词： quadratic unconstrained binary optimization Multicommodity flow Network flow Persistency Roof duality

来源：评论

学校读者我要写书评

暂无评论

Clustering-driven evolutionary algorithms: an application of path relinking to the quadratic unconstrained binary optimization problem

引用

JOURNAL OF HEURISTICS 2019年第4-5期25卷 629-642页

作者： Samorani, Michele Wang, Yang Wang, Yang Lv, Zhipeng Glover, Fred Santa Clara Univ Leavey Sch Business Santa Clara CA 95051 USA Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan 430074 Hubei Peoples R China Northwestern Polytech Univ Sch Management Xian 710072 Shaanxi Peoples R China Univ Colorado Leeds Sch Business Boulder CO 80309 USA

A long-standing challenge in the metaheuristic literature is to devise a way to select parent solutions in evolutionary population-based algorithms to yield better offspring, and thus provide improved solutions to populate successive generations. We identify a way to achieve this goal that simultaneously improves the efficiency of the evolutionary process. Our strategy derives from a proposal associated with the scatter search and path relinking evolutionary algorithms that prescribes clustering the solutions and focusing on the two classes of solution combinations where the parents alternatively belong to the same cluster or to different clusters. We demonstrate the efficacy of our approach for selecting parents within this scheme by applying it to the important domain of quadratic unconstrained binary optimization (QUBO), which provides a model for solving a wide range of binary optimization problems. Within this setting, we focus on the path relinking algorithm, which together with tabu search has provided one of the most effective methods for QUBO problems. Computational tests disclose that our solution combination strategy improves the best results in the literature for hard QUBO instances.

关键词： Path relinking Machine learning Clustering quadratic unconstrained binary optimization Tabu search

来源：评论

学校读者我要写书评

暂无评论

Classifying and Benchmarking Quantum Annealing Algorithms Based on quadratic unconstrained binary optimization for Solving NP-Hard Problems

引用

IEEE ACCESS 2023年 11卷 104165-104178页

作者： Jiang, Jehn-Ruey Chu, Chun-Wei Natl Cent Univ Dept Comp Sci & Informat Engn Taoyuan 320317 Taiwan

Quantum annealing has the potential to outperform classical transistor-based computer technologies in tackling intricate combinatorial optimization problems. However, ongoing scientific debates cast doubts on whether quantum annealing devices (or quantum annealers) can genuinely provide better problem-solving capabilities than classical computers. The question of whether quantum annealing algorithms (QAAs) running on quantum annealers have computational advantages over classical algorithms (CAs) running on classical computers still remains unclear. This paper aims to clarify the question by classifying and benchmarking QAAs that utilize quadratic unconstrained binary optimization (QUBO) formulas to solve NP-hard problems. It proposes a four-class classification of QUBO formulas and exemplifies each class by QUBO formulas used by QAAs for solving specific NP-hard problems, such as the subset sum, maximum cut, vertex cover, 0/1 knapsack, graph coloring, Hamiltonian cycle, traveling salesperson, and job shop scheduling problems. The classification is based on the following two criteria: (i) Does the number of QUBO variables scale linearly with the problem input size? (ii) Does the QUBO formula have both the constraint term and the optimization term? QAAs are implemented and run on a D-Wave quantum annealer for benchmarking. They are benchmarked against related CAs in terms of the quality of the solution and the time to the solution. The benchmarking results reveal which classes of QUBO formulas are likely to provide advantages to QAAs over CAs. Furthermore, based on the benchmarking results, observations and suggestions are given for each class of QUBO formulas, facilitating the adoption of appropriate actions to improve the performance of QAAs.

关键词： Noisy intermediate-scale quantum quantum annealing quantum computer quadratic unconstrained binary optimization

来源：评论

学校读者我要写书评

暂无评论

Local search heuristics for quadratic unconstrained binary optimization (QUBO)

引用

JOURNAL OF HEURISTICS 2007年第2期13卷 99-132页

作者： Boros, Endre Hammer, Peter L. Tavares, Gabriel Rutgers State Univ RUTCOR Piscataway NJ 08854 USA

We present a family of local-search-based heuristics for quadratic unconstrained binary optimization (QUBO), all of which start with a (possibly fractional) initial point, sequentially improving its quality by rounding or switching the value of one variable, until arriving to a local optimum. The effects of various parameters on the efficiency of these methods are analyzed through computational experiments carried out on thousands of randomly generated problems having 20 to 2500 variables. Tested on numerous benchmark problems, the performance of the most competitive variant (ACSIOM) was shown to compare favorably with that of other published procedures.

关键词： integer programming local optimization quadratic unconstrained binary optimization quadratic pseudo-Boolean functions heuristics

来源：评论

学校读者我要写书评

暂无评论

A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)

引用

DISCRETE optimization 2008年第2期5卷 501-529页

作者： Boros, Endre Hammer, Peter L. Sun, Richard Tavares, Gabriel Rutgers State Univ RUTCOR Piscataway NJ 08854 USA Lucent Technol Holmdel NJ 07733 USA

The "roof dual" of a QUBO (quadratic unconstrained binary optimization) problem has been introduced in [P.L. Hammer, P. Hansen, B. Simeone, Roof duality, complementation and persistency in quadratic 0-1 optimization, Mathematical Programming 28 (1984) 121-1551;it provides a bound to the optimum value, along with a polynomial test of the sharpness of this bound, and (due to a "persistency" result) it also determines the values of some of the variables at the optimum. In this paper we provide a graph-theoretic approach to provide bounds, which includes as a special case the roof dual bound, and show that these bounds can be computed in O(n(3)) time by using network flow techniques. We also obtain a decomposition theorem for quadratic pseudo-Boolean functions, improving the persistency result of [P.L. Hammer, P. Hansen, B. Simeone, Roof duality, complementation and persistency in quadratic 0-1 optimization, Mathematical Programming 28 (1984) 121-155]. Finally, we show that the proposed bounds (including roof duality) can be applied in an iterated way to obtain significantly better bounds. Computational experiments on problems up to thousands of variables are presented. (c) 2007 Elsevier B.V. All rights reserved.

关键词： quadratic unconstrained binary optimization roof duality persistency network flows

来源：评论

学校读者我要写书评

暂无评论

An encoding of argumentation problems using quadratic unconstrained binary optimization

引用

QUANTUM MACHINE INTELLIGENCE 2024年第2期6卷 1-20页

作者： Baioletti, Marco Santini, Francesco Univ Perugia Dipartimento Matemat & Informat Via Vanvitelli 1 I-06123 Perugia Italy

In this paper, we develop a way to encode several NP-Complete problems in Abstract Argumentation to quadratic unconstrained binary optimization (QUBO) problems. In this form, a solution for a QUBO problem involves minimizing a quadratic function over binary variables (0/1), where the coefficients can be represented by a symmetric square matrix (or an equivalent upper triangular version). With the QUBO formulation, exploiting new computing architectures, such as Quantum and Digital Annealers, is possible. A more conventional approach consists of developing approximate solvers, which, in this case, are used to tackle the intrinsic complexity. We performed tests to prove the correctness and applicability of classical problems in argumentation and enforcement of argument sets. We compared our approach to two other approximate solvers in the literature during tests. In the final experimentation, we used a Simulated Annealing algorithm on a local machine. Also, we tested a Quantum Annealer from the D-Wave Ocean SDK and the Leap (TM) Quantum Cloud Service.

关键词： Argumentation Abstract frameworks quadratic unconstrained binary optimization Approximate solvers Quantum annealers

来源：评论

学校读者我要写书评

暂无评论

How to Approximate any Objective Function via quadratic unconstrained binary optimization 29

How to Approximate any Objective Function via Quadratic Unco...

引用

29th IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)

作者： Gabor, Thomas Rosenfeld, Marian Lingsch Linnhoff-Popien, Claudia Feld, Sebastian Ludwig Maximilians Univ Munchen Mobile & Distributed Syst Munich Germany Delft Univ Technol Quantum & Comp Engn Delft Netherlands

ISBN: (纸本)9781665437868

quadratic unconstrained binary optimization (QUBO) has become the standard format for optimization using quantum computers, i.e., for both the quantum approximate optimization algorithm (QAOA) and quantum annealing (QA). We present a toolkit of methods to transform almost arbitrary problems to QUBO by (i) approximating them as a polynomial and then (ii) translating any polynomial to QUBO. We showcase the usage of our approaches on two example problems (ratio cut and logistic regression).

关键词： quadratic unconstrained binary optimization QUBO quantum computing approximation

来源：评论

学校读者我要写书评

暂无评论

Solving linear systems by quadratic unconstrained binary optimization on D-Wave quantum annealing device 13

Solving linear systems by quadratic unconstrained binary opt...

引用

Conference on Quantum Information Science, Sensing, and Computation XIII

作者： Jun, Kyungtaek Conley, Rebecca Huang, Yecheng Lim, Hyunkyung Yu, Kwangmin Natl Inst Math Sci Busan 49241 South Korea St Peters Univ Dept Math & Stat Jersey City NJ 07306 USA SUNY Stony Brook Dept Appl Math & Stat Stony Brook NY 11794 USA Brookhaven Natl Lab Computat Sci Initiat Upton NY 11973 USA

ISBN: (数字)9781510642904

ISBN: (纸本)9781510642904

Many quantum computing algorithms are being developed with the advent of quantum computers. Solving linear systems is one of the most fundamental problems in almost all of science and engineering. HHL algorithm, a monumental quantum algorithm for solving linear systems on the gate model quantum computers, was invented and several advanced variations have been developed. However, HHL-based algorithms have a lot of limitations in spite of their importance. We address solving linear systems on a D-Wave quantum annealing device. To formulate a quadratic unconstrained binary optimization (QUBO) model for a linear system solving problem, we make use of a linear least-square problem with binary representation of the solution. We validate this QUBO model on the D-Wave system and discuss the results.

关键词： Quantum Annealing quadratic unconstrained binary optimization Linear Systems of Equations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：