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 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.
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 po...
详细信息
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.
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 opti...
详细信息
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.
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 roundin...
详细信息
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.
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 mi...
详细信息
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.
暂无评论