Buku resep untuk penyandian SAT?

Pemecah SAT semakin efisien dalam memecahkan kasus besar dan sedang digunakan sebagai ujung-belakang dalam berbagai konteks. Setiap kali seseorang ingin menggunakannya untuk memecahkan masalah dalam domain tertentu, ia harus membuat encoding ad-hoc yang tidak hanya memiliki set solusi yang tepat tetapi juga menempatkan kendala (bahkan berlebihan) dalam bentuk yang membantu heuristik pemecah dalam menemukan solusi lebih cepat.

Banyak pengkodean seperti itu bagi saya akan sangat umum, misalnya: menyatakan bahwa satu set node yang terbatas dihubungkan sebagai pohon, atau sebagai DAG, atau daftar diurutkan ...

Apakah ada buku repositori / resep pengkodean umum untuk masalah umum dengan solusi yang dioptimalkan?

Saya membaca makalah survei beberapa tahun yang lalu yang tampaknya relevan, " Teknik Penyandian SAT yang Sukses " oleh Magnus Björk.

Abstrak:

Artikel ini mengidentifikasi praktik yang baik untuk penyandian SAT dengan menganalisis wawancara dengan sejumlah pakar SAT yang terkenal. Tujuannya adalah untuk menentukan kepercayaan dalam strategi pengkodean yang berbeda dengan menganalisis apakah ada konsensus di antara para ahli atau tidak, serta membawa keluar pengetahuan tersembunyi kepada pengguna SAT.

Ada konsensus bahwa teknik pengkodean biasanya memiliki dampak dramatis pada efisiensi pemecah SAT, bahwa seringkali dibutuhkan banyak pekerjaan untuk menemukan pengkodean yang baik, dan bahwa ukuran pengkodean hanya sangat longgar terkait dengan kekerasan dalam menemukan solusi. . Topik di mana yang diwawancarai tidak setuju termasuk kelayakan termasuk aritmatika dalam masalah SAT dan apakah akan merumuskan masalah sebagai klausa atau sirkuit.

Artikel ini menjelaskan sejumlah strategi yang bagus dalam situasi yang berbeda, seperti cara berbeda untuk mewakili angka dan cara menggunakan inkrementalitas.

Itu selalu merupakan ide yang baik untuk pertama-tama memeriksa Buku Pegangan Kepuasan [1] (saya kira itu tidak tersedia secara gratis, maaf). Di sini, Bab 2 berjudul "Penyandian CNF". Paling tidak, buku ini menyediakan referensi literatur tentang keadaan seni pada saat penulisan, dan Anda dapat memperluas pencarian Anda melalui mereka.

Selain itu, di sini dan di sini adalah dua slide terbaru tentang preprocessing SAT. Slide memberikan gambaran singkat tentang teknik preprocessing, dan juga referensi lebih lanjut. Idenya adalah bahwa alih-alih mencoba "secara manual" memodelkan masalah dengan cara yang efisien, Anda hanya memodelkannya dengan cara termudah, tekan go, dan perangkat lunak memberi Anda pengkodean yang efisien.

[1] Biere, Armin, Marijn Heule, dan Hans van Maaren, eds. Buku pegangan kepuasan. Vol. 185. IOS Press, 2009.

bukan jawaban langsung, tetapi sudut lain yang semakin erat terkait: beberapa di antaranya tercakup oleh bidang penelitian yang relatif baru yang dikenal sebagai SMT, Satisfiability Modulo Theories . ide dasarnya adalah menggabungkan pengkodean masalah (misalnya, katakanlah bilangan bulat aritmatika, grafik, dll) ke dalam SAT solver tetapi juga gunakan / manfaatkan pengetahuan ekstra yang berasal dari kopling ini untuk membangun algoritma solusi yang lebih maju. inilah survei. seperti yang ditunjukkan mereka bisa jauh lebih efisien daripada menggabungkan mekanisme pengkodean ad-hoc dengan pemecah SAT standar.

• Teori Kepuasan Modulo: An Appetizer / Leonardo de Moura dan Nikolaj Bjørner

  Teori Satisfiability Modulo (SMT) adalah tentang memeriksa kepuasan formula logis atas satu atau lebih teori. Masalahnya mengacu pada kombinasi dari beberapa area paling mendasar dalam ilmu komputer. Ini menggabungkan masalah kepuasan Boolean dengan domain, seperti, yang dipelajari dalam optimasi cembung dan istilah memanipulasi sistem simbolik. Ini juga mengacu pada masalah yang paling produktif di abad lalu dari logika simbolik: masalah keputusan, kelengkapan dan ketidaklengkapan teori logis, dan akhirnya teori kompleksitas. Masalah menggabungkan secara modular algoritma tujuan khusus untuk setiap domain adalah sedalam dan menarik seperti menemukan algoritma baru yang bekerja sangat baik dalam konteks kombinasi. SMT juga menikmati peran yang sangat berguna dalam rekayasa perangkat lunak. Perangkat lunak modern, analisis perangkat keras dan alat model berbasis semakin kompleks dan sistem perangkat lunak multi-faceted. Namun, pada intinya mereka selalu merupakan komponen yang menggunakan logika simbolik untuk menggambarkan keadaan dan transformasi di antara mereka. Pemecah SMT yang disetel dengan baik yang memperhitungkan terobosan canggih biasanya mengukur skala pesanan di luar pemecah khusus ad-hoc.