Survei transformasi terkait dengan penggunaan pemecah SAT

13

Saya mulai menyelidiki kemungkinan mengandalkan solver SAT untuk mengatasi masalah optimisasi yang saya minati, dan saya sedang mencari survei yang akan menampilkan contoh-contoh transformasi "pintar" ke varian SAT (yaitu, transformasi yang menghasilkan dalam masalah ukuran yang wajar, karena saya tidak tertarik untuk membuktikan hasil kekerasan tetapi dalam benar-benar menyelesaikan masalah), kira-kira dalam semangat apa yang dapat ditemukan dalam survei pada grafik kubik oleh Greenlaw dan Petreschi , jika perbandingan dapat dibuat di antara keduanya.

Apakah survei seperti itu luput dari perhatian saya karena itu tidak ada, atau karena saya baru saja melewatkannya?

ds.algorithms reference-request sat optimization Anthony Labarre
sumber
Apa yang Anda maksud dengan "varian SAT"?
Giorgio Camerani
@Walter: Maaf jika ini bukan kata yang tepat, saya maksudkan hal-hal seperti -SAT, Planar-SAT, NAE-SAT, dan sebagainya ... tapi saya mungkin harus menyertakan dua kata di antara tanda kurung, karena saya tidak tahu apakah itu penting ketika menggunakan pemecah SAT. k
Anthony Labarre
4
Jangan khawatir, itu kata yang tepat, aku seharusnya mengerti itu. Dari sudut pandang yang murni praktis, saya tidak berpikir itu penting (yang paling penting adalah betapa pelitnya pengkodean Anda). Bisakah Anda memberikan detail lebih lanjut tentang masalah pengoptimalan yang Anda coba selesaikan? Saya sangat tertarik dengan aplikasi praktis SAT dan dalam aspek teknik pemecahan SAT.
Giorgio Camerani
Kedengarannya agak membingungkan bahwa Anda berbicara tentang masalah optimasi tetapi pada saat yang sama tentang SAT. Biasanya untuk optimalitas Anda membutuhkan sesuatu yang lebih kuat, misalnya MAX-SAT. Mungkin Anda bisa mengklarifikasi itu.
Mikolas
pertanyaan ini mungkin agak terkait: cstheory.stackexchange.com/q/4314/4506
Mikolas

Jawaban:

9

Tidak yakin apakah itu yang Anda cari tetapi di sini ada satu: JM Silva, aplikasi Praktis Kepuasan Boolean .

Mikolas
sumber
2
Saya tidak bisa mengaksesnya melalui tautan Anda, ini yang lain . Sekilas, makalahnya tampak cukup menarik, tetapi lebih fokus pada aplikasi daripada yang saya cari.
Anthony Labarre
@Anthony yah Anda memang mengatakan Anda tertarik pada aspek praktis :-) Bagaimanapun, pemecah arus utama yang ada tidak benar-benar membedakan antara berbagai jenis SAT. Di masa lalu telah ada beberapa pekerjaan mengeksploitasi klausa biner, misalnya. Tetapi solver yang ada hanya menggunakan DPLL + unit prop + clause learning. Namun, beberapa preprosesor mengeksploitasi struktur. Tetapi sekali lagi, tidak benar-benar dari sudut pandang kompleksitas th. klasifikasi.
Mikolas
8

Bab 2 dari Handbook of Satisfiability mensurvei aspek-aspek yang perlu diingat ketika merancang transformasi tersebut, serta daftar referensi yang menjawab pertanyaan saya. Ini membantu saya menemukan beberapa contoh yang bisa kita lihat untuk membiasakan diri dengan transformasi ini:

Anthony Labarre
sumber