| |
Venkata Pavan Sumanth Sikhakollu, Shreesha Sreedhara,
Rajit Manohar, Alan Mishchenko, and Jaijeet Roychowdhury
3-SAT is a class of NP-hard combinatorial optimization
problems that Ising machines have had difficulty solving successfully.
Solution success rate depends not only on the choice of Ising machine, but
crucially, also on the mapping from 3-SAT to Ising form. We evaluate the
performance of Oscillator Ising Machines (OIMs) on several existing
3-SAT-to-Ising mappings, finding that they yield mediocre or poor results.
We propose two novel enhancements to logic-synthesis-based Ising mapping
schemes that improve solution success rate significantly (from 0%
to about 56% on SATLIB's uf20 problem set). We then propose a new
circuit- and clause-based 3-SAT-to-Ising mapping scheme that employs
3-input OR gates. Using this mapping increases OIM's success rate on uf20
to 95.9%---we believe this is by far the best raw performance achieved on
any 3-SAT problem class by any Ising machine scheme. We also present
a comparison of OIM vs. simulated annealing on Ising-mapped 3-SAT
problems, revealing that OIM's performance is significantly superior.
|
|
