Maksimal tilfredsstillelsesproblem - Maximum satisfiability problem

I beregningskompleksitetsteorien er det maksimale tilfredshetsproblemet ( MAX-SAT ) problemet med å bestemme maksimalt antall ledd, av en gitt boolsk formel i konjunktiv normalform , som kan gjøres opp ved å tilordne sannhetsverdier til variablene til formelen. Det er en generalisering av det boolske tilfredsstillelsesproblemet , som spør om det finnes en sannhetsoppgave som gjør alle ledd sanne.

Eksempel

Den konjunktive normale formelformelen

{\ displaystyle (x_ {0} \ lor x_ {1}) \ land (x_ {0} \ lor \ lnot x_ {1}) \ land (\ lnot x_ {0} \ lor x_ {1}) \ land ( \ lnot x_ {0} \ lor \ lnot x_ {1})}

er ikke tilfredsstillende: uansett hvilke sannhetsverdier som er tildelt de to variablene, vil minst en av de fire leddene være falske. Imidlertid er det mulig å tildele sannhetsverdier på en slik måte at tre av fire ledd blir sanne; faktisk, hver sannhetsoppgave vil gjøre dette. Derfor, hvis denne formelen er gitt som en forekomst av MAX-SAT-problemet, er løsningen på problemet nummer tre.

Hardhet

MAX-SAT-problemet er NP-vanskelig , siden løsningen lett fører til løsningen på det boolske tilfredsstillelsesproblemet , som er NP-komplett .

Det er også vanskelig å finne en omtrentlig løsning på problemet, som tilfredsstiller en rekke klausuler innenfor et garantert tilnærmingsforhold for den optimale løsningen. Mer presist er problemet APX- komplett, og innrømmer således ikke et tilnærmingsskjema for polynom-tid med mindre P = NP.

Vektet MAX-SAT

Mer generelt kan man definere en vektet versjon av MAX-SAT som følger: gitt en konjunktiv normal formelformel med ikke-negative vekter tildelt hver ledd, finn sannhetsverdier for dens variabler som maksimerer den kombinerte vekten av de tilfredsstilte leddene. MAX-SAT-problemet er en forekomst av vektet MAX-SAT der alle vekter er 1.

Tilnærmelsesalgoritmer

1/2-tilnærming

Tilfeldig tilføyelse av hver variabel for å være sann med sannsynlighet 1/2 gir en forventet 2-tilnærming . Mer presist, hvis hver ledd har minst k- variabler, gir dette en (1 - 2 ^{- k} ) -tilnærming. Denne algoritmen kan avvikles ved hjelp av metoden for betingede sannsynligheter .

(1-1 / `e` ) -tilnærming

MAX-SAT kan også uttrykkes ved hjelp av et heltall lineært program (ILP). Feste en konjunktiv normalform formel F med variable x ₁ , x ₂ , ..., x _n , og la C betegner den tidsbestemte F . For hver ledd c i C , la S ⁺_c og S ^-_c betegne sett med variabler som ikke er negert i c , og de som er negert i c , henholdsvis. Variablene y _x for ILP vil tilsvare variablene med formelen F , mens variablene z _c vil tilsvare leddene. ILP er som følger:

maksimere	${\ displaystyle \ sum _ {c \ in C} w_ {c} \ cdot z_ {c}}$		(maksimer vekten til de fornøyde klausulene)
underlagt	${\ displaystyle z_ {c} \ leq \ sum _ {x \ in S_ {c} ^ {+}} y_ {x} + \ sum _ {x \ in S_ {c} ^ {-}} (1-y_ {x})}$	for alle ${\ displaystyle c \ in C}$	(punkt er sann iff det har en sann, ikke-negerte variabel eller en falsk, negerte en)
	${\ displaystyle z_ {c} \ in \ {0,1 \}}$	for alle . ${\ displaystyle c \ in C}$	(hver klausul er enten fornøyd eller ikke)
	${\ displaystyle y_ {x} \ in \ {0,1 \}}$	for alle . ${\ displaystyle x \ i F}$	(hver variabel er enten sant eller usant)

Ovennevnte program kan lempes til følgende lineære program L :

maksimere	${\ displaystyle \ sum _ {c \ in C} w_ {c} \ cdot z_ {c}}$		(maksimer vekten til de fornøyde klausulene)
underlagt	${\ displaystyle z_ {c} \ leq \ sum _ {x \ in S_ {c} ^ {+}} y_ {x} + \ sum _ {x \ in S_ {c} ^ {-}} (1-y_ {x})}$	for alle ${\ displaystyle c \ in C}$	(punkt er sann iff det har en sann, ikke-negerte variabel eller en falsk, negerte en)
	${\ displaystyle 0 \ leq z_ {c} \ leq 1}$	for alle . ${\ displaystyle c \ in C}$
	${\ displaystyle 0 \ leq y_ {x} \ leq 1}$	for alle . ${\ displaystyle x \ i F}$

