constraint programming

constraint programming (tsz. constraint programmings)

1. (informatika, mesterséges intelligencia) A Constraint Programming (korlátozásos programozás, CP) egy erőteljes paradigmája a deklaratív programozásnak, amelyet bonyolult kombinatorikus problémák (pl. ütemezés, erőforrás-kezelés, puzzle-feladatok, konfigurációk stb.) megoldására használnak. Ebben a megközelítésben megoldáskeresés nem algoritmikus lépésekkel, hanem feltételek (korlátozások) megadásával történik, amelyek meghatározzák, milyen tulajdonságokkal rendelkezhet egy érvényes megoldás.

A Constraint Programming egy problémamegoldó keretrendszer, ahol:

• Megadunk egy változókészletet.
• Mindegyik változónak van egy tartománya (domain) – lehetséges értékeinek halmaza.
• Különféle korlátozásokat (constraints) definiálunk a változók között.
• A cél: olyan érékadásokat találni a változókhoz, amelyek mindegyik korlátozást kielégítik.

Sudoku – a rács minden mezője egy változó, tartományuk: {1,2,…,9}. Korlátozás: minden sorban/oszlopban/blokkban minden szám csak egyszer szerepelhet.

Legyenek ${\textstyle X_{1},X_{2},...,X_{n}}$ változók.

Minden változónak van egy értéktartománya ${\textstyle D_{i}}$, azaz ${\textstyle X_{i}\in D_{i}}$.

Például:

• ${\textstyle D_{1}=\{1,2,3,4,5\}}$
• ${\textstyle D_{2}=\{a,b\}}$

Formálisan: ${\textstyle C(X_{i},X_{j},...,X_{k})}$ reláció, amely a változók bizonyos kombinációit engedélyezi.

Példák:

• ${\textstyle X_{1}\neq X_{2}}$
• ${\textstyle X_{3}+X_{4}\leq 10}$
• ${\textstyle {\text{AllDifferent}}(X_{1},...,X_{n})}$

A constraint programming rendszer a következő lépéseket alkalmazza:

Minden lehetséges értékadás a változókhoz. A keresési tér exponenciálisan nagy, de a korlátozások ezt nagymértékben szűkítik.

A leggyakoribb módszer a backtracking (visszalépéses keresés), amely:

1. Választ egy változót.
2. Kipróbálja a lehetséges értékeket.
3. Ha valamelyik megsérti a korlátozást, visszalép.

Ez egy intelligens tartományszűkítési eljárás. A cél: a változók értéktartományát csökkenteni a korlátozások alapján.

Pl.:

• Ha ${\textstyle X+Y=5}$, és ${\textstyle X=2}$, akkor ${\textstyle Y\in \{3\}}$
• Ha egy AllDifferent korlátozásban csak egy érték maradt, más változók nem vehetik fel azt

Hatékony CP rendszerek változó- és érték-választási heurisztikákat alkalmaznak:

• Minimum Remaining Values (válaszd azt a változót, amelyiknek legkevesebb lehetséges értéke van)
• Most Constraining Variable (válaszd azt, amelyik a legtöbb korlátozásban szerepel)

Két változó között (pl. ${\textstyle X\neq Y}$)

Több változóra ható magas szintű korlátozás. Például:

• AllDifferent: minden változó különböző
• Cumulative: erőforrás-használat korlátozása idő szerint (pl. gépek, memória)
• Element: indexelés (pl. ${\textstyle X_{i}=V}$)

• Iskolai órarendek
• Gyártósor optimalizálás
• Repülőgép-karbantartási időpontok

• Munkafolyamat-elosztás gépek között
• Energiafogyasztás optimalizálása

• Hardver-összeszerelés
• Termékopciók érvényessége

• Sudoku
• N-queens
• Kakuro

Feladat: Tegyünk le 4 királynőt 4×4-es táblára úgy, hogy ne üssék egymást!

• Változók: ${\textstyle Q_{1},Q_{2},Q_{3},Q_{4}}$ (oszloponként egy királynő, érték: sor)
• Tartomány: ${\textstyle D_{i}=\{1,2,3,4\}}$
• Korlátozások:
  • ${\textstyle {\text{AllDifferent}}(Q_{1},Q_{2},Q_{3},Q_{4})}$ (nem lehetnek egy sorban)
  • ${\textstyle |Q_{i}-Q_{j}|\neq |i-j|}$ (nem lehetnek egy átlóban)

A CP megoldó keres a feltételeket kielégítő értékadásokat.

• MiniZinc – deklaratív nyelv CP modellezéshez
• Choco Solver – Java alapú CP könyvtár
• Google OR-Tools – támogatja CP-t, MIP-et, SAT-ot
• Gecode – C++ CP könyvtár
• ECLiPSe, SICStus Prolog – logikai programozási nyelvek CP támogatással

A CP folyamatosan fejlődik:

• Hibrid megoldások: CP + MIP/SAT kombinációk
• Tanuló keresés (learning during search)
• Magas szintű modellezőnyelvek
• Magyarázatok (explanations): miért nincs megoldás?

A Constraint Programming:

• Deklaratív megközelítés, a “mit”, nem a “hogyan”-t írjuk le.
• Alapja: változók, tartományok, korlátozások.
• Használ: backtracking, propagation, heurisztikák.
• Nagyon rugalmas és általános kombinatorikus problémákra.
• Sokféle ipari és kutatási alkalmazás van rá.

• constraint programming - Szótár.net (en-hu)
• constraint programming - Sztaki (en-hu)
• constraint programming - Merriam–Webster
• constraint programming - Cambridge
• constraint programming - WordNet
• constraint programming - Яндекс (en-ru)
• constraint programming - Google (en-hu)
• constraint programming - Wikidata
• constraint programming - Wikipédia (angol)