È fattibile risolvere questo problema di copertura sottoinsieme con SAT SOLVER?

Question

Il problema è trovare $ \ mathcal {s} $ , una minima raccolta di sottoinsiemi di $ \ {1 , \ punti, 17 \} $ in modo tale che le due condizioni siano soddisfatte:

.
1. se $ s \ subseteq \ mathcal {s} $ quindi $ | s |= 6 $ ;
2. per qualsiasi classe $ A \ SOTETETQ \ {1, \ Dots, 17 \} $ con $ | A |= 3 $ esiste una $ s \ in \ mathcal {s} $ con $ A \ sottoinsieme $ .

Vedi qui per un problema combinatorio correlato ..

Penso che questo possa essere formulato come un problema Min SAT.

per ogni $ S \ SOTETETQ \ {1, \ DOTS, 17 \} $ con $ | S |= 6 $ , introduciamo una variabile $ x_s $ . E per ogni $ A \ SOTETETQ \ {1, \ Dots, 17 \} $ con $ | A |= 3 $ , introduciamo una clausola $$ \ vee_ {s: a \ semetettq s, | s |= 6} x_ {s} $$ Poi in Principal possiamo usare un risolutore satellitare per trovare il numero minimo di $ x_s $ che deve essere vero per soddisfare tutte le clausole.

Questo ha bisogno di $ \ binom {17} {6}= 12376 $ variabili, $ \ binom {17} { 3}= 680 $ clausole di lunghezza $ \ binom {17-3} {3}= 364 $ .

Ho pochissima esperienza nell'utilizzo effettivamente dei solutori SAT. Quindi questo vale davvero la pena provare sul mio laptop o non c'è alcuna speranza?

---

AGGIORNAMENTO

Risultati Ci sono molte ricerche sulla copertura impostata. Sembra che fossi troppo ambizioso per cercare di risolvere il problema per i parametri (17, 6, 3).

È già un problema aperto per (12, 5, 3).

Vedi qui per maggiori dettagli.

---

Aggiorna 2

ha provato a scrivere tutto in puro sabato ed è un po 'forte> più veloce usando cadico di z3.

Inoltre, è significativamente più veloce trovare una soluzione che non esistere soluzioni.

Ho provato a rompere la simmetria aggiungendo i vincoli che è necessario selezionare il primo e l'ultimo sottoinsieme dell'ordine Lexicon.

Answer 1

L'ottimizzazione con SAT è solitamente indirizzata come Maxsat invece di Min SAT.In particolare, suggerisco di cercare solviss per "Maxsat parziale ponderato", ad esempio Maxhs e RC2.

La dimensione del problema che hai è abbastanza piccolo nel contesto dei moderni solver maxsat, quindi sì, vale la pena provare.Non ci sono garanzie che il risolutore funzionerà in modo efficiente, ed è molto difficile prevedere se funzionerà in modo efficiente, quindi la cosa migliore da fare è provare.

Answer 2

Con Sat, può essere difficile prevedere ciò che sarà fattibile e ciò che non lo farà. Vale la pena provare.

Suggerisco che, invece di Minsat, provi prima di utilizzare la ricerca binaria su $ n= | \ mathcal {s} | $ , il numero di set bisogno. È possibile utilizzare un contenitore At-Most- $ N $ -out-of-12376 vincolo sulla tua $ x_s $ Variabili. Ci sono diversi Tecniche per codifica che in SAT, anche se in pratica proverei prima di provare a utilizzare plible con il risolutore Z3.

Il tuo problema ha un sacco di simmetria. Le solutori satellitare a volte possono avere difficoltà con la simmetria. Potresti provare a fare il più possibile per rompere la simmetria. Ad esempio, senza perdita di generalità possiamo assumere che $ \ {1,2,3,4,5,6} $ è uno dei set (altrimenti permuta Tutti i numeri così è), quindi potresti effettuare un hardcode questo fatto nell'istanza SAT. Più tali lemmi puoi dimostrare, meglio potrebbe eseguire il risolutore satellitare.

Puoi anche codificare in modo diverso i set. Let $ s_i $ Denota la $ i $ Set che è scelto da $ \ Mathcal {s} $ . Introdurre variabless $ x_ {i, j} $ per indicare che $ j \ in s_i $ e variabili < Span Class="Math-Container"> $ y_ {i, a} $ per indicare che la $ a \ sottoinsieme s_i $ , per ogni < Class="Math-Container"> $ A \ SOTETETQ \ {1, \ DOTS, 17 \} $ con $ | A |= 3 $ E ogni $ i \ in \ {1, \ dots, n \} $ e ogni $ j \ in \ {1, \ punti, 17 \} $ . Aggiungi una clausola $ \ bigvee_i y_ {i, a} $ per ogni $ a $ per assicurarti che ciascuno $ A $ è coperto da almeno un set. Aggiungere un vincolo di 6-out-out-17 per ogni $ i $ per indicare esattamente 6 della $ x_ {i , j} $ sono veri. Infine, aggiungi vincoli per far rispettare la coerenza tra la $ x $ 's e $ y $ ' s. In particolare, per ogni $ A={A_1, A_2, A_3 \} $ , aggiungi clausole $ \ neg x_ { I, A_1} \ lor \ neg x_ {i, a_2} \ lor \ neg x_ {i, a_3} {i, a_3} \ lor y_ {i, a} $ e $ \ neg y_ {i, a} \ lor x_ {i, a_1} $ e $ \ neg y_ {i, a} \ lor x_ {i, a_2} $ < / span> e $ \ neg y_ {i, a} \ lor x_ {i, a_3} $ . Questo richiederà circa $ (17 + 680) n $ variabili e $ 4 \ cdot 680 n $ clausole ( non contando la $ N $ Vincoli 6-out-17); Dal momento che mi aspetto $ n \ circa 35 $ , questa è circa variabili 24k e clausole di 100k. Sono più clausole della tua codifica, e ha ancora più simmetria, quindi potrebbe funzionare peggio - anche se sono clausole più brevi, ed è difficile prevedere quali codifiche funzionerà meglio con Sat, così spesso è necessaria una sperimentazione. Potresti anche provare a esprimere questo come istanza ILP invece di Sat.