Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions
Quadratic Unconstrained Binary Optimization (QUBO) is recognized as a unifying framework for modeling a wide range of problems. Problems can be solved with commercial solvers customized for solving QUBO and since QUBO have degree two, it is useful to have a method for transforming higher degree pseudo-Boolean problems to QUBO format. The standard transformation approach requires additional auxiliary variables supported by penalty terms for each higher degree term. This paper improves on the existing cubic-to-quadratic transformation approach by minimizing the number of additional variables as well as penalty coefficient. Extensive experimental testing on Max 3-SAT modeled as QUBO shows a near 100% reduction in the subproblem size used for minimization of the number of auxiliary variables.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Pseudo-Boolean Polynomials Approach for Image Edge Detection
We introduce a novel approach for image edge detection based on pseudo-Boolean polynomials for image patches. We show that patches covering edge regions in the image result in pseudo-Boolean polynomials with higher degre…
Edge DetectionEfficient Minimization of Higher Order Submodular Functions using Monotonic Boolean Functions
Submodular function minimization is a key problem in a wide variety of applications in machine learning, economics, game theory, computer vision, and many others. The general solver has a complexity of $O(n^3 \log^2 n . …
BIG-bench Machine LearningAnalysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem
We analyze the transformation of QUBO from its conventional Boolean presentation into an equivalent spin glass problem with coupled $\pm1$ spin variables exposed to a site-dependent external field. We find that in a wide…
Pseudo-Boolean Polynomials Approach To Edge Detection And Image Segmentation
We introduce a deterministic approach to edge detection and image segmentation by formulating pseudo-Boolean polynomials on image patches. The approach works by applying a binary classification of blob and edge regions i…
Binary ClassificationEdge DetectionImage SegmentationSemantic SegmentationOn Quadratization of Pseudo-Boolean Functions
We survey current term-wise techniques for quadratizing high-degree pseudo-Boolean functions and introduce a new one, which allows multiple splits of terms. We also introduce the first aggregative approach, which splits …
Survey