Chook -- A comprehensive suite for generating binary optimization problems with planted solutions

Abstract

We present Chook, an open-source Python-based tool to generate discrete optimization problems of tunable complexity with a priori known solutions. Chook provides a cross-platform unified environment for solution planting using a number of techniques, such as tile planting, Wishart planting, equation planting, and deceptive cluster loop planting. Chook also incorporates planted solutions for higher-order (beyond quadratic) binary optimization problems. The support for various planting schemes and the tunable hardness allows the user to generate problems with a wide range of complexity on different graph topologies ranging from hypercubic lattices to fully-connected graphs.

arXiv comment8 pages, 2 figures, 3 tables. Python source code under ancillary files (v 0.2 uses an updated k-local scheme)

References in corpus (12)

• A Coherent Ising Machine Based On Degenerate Optical Parametric Oscillators
• Probing for quantum speedup in spin glass problems with planted solutions
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• First-order transitions and the performance of quantum algorithms in random optimization problems
• Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states
• Practical engineering of hard spin-glass instances
• The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
• Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT
• Equation Planting: A Tool for Benchmarking Ising Machines
• Computational hardness of spin-glass problems with tile-planted solutions
• Typical kernel size and number of sparse random matrices over GF(q) - a statistical physics approach

Cited by in corpus (5)

• Computational Overhead of Locality Reduction in Binary Optimization Problems
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Fluctuation guided search in quantum annealing
• Posiform Planting: Generating QUBO Instances for Benchmarking
• Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking