Relax! It's just SAT
People
Supervisor
Description
Goals
This project suggest exploring the use of existing implementations of an SDP solution procedure, and swap out the BLAS and LAPACK libraries with their CUDA/GPGPU counterparts. For example, using “libnvblas.so” for the BLAS implementation. The target problem corpus will be "hard" random UNSAT problems in the 3-SAT family, with upwards of 700 Boolean variables.
Background Literature
[*A] Anjos, M. An improved semidefinite programming relaxation for the satisfiability problem. Math. Program. 102, 589–608 (2005).
Gain
Scholarships are available for AU/NZ university students who wish to do an honours research year of study at the Australian National University.
https://www.anu.edu.au/study/scholarships/find-a-scholarship/co-lab-honours-grant
Keywords
Boolean Satisfiability, GPGPU, Semidefinite Programming