Følgende algoritme som bruker den avslapningen er en forventet (1-1 / e ) tilnærming:

Løs det lineære programmet L og få en løsning O
Sett variable x til å være sant med sannsynlighet y _x der y _x er verdien gitt i O .

Denne algoritmen kan også bli derandomisert ved hjelp av metoden for betingede sannsynligheter.

3/4-tilnærming

1/2-tilnærmelsesalgoritmen gjør det bedre når klausulene er store, mens (1-1 / e ) -tilnærmingen gjør det bedre når klausulene er små. De kan kombineres som følger:

Kjør (derandomized) 1/2-tilnærming algoritme for å få en sannhet oppdrag X .
Kjør (derandomized) (1-1 / e) -approximation å få en sannhet oppdrag Y .
Output avhengig av hvilken av X eller Y som maksimerer vekten av de tilfredsstilte klausulene.

Dette er en deterministisk faktor (3/4) tilnærming.

Eksempel

På formelen

{\ displaystyle F = \ underbrace {(x \ lor y)} _ {{\ text {weight}} 1} \ land \ underbrace {(x \ lor \ lnot y)} _ {{\ text {weight}} 1 } \ land \ underbrace {(\ lnot x \ lor z)} _ {{\ text {vekt}} 2+ \ epsilon}}

hvor (1-1 / e ) -tilnærmingen vil sette hver variabel til Sann med sannsynlighet 1/2, og slik vil oppføre seg identisk med 1/2 tilnærming. Forutsatt at tildelingen av x velges først under derandomisering, vil de derandomiserte algoritmene velge en løsning med totalvekt , mens den optimale løsningen har vekt . ${\ displaystyle \ epsilon> 0}$ ${\ displaystyle 3+ \ epsilon}$ ${\ displaystyle 4+ \ epsilon}$

Løsere

Mange eksakte løsere for MAX-SAT har blitt utviklet de siste årene, og mange av dem ble presentert i den velkjente konferansen om det boolske tilfredsstillelsesproblemet og relaterte problemer, SAT-konferansen. I 2006 var SAT-konferansen vert for den første MAX-SAT-evalueringen som sammenlignet ytelsen til praktiske løsere for MAX-SAT, slik den tidligere har gjort for det pseudo-boolske tilfredsstillelsesproblemet og det kvantifiserte boolske formelproblemet . På grunn av sin NP-hardhet kan store MAX-SAT-forekomster generelt ikke løses nøyaktig, og man må ofte ty til tilnærmelsesalgoritmer og heuristikker

Det er flere løsere sendt til de siste Max-SAT-evalueringene:

Branch and Bound based: Clone, MaxSatz (basert på Satz ), IncMaxSatz, IUT_MaxSatz, WBO, GIDSHSat.
Tilfredsstillelsesbasert: SAT4J, QMaxSat.
Utilfredshetsbasert: msuncore, WPM1, PM2.

Spesielle tilfeller

MAX-SAT er en av optimaliseringsutvidelsene til det boolske tilfredshetsproblemet , som er problemet med å bestemme om variablene til en gitt boolsk formel kan tildeles på en slik måte at formelen evalueres til SANT. Hvis klausulene er begrenset til å ha maksimalt 2 bokstaver, som i 2-tilfredshet , får vi MAX-2SAT- problemet. Hvis de er begrenset til maksimalt 3 liter per klausul, som i 3-tilfredshet , får vi MAX-3SAT- problemet.

Relaterte problemer

Det er mange problemer knyttet til tilfredshet av konjunktiv normalform Boolske formler.

Beslutningsproblemer :
- 2SAT
- 3SAT
Optimaliseringsproblemer, der målet er å maksimere antall tilfredse klausuler:
- MAX-SAT, og den tilsvarende vektede versjonen Vektet MAX-SAT
- MAX- k SAT, der hver ledd har nøyaktig k variabler:
- Det delvise maksimale tilfredshetsproblemet (PMAX-SAT) ber om maksimalt antall klausuler som kan oppfylles ved enhver tildeling av en gitt delmengde klausuler. Resten av leddene må oppfylles.
- Det myke tilfredsstillelsesproblemet (soft-SAT), gitt et sett med SAT-problemer, ber om maksimalt antall av disse problemene som kan oppfylles ved enhver oppgave.
- Det minste tilfredshetsproblemet.
MAX-SAT-problemet kan utvides til det tilfellet hvor variablene i problemet med begrensningstilfredshet hører til settet med realer. Problemet beløper seg til å finne den minste q slik at q - avslappede skjæringspunktet av de begrensninger som ikke er tom.

