Set di codifica dei vincoli at-most-one come un problema max-sab

Question

Assumere un set di variabile $ V $ = $ \ {v_1, ..., v_m \} $ < / span>.

Dato Total $ N $ I vincoli at-most-one (AMO) (al massimo un elemento in un determinato set true ) Imposta [del modulo sottostante], sopra la set di variabili $ V $ ,

$$ AMO \, (V_1, V4, \ NEG V_6, V_ {10}) \\ ... \\ AMO \, (V_2, \ NEG V3, V_7 ) $$

Problem: Find an assignment to $V$ that maximize
         the number of satisfiable AMO constraint set. 

.

Non riesco a rappresentarlo come problema max-sabato.

Provato fino ad ora (tentativo 1): usando un vincolo duro per ciascuno dei vincoli a maggior parte. Questo non funzionerà come codifica di $ AMO (V_i, ..., V_W) $ avrà più clausole per ogni $ AMO $ e tutti hanno assegnato lo stesso peso (peso superiore). Una soluzione a questo set potrebbe non essere la massimale.

Tentativo (2): fissare il problema di cui sopra, ho provato il peso della clausola relativa; I.e., per ogni clausola assegnare il peso proporzionale alle dimensioni della clausola. Ciò darà la preferenza di assegnare una clausola più breve soddisfacente. Ma questo non funziona in situazioni estreme come se tutta la clausola ha la stessa lunghezza.

Ho esperienza con SAT SOLVERS, ma questo è il mio primo tentativo di problemi di sabato max.

Answer 1

Il modo standard per creare vincoli morbidi in Maxsat è utilizzare le variabili dell'etichetta:

Per ogni $ AMO_J $ vincolo, creare una nuova variabile $ l_j $ .Quindi creare una clausola unità $ (\ lnot l_j) $ con peso $ 1 $ e aggiungere il $ l_j $ ad ogni clausola dello standard $ AMO_J $ codifica che contiene solo clausole dure (peso infinito).

Ora la variabile etichetta $ l_j $ agisce come interruttore: impostazione $ l_j= True $ "Disattiva" la classe $ AMO_J $ Constraint hard, ma non soddisfa la clausola unità $ (\ lnot l_j) $ .