2017/05/27 by Mark Lewis, Fred Glover, Lewis, Mark +2 · 4 citations
Computer Science · Engineering · #Quantum Computing Algorithms and Architecture #Optical Network Technologies #Quantum Information and Cryptography
paper · pdf · doi:10.48550/arxiv.1705.09844
The Quadratic Unconstrained Binary Optimization problem (QUBO) has become a\nunifying model for representing a wide range of combinatorial optimization\nproblems, and for linking a variety of disciplines that face these problems. A\nnew class of quantum annealing computer that maps QUBO onto a physical qubit\nnetwork structure with specific size and edge density restrictions is\ngenerating a growing interest in ways to transform the underlying QUBO\nstructure into an equivalent graph having fewer nodes and edges. In this paper\nwe present rules for reducing the size of the QUBO matrix by identifying\nvariables whose value at optimality can be predetermined. We verify that the\nreductions improve both solution quality and time to solution and, in the case\nof metaheuristic methods where optimal solutions cannot be guaranteed, the\nquality of solutions obtained within reasonable time limits.\n We discuss the general QUBO structural characteristics that can take\nadvantage of these reduction techniques and perform careful experimental design\nand analysis to identify and quantify the specific characteristics most\naffecting reduction. The rules make it possible to dramatically improve\nsolution times on a new set of problems using both the exact Cplex solver and a\ntabu search metaheuristic.\n