Se også

Eksterne linker

Referanser

^ Mark Krentel. Kompleksiteten av optimaliseringsproblemer . Proc. av STOC '86. 1986.
^ Christos Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
^ Cohen, Cooper, Jeavons. En komplett karakterisering av kompleksitet for boolske problemer med optimalisering av begrensninger . CP 2004.
^ Vazirani 2001 , s. 131.
^ Borchers, Brian; Furman, Judith (1998-12-01). "En to-fase nøyaktig algoritme for MAX-SAT og vektede MAX-SAT-problemer". Journal of Combinatorial Optimization . 2 (4): 299–306. doi : 10.1023 / A: 1009725216438 . ISSN 1382-6905 .
^ Du, Dingzhu; Gu, juni; Pardalos, Panos M. (1997-01-01). Tilfredsstillelsesproblem: Teori og applikasjoner: DIMACS Workshop, 11.-13. Mars 1996 . American Mathematical Soc. s. 393. ISBN 9780821870808.
^ Vazirani 2001 , Lemma 16.2.
^ Vazirani 2001 , avsnitt 16.2.
^ Vazirani , s. 136.
^ Vazirani 2001 , teorem 16.9.
^ Vazirani 2001 , eksempel 16.11.
^ R. Battiti og M. Protasi. Approximate Algorithms and Heuristics for MAX-SAT Handbook of Combinatorial Optimization, Vol 1, 1998, 77-148, Kluwer Academic Publishers.
^ Josep Argelich og Felip Manyà. Nøyaktige Max-SAT-løsere for overbegrensede problemer . I Journal of Heuristics 12 (4) s. 375-392. Springer, 2006.
^ Jaulin, L .; Walter, E. (2002). "Garantert robust ikke-lineær minimax estimering" (PDF) . IEEE-transaksjoner med automatisk kontroll . 47 .

Vazirani, Vijay V. (2001), Approximation Algorithms (PDF) , Springer-Verlag, ISBN 978-3-540-65367-7

[1] Mark Krentel. Kompleksiteten av optimaliseringsproblemer . Proc. av STOC '86. 1986.

[2] Christos Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

[3] Cohen, Cooper, Jeavons. En komplett karakterisering av kompleksitet for boolske problemer med optimalisering av begrensninger . CP 2004.

[FOOTNOTEVazirani2001131-4] Vazirani 2001 , s. 131.

[5] Borchers, Brian; Furman, Judith (1998-12-01). "En to-fase nøyaktig algoritme for MAX-SAT og vektede MAX-SAT-problemer". Journal of Combinatorial Optimization . 2 (4): 299–306. doi : 10.1023 / A: 1009725216438 . ISSN 1382-6905 .

[6] Du, Dingzhu; Gu, juni; Pardalos, Panos M. (1997-01-01). Tilfredsstillelsesproblem: Teori og applikasjoner: DIMACS Workshop, 11.-13. Mars 1996 . American Mathematical Soc. s. 393. ISBN 9780821870808.

[FOOTNOTEVazirani2001Lemma_16.2-7] Vazirani 2001 , Lemma 16.2.

[FOOTNOTEVazirani2001Section_16.2-8] Vazirani 2001 , avsnitt 16.2.

[FOOTNOTEVazirani136-9] Vazirani , s. 136.

[FOOTNOTEVazirani2001Theorem_16.9-10] Vazirani 2001 , teorem 16.9.

[FOOTNOTEVazirani2001Example_16.11-11] Vazirani 2001 , eksempel 16.11.

[12] R. Battiti og M. Protasi. Approximate Algorithms and Heuristics for MAX-SAT Handbook of Combinatorial Optimization, Vol 1, 1998, 77-148, Kluwer Academic Publishers.

[13] Josep Argelich og Felip Manyà. Nøyaktige Max-SAT-løsere for overbegrensede problemer . I Journal of Heuristics 12 (4) s. 375-392. Springer, 2006.

[14] Jaulin, L .; Walter, E. (2002). "Garantert robust ikke-lineær minimax estimering" (PDF) . IEEE-transaksjoner med automatisk kontroll . 47 .

Languages

In other projects

Maksimal tilfredsstillelsesproblem - Maximum satisfiability problem

Innhold

Eksempel

Hardhet