A kényszerkielégítési problémák (angol rövidítéssel CSP) formális definícióját változók (variables), X₁, X₂, …, X_n, és kényszerek (constraints), C₁, C₂, …, C_m halmazaival adhatjuk meg. Minden egyes X_i változó esetén adott a lehetséges értékek egy nem-üres D_i tartománya. Minden egyes C_i kényszer a változók valamely részhalmazára vonatkozik, és meghatározza a részhalmaz megengedett értékkombinációit. Egy problémaállapotot az definiál, hogy vagy néhány, vagy mindegyik változóhoz értékeket rendelünk hozzá {X_i = v_i, X_j = v_j, ...}. Egy hozzárendelést konzisztensnek (vagy megengedettnek) nevezünk, ha egyetlen kényszert sem sért meg. Teljes az a hozzárendelés, amelyben mindegyik változó szerepel, és egy teljes hozzárendelés a kényszerkielégítési problémának megoldása, ha mindegyik kényszert kielégíti. Néhány kényszerkielégítési probléma azt is igényli, hogy a megoldás egy célfüggvényt maximalizáljon.

Mit is jelent mindez? Tegyük fel, hogy Romániába beleunva Ausztrália térképét tanulmányozzuk, és a térképen az 5.1. (a) ábrán feltüntetett államokat és területeket látjuk, feladatunk pedig az, hogy vörössel, zölddel és kékkel minden egyes részt színezzünk ki úgy, hogy a szomszédos részeknek ne legyen azonos a színe. Ahhoz, hogy ezt kényszerkielégítési problémaként fogalmazhassuk meg, változókat kell bevezetnünk az egyes részekhez: NyA, ÉT, Q, ÚDW, V, DA és T. Mindegyik változó tartománya a {vörös, zöld, kék} halmaz. Kényszerek írják elő, hogy a szomszédos részek különböző színűek legyenek, például NyA és ÉT esetén a megengedhető kombinációk az alábbi párok lehetnek:

{(vörös, zöld), (vörös, kék), (zöld, vörös), (zöld, kék), (kék, vörös), (kék, zöld)}

(A kényszert tömörebben is ki lehet fejezni a NyA ≠ ÉT egyenlőtlenséggel, feltéve persze, hogy a kényszermegoldó algoritmus valamiképpen ki tudja értékelni az ilyen kifejezéseket.) Sok lehetséges megoldás adódik, mint például az

{NyA = vörös, ÉT = zöld, Q = vörös, ÚDW = zöld, V = vörös, DA = kék, T = vörös}

Gyakran hasznos lehet, ha felrajzoljuk a kényszerkielégítési probléma kényszergráfját (constraint graph), amint az az 5.1. (b) ábrán is látható. A gráf csomópontjai a probléma változóinak, élei pedig a kényszereknek felelnek meg.

Sok előnnyel járhat, ha egy problémát kényszerkielégítési problémaként tekintünk. Az állapotok reprezentációja miatt a kényszerkielégítési problémák egy standard mintára illeszkednek (ez a minta a hozzárendelt értékekkel rendelkező változók halmaza), az állapotátmenet-függvényt és a célállapottesztet pedig az összes kényszerkielégítési problémára érvényes általános módon meg lehet írni. Sőt létrehozhatók hatékony, általános heurisztikák minden kiegészítő, tárgyterület-specifikus szakértelem nélkül. Végül pedig a kényszergráf struktúrájának segítségével lerövidíthető a megoldási folyamat, és ez néhány esetben exponenciálisan csökkenti a probléma komplexitását. A kényszerkielégítési probléma reprezentációja a legelső (és a legegyszerűbb) a könyv menete során bemutatott reprezentációs sémák sorában.

5.1. ábra - (a) Ausztrália államai és területei. A térkép kiszínezése tekinthető kényszerkielégítési problémának is. A cél az, hogy minden egyes részhez olyan színt találjunk, amely nem azonos egy szomszédos rész színével sem. (b) A térképszínezési probléma kényszergráfként reprezentálva.

Könnyű észrevenni, hogy egy kényszerkielégítési problémára adható egy inkrementális megfogalmazás (incremental formulation), amely a kényszerkielégítési problémát szabályos keresési problémaként tekinti:

A kényszerkielégítési problémák legegyszerűbb esetében a változók diszkrétek és véges tartományúak. A térképszínezési problémák is ehhez az esethez tartoznak. A 3. fejezetben bemutatott 8-királynő problémát is felfoghatjuk véges tartományú kényszerkielégítési problémaként, ahol a Q₁, …, Q₈ változók a királynők 1, …, 8 oszlopokban betöltött pozícióit jelölik, és mindegyik változó tartománya {1, 2, 3, 4, 5, 6, 7, 8}. Amennyiben maximum d a kényszerkielégítési probléma bármely változójához tartozó tartomány mérete, akkor a lehetséges teljes hozzárendelések száma O(dⁿ), azaz a változók számának exponenciális függvénye. A véges tartományú kényszerkielégítési problémák közé tartoznak a Boole-problémák is, ahol a változók értéke vagy igaz, vagy hamis. A Boole kényszerkielégítési problémák speciális esetként tartalmaznak néhány NP-teljes problémát, például a 3SAT-ot (lásd 7. fejezet). Legrosszabb esetben tehát nem lehetséges, hogy exponenciálisnál kevesebb idő alatt meg tudunk oldani egy véges tartományú kényszerkielégítési problémát. A legtöbb gyakorlati alkalmazásban azonban az általános célú CSP algoritmusok megbirkóznak a 3. fejezetben bemutatott általános célú keresési algoritmusokkal megoldhatóknál több nagyságrenddel nagyobb problémákkal is.

A diszkrét változók lehetnek végtelen tartományúak is: például ilyen az egész számok halmaza vagy a füzérek halmaza. Például amikor egy építkezési munka naptárát ütemezzük, minden feladat kezdési ideje egy változó, amelyeknek lehetséges értékei az aktuális dátum napjait megadó egész számok. Végtelen tartományok esetén már nem lehet a kényszereket a megengedett értékkombinációk felsorolásával leírni. Ehelyett egy kényszernyelvet (constraint language) kell használni. Például ha Munka₁ öt napig tart, és meg kell előznie Munka₃-t, akkor kényszernyelvként az algebrai egyenlőtlenségek nyelvére van szükségünk, mint például KezdMunka₁ + 5 ≤ KezdMunka₃. Továbbá az ilyen kényszereket többé már nem lehet megoldani az összes lehetséges hozzárendelés felsorolásával, mert végtelen sok van belőlük. Különleges megoldó algoritmusok (melyekre itt nem térünk ki) léteznek egész értékű változók lineáris kényszereire, azaz olyan kényszerekre, mint a fenti, ahol mindegyik változó csak lineáris műveletekben jelenik meg. Megmutatható, hogy nem létezhet algoritmus egész értékű változók általános nemlineáris kényszereinek megoldására. Néhány esetben az egész értékű kényszerproblémák egyszerűen azzal visszavezethetők véges tartományúakra, hogy korlátozzuk az összes változó értékeit. Egy ütemezési problémában például egy felső korlátot szabhatunk az összes ütemezendő munka teljes hosszára.

A folytonos tartományú kényszerkielégítési problémák elég gyakoriak a valós alkalmazásokban, és az operációkutatáson belül is tanulmányozták ezeket a problémákat. Például a Hubble űrteleszkóp kísérleteinek ütemezése a megfigyelések nagyon pontos időzítését igényli, a megfigyelések és a manőverek kezdeti és befejezési időpontjai folytonos értékű változók és csillagászati, precedencia-, valamint teljesítménykényszerek sokasága vonatkozik rájuk. A folytonos tartományú kényszerkielégítési problémák legismertebb válfaja a lineáris programozási problémák csoportja, ahol a kényszerek konvex tartományt alkotó lineáris egyenlőtlenségek. A lineáris programozási feladatokat meg lehet oldani a változók száma szerinti polinomiális időben. Más típusú kényszerekkel és célfüggvényekkel rendelkező problémákat is tanulmányoztak, például ilyennel foglalkozik a kvadratikus programozás, a másodrendű kónikus programozás és hasonló társaik.

Azon túl, hogy megvizsgálhatjuk a kényszerkielégítési problémákban megjelenő változók típusát, hasznos lehet a kényszerfajtákat is tanulmányozni. A legegyszerűbb fajta az unáris kényszer (unary constraint), amely egy változó értékére tesz megkötést. Elképzelhető például, hogy a délausztrálok élénken tiltakoznak a zöld szín ellen. A hivatkozott változó tartományának előfeldolgozásával mindegyik unáris kényszer kiküszöbölhető: ki kell venni a kényszert sértő összes értéket. A bináris kényszer (binary constraint) két változót köt össze. Például a DA ≠ ÚDW egy bináris kényszer. A csak bináris kényszerekkel rendelkező kényszerkielégítési problémát binárisnak nevezzük, amit az 5.1. (b) ábrán láthatóhoz hasonló kényszergráffal lehet reprezentálni.

A magasabb rendű kényszerek három vagy több változóra vonatkoznak. Ennek egy ismerős példája a betűrejtvény (lásd 5.2. (a) ábra). A betűrejtvényben általában mindegyik betű különböző számot jelöl. Ez a megkötés az 5.2. (a) ábra betűrejtvénye esetén például a hatváltozós MindKül(F,T,U,W,R,O) kényszerrel adható meg. Egy másik megoldás lehet, ha a megkötést bináris kényszerek (mint például F≠T) gyűjteményével adjuk meg. A rejtvény négy oszlopában az összeadáskényszerek több változót is tartalmazhatnak, amelyek a következőképpen írhatók fel:

O + O = R + 10 · X1

X1 + W + W = U + 10 · X2

X2 + T + T = O + 10 · X3

X3 = F

ahol X₁, X₂ és X₃ a következő oszlopba átvitt számjegyet (0 vagy 1) reprezentáló segédváltozók (auxiliary variables). A magasabb rendű kényszereket egy kényszerhipergráffal (constraint hyprergraph) lehet ábrázolni, amelynek egy példája az 5.2. (b) ábrán látható. Az éles szemű olvasónak feltűnhet, hogy a MindKül kényszer felbontható bináris kényszerekre: F ≠ T, F ≠ U stb. Az 5.11. feladat éppen annak bizonyítását kéri, hogy elegendő segédváltozó bevezetésével mindegyik magasabb rendű véges tartományú kényszer átírható bináris kényszerek halmazává. Ebből kiindulva ebben a fejezetben csak bináris kényszerekkel foglalkozunk.

Az eddig említett kényszerek mind abszolút kényszerek voltak: egy kényszer megszegése kizár egy megoldásjelöltet. A valós alkalmazások során azonban sok kényszerkielégítési probléma tartalmaz preferenciakényszereket, melyek jelzik, hogy mely megoldások preferáltak. Egy egyetemi órarend meghatározásakor például X professzor talán inkább reggel tanítana, míg Y professzor a délutáni órákat részesítené előnyben. Egy olyan órarend, amely szerint X professzornak délután kettőkor kellene tanítania, még megoldás lenne (persze csak ha X professzor éppenséggel nem a tanszékvezető), de ez nem lenne optimális megoldás. A preferenciakényszerek gyakran az egyedi változó-hozzárendelések költségeként ábrázolhatók: például ha X professzor egy délutáni időpontot kap, az két pontot ront az általános célfüggvényen, míg a reggeli óraidőpont csak egy pontba kerül. Így megfogalmazva a preferenciákkal kiegészített kényszerkielégítési problémák (útvonalalapú vagy lokális) optimalizációs keresési módszerekkel megoldhatók. Az ilyen kényszerkielégítési problémákkal a fejezetben többet nem foglalkozunk, de az irodalomjegyzékben megadunk néhány kiindulási pontként használható hivatkozást.

5.2. ábra - (a) Egy betűrejtvény. Mindegyik betű különböző számjegyet jelöl, a rejtvény célja olyan számjegyeket helyettesíteni a betűk helyére, amelyekkel a kiadódó összeg aritmetikailag helyes lesz (azzal a külön megkötéssel, hogy nem kezdő nullák nem megengedettek). (b) A betűrejtvény kényszerhipergráfja a MindKül kényszer és az oszloponkénti összeadási kényszerek feltüntetésével. A kényszereket négyzet alakú dobozok jelölik. Minden doboz azzal a változóval van összekötve, amelyre a doboz által jelzett kényszer vonatkozik.