QUBO-Generation for (MAX-)3SAT via generative AI-Methods

QUBO-Generation for (MAX-)3SAT via generative AI-Methods

Abstract:

Creating QUBOs for 3-SAT formulas using pattern QUBOs poses several challenges. Generating pattern QUBOs and building the QUBO structure itself is technically demanding due to the brute-force approach. In this study, two machine-learning approaches for QUBO generation given a 3-SAT formula are tested. Various encoding methods were explored for representing formulas and matrices. Formula encodings included vector, Word2Vec, and BERT-based methods, while latent representations were tested on QUBOs. As an initial model, a conditional autoencoder was used, with variations like dual encoders and pretrained encoders based on a RESNET18 architecture also evaluated. Accurate QUBOs could be generated for formulas with a single clause, but for formulas with up to four clauses, energy levels of solution and non-solution states overlapped. Finally, a conditional diffusion model was implemented and trained on 5 and 7 clause random formulas using vector, Word2Vec, and BERT formula embeddings. QUBOs generated with BERT formula embeddings fulfilled the highest average number of clauses per formula, though most formulas remained unsolved. Training with masked diffusion further improved performance, as QUBOs generated with masking fulfilled, on average, one additional clause. However, this approach requires a predefined mask during data generation. The sparse QUBO data structure and challenges in encoding 3-SAT formulas are likely primary factors behind these results.

Author:

Philippe Wehr

Advisors:

Sebastian Zielinski, Michael Kölle, Claudia Linnhoff-Popien

Student Thesis | Published March 2025 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors