Programare constrângere

Programarea constrângere (CP sau CP pentru programarea constrângere în limba engleză) este o paradigmă de programare a apărut în anii 1970 și 1980 pentru rezolvarea problemelor mari combinatoriale , cum ar fi problemele de planificare și programare. În programarea constrângerilor, separăm partea de modelare utilizând probleme de satisfacție a constrângerilor (sau CSP pentru Constraint Satisfaction Problem ), de partea de rezoluție a cărei particularitate constă în utilizarea activă a constrângerilor problemei pentru a reduce dimensiunea spațiului soluțiilor care urmează să fie acoperit (vorbim de propagarea constrângerilor).

„În informatică, dintre toate abordările de programare, programarea prin constrângere este cea mai apropiată de ideal: utilizatorul descrie problema, computerul o rezolvă. "

- E. Freuder

În contextul programării constrângerilor, problemele sunt modelate folosind variabile de decizie și constrângeri, unde o constrângere este o relație între una sau mai multe variabile care limitează valorile pe care fiecare dintre variabilele le leagă de constrângere. Algoritmii de căutare a soluțiilor, în PPC, se bazează în general pe propagarea constrângerilor, pentru a reduce numărul de soluții candidate care urmează să fie explorate, precum și pe o căutare sistematică între diferitele atribuiri posibile ale fiecărei variabile. Astfel de algoritmi garantează găsirea unei soluții, atunci când există, și fac posibilă demonstrarea faptului că nu există o soluție la o problemă dacă nu au găsit o soluție la sfârșitul căutării exhaustive.

Unul dintre primii rezolvatori de constrângeri este ALICE scris în 1976 de Jean-Louis Laurière .

Problema satisfacerii constrângerilor asupra domeniilor finite

O constrângere este o relație între mai multe variabile care limitează setul de valori pe care aceste variabile le pot lua simultan.

Definiție  -  O problemă de satisfacție a constrângerii pe domenii finite (sau CSP) este definită de un triplet în care: (X,D,VS){\ displaystyle ({\ mathcal {X}}, {\ mathcal {D}}, {\ mathcal {C}})}

• X={X1,...,Xnu}{\ displaystyle {\ mathcal {X}} = \ {x_ {1}, \ dots, x_ {n} \}} este setul de variabile ale problemei;
• D={D1,...,Dnu}{\ displaystyle {\ mathcal {D}} = \ {{\ mathcal {D}} _ {1}, \ dots, {\ mathcal {D}} _ {n} \}}este setul de domenii ale variabilelor, adică pentru tot ce avem ;k∈[1;nu]{\ displaystyle k \ in [1; n]}Xk∈Dk{\ displaystyle x_ {k} \ in {\ mathcal {D}} _ {k}}
• VS={VS1,...,VSm}{\ displaystyle {\ mathcal {C}} = \ {C_ {1}, \ dots, C_ {m} \}}este un set de constrângeri. O constrângere este definită de setul de variabile la care se referă și de relația care definește setul de valori pe care variabilele :VSeu=(Xeu,Reu){\ displaystyle C_ {i} = ({\ mathcal {X}} _ {i}, {\ mathcal {R}} _ {i})}Xeu={Xeu1,...,Xeuk}{\ displaystyle {\ mathcal {X}} _ {i} = \ {x_ {i_ {1}}, \ dots, x_ {i_ {k}} \}}Reu⊂Deu1×⋯×Deuk{\ displaystyle {\ mathcal {R}} _ {i} \ subset {\ mathcal {D}} _ {i_ {1}} \ times \ dots \ times {\ mathcal {D}} _ {i_ {k}} }Xeu{\ displaystyle {\ mathcal {X}} _ {i}}

Când definim o constrângere prin enumerarea setului de valori care satisfac această constrângere, spunem că constrângerea este definită în extensie. Există și alte reprezentări constrângeri precum:

• constrângeri aritmetice ( ) asupra expresiilor;<,>,≤,≥,=,≠{\ displaystyle <,>, \ leq, \ geq, =, \ neq}
• constrângeri logice (disjuncție, implicație etc.);
• constrângeri a căror semantică este descrisă: „toate diferite” etc.

Numim atribuire, faptul de a asocia o valoare a domeniului său unei variabile. În cadrul rezolvării problemelor de satisfacție a constrângerii, vorbim de atribuire parțială atunci când afectăm un subset al tuturor variabilelor problemei și de atribuire totală atunci când afectăm toate variabilele problemei.

Definiție  -  O atribuire a unui CSP este definită de cuplul în care: LA{\ displaystyle {\ mathcal {A}}}P=(X,D,VS){\ displaystyle P = ({\ mathcal {X}}, {\ mathcal {D}}, {\ mathcal {C}})}LA=(XLA,VLA){\ displaystyle {\ mathcal {A}} = ({\ mathcal {X _ {\ mathcal {A}}}}, {\ mathcal {V _ {\ mathcal {A}}}})}

• XLA⊂X{\ displaystyle {\ mathcal {X _ {\ mathcal {A}}}} \ subset {\ mathcal {X}}} este un subset de variabile;
• VLA={vLA1,...,vLAk}∈{DLA1,...,DLAk}{\ displaystyle {\ mathcal {V _ {\ mathcal {A}}}} = \ {v _ {{\ mathcal {A}} _ {1}}, \ dots, v _ {{\ mathcal {A}} _ {k}} \} \ in \ {{\ mathcal {D}} _ {{\ mathcal {A}} _ {1}}, \ dots, {\ mathcal {D}} _ {{\ mathcal {A }} _ {k}} \}} este tuplul valorilor luate de variabilele afectate.

Spunem că o atribuire este parțială atunci când setul de variabile afectate este diferit de setul de variabile din problemă, altfel vorbim de atribuire totală.

Proprietate  -  Fie o atribuire (parțială sau totală) a unui CSP și o constrângere , astfel încât , asignarea satisface constrângerea dacă și numai dacă setul de valori ale variabilelor pe care se referă constrângerea aparține . LA=(XLA,VLA){\ displaystyle {\ mathcal {A}} = ({\ mathcal {X _ {\ mathcal {A}}}}, {\ mathcal {V _ {\ mathcal {A}}}})}P=(X,D,VS){\ displaystyle P = ({\ mathcal {X}}, {\ mathcal {D}}, {\ mathcal {C}})}VSeu=(Xeu,Reu){\ displaystyle C_ {i} = ({\ mathcal {X}} _ {i}, {\ mathcal {R}} _ {i})}P{\ displaystyle P}Xeu⊂XLA{\ displaystyle {\ mathcal {X}} _ {i} \ subset {\ mathcal {X _ {\ mathcal {A}}}}}LA{\ displaystyle {\ mathcal {A}}}VSeu{\ displaystyle C_ {i}}VLAeu={veu∈VLA ca Xeu∈Xeu}{\ displaystyle {\ mathcal {V}} _ {{\ mathcal {A}} _ {i}} = \ {v_ {i} \ in {\ mathcal {V}} _ {\ mathcal {A}} {\ mbox {cum ar fi}} x_ {i} \ în {\ mathcal {X}} _ {i} \}}VSeu{\ displaystyle C_ {i}}Reu{\ displaystyle {\ mathcal {R}} _ {i}}

Definiție  -  O soluție a unui CSP este o atribuire totală care satisface setul de constrângeri.

Când căutați soluții la o problemă de satisfacție a constrângerii, s-ar putea dori, de exemplu:

• găsiți o soluție (satisfacerea tuturor constrângerilor);
• găsiți toate soluțiile la problemă;
• găsiți o soluție optimă în ceea ce privește un criteriu (în general minimizarea sau maximizarea unei variabile);
• dovediți inexistența unei soluții (în cazul unei probleme supra-constrânse).

Căutând soluții

Căutare în copaci

În cazul rezoluției pe domenii finite, în teorie este posibil să enumerăm toate posibilitățile și să verificăm dacă acestea încalcă sau nu constrângerile, această metodă se numește generare și testare . Cu toate acestea, acest lucru se dovedește impracticabil pentru problemele de dimensiuni medii datorită numărului mare de combinații posibile. Una dintre părțile majore ale rezoluției, numită „filtrare”, își propune să evite această enumerare exhaustivă. Constă în deducerea din constrângeri a valorilor imposibile. Când o variabilă are un singur candidat, aceasta este instanțiată (adică i se atribuie această valoare). Cu toate acestea, filtrarea singură nu instanțiază toate variabilele și, prin urmare, este necesar să împărțiți problema în mai multe părți (de exemplu prin instanțierea unei variabile la fiecare dintre valorile sale posibile) și reporniți filtrarea pe una dintre aceste părți și aceasta, un mod recursiv până la obținerea instanțierii tuturor variabilelor. Când filtrarea detectează că instanțierea parțială încalcă o constrângere, atunci se folosește în general un mecanism de feedback pentru a pune la îndoială ultima alegere făcută.

Această serie de defecțiuni ale problemei poate fi reprezentată sub forma unui copac . Scopul cercetării este de a parcurge acest arbore (construindu-l pe măsură ce mergeți) până când se găsește o soluție la problemă, în timp ce filtrarea constă în „tăierea” acestui arbore prin îndepărtarea tuturor părților rezultând doar în contradicții.

Propagarea constrângerilor

Propagarea constrângerilor (sau filtrarea) constă în eliminarea dintr-o problemă PPC a valorilor variabilelor care nu pot lua parte la o soluție. Pentru a accelera căutarea unei soluții la o problemă, este necesar să se obțină un compromis bun între timpul necesar filtrării și eficacitatea acesteia. Acesta este motivul pentru care există mai multe niveluri de eficiență a filtrării, capabile să elimine mai multe sau mai puține valori, pentru un cost mai mult sau mai puțin ridicat în timp. Deoarece toate constrângerile unei probleme PPC trebuie îndeplinite, faptul că o valoare a unei variabile nu poate satisface o singură constrângere a problemei implică faptul că nu poate lua parte la nicio soluție a problemei. Prin urmare, este posibil să se argumenteze separat pe fiecare constrângere pentru a putea găsi valori pentru care această constrângere nu poate fi satisfăcută și, prin urmare, pentru a le elimina din întreaga problemă.

Se numește consistență locală faptul de a verifica dacă anumite variabile nu încalcă constrângerile care sunt legate de aceasta. Celelalte variabile și constrângeri sunt apoi ignorate. Acest lucru face posibilă filtrarea anumitor valori imposibile la un cost redus. Există mai multe consistențe locale, fiecare oferind un echilibru diferit între eficiența filtrării și viteza de calcul.

Extensii

• constrângeri apreciate
• constrângeri globale
• studiul și detectarea simetriilor
• tehnici de descompunere și clase de probleme „tratabile”
• metaheuristică
• faza de tranzitie

Exemple de probleme

Printre problemele clasice care pot fi tratate prin programarea constrângerilor, putem menționa:

• problema celor opt regine , care constă în plasarea a opt regine pe o tablă de șah, astfel încât nici o regină să nu poată lua alta;
• sudoku , în cazul în care va trebui să completați o grilă de 9x9 cu cifre de la 1 la 9 , astfel încât fiecare cifră apare o singură dată în fiecare rând, coloană și 3x3 dimensiunea sub-cutie.

Rezolvarea constrângerilor

• Software academic
  • Prolog III (1989)
  • MiniCP (bibliotecă Java pentru predarea programării constrângerilor. Licență gratuită) (2018)
• Software comercial
  • Artelys Kalis ( biblioteci C ++ , Java , Python , modulul suitei FICO Xpress)
  • CHIP V5 ( C , C ++ , Prolog) (1988)
  • Cometa (limbaj orientat pe obiecte pentru rezolvarea problemelor de constrângere. Utilizare academică gratuită.)
  • Disolver (Biblioteca C ++ )
  • IBM CP Optimizer, succesorul ILOG Solver / Scheduler ( biblioteci C ++ , Python, Java , .NET )
  • Jekejeke Minlog (Biblioteca Prolog)
  • Prolog IV (1996)
• Software gratuit licențiat
  • AbsCon (Biblioteca Java )
  • Choco (bibliotecă Java , software gratuit: stil X11)
  • Cream (Biblioteca Java )
  • Eclipse Prolog (Biblioteca Prolog)
  • Gecode (Biblioteca C ++ )
  • Google OR-tools ( bibliotecă C ++ , legări Java , C # , Python )
  • JaCoP (Biblioteca Java )
  • JOpt (Biblioteca Java )
  • Minion ( C ++ )
  • OscaR ( Scala )
  • Scarab (Biblioteca Scala )
  • python-constraint ( Python Library )

Bibliografie

• (en) Thom Frühwirth și Slim Abdennadher , Essentials of Constraint Programming , Springer ,aprilie 2003, 145  p. [ detaliu ediții ] ( ISBN  978-3-540-67623-2 , prezentare online )
• (ro) Francesca Rossi , Peter Van Beek și Toby Walsh , Manual de programare a constrângerilor , Elsevier,2006[ detaliu ediții ] ( ISBN  978-0-444-52726-4 , prezentare online )
• Annick Fron, Constraint Programming, The Book Edition, ( ISBN  978-2879080628 )
• (ro) Trends in Constraint Programming, editat de Frédéric Benhamou, Narendra Jussien, Barry O'Sullivan, © ISTE Ltd, 2007 ( ISBN  978-1-905-209-97-2 )

Note și referințe

1. Mackworth, Coerența în rețelele de relații, Inteligența artificială , 9: 99-118, 1977
2. Haralick, Eliott, Creșterea eficienței căutării copacilor pentru probleme de satisfacție a constrângerilor, inteligență artificială , 14: 263-313, 1980
3. Roman Bartak, Un ghid pentru programarea constrângerilor, 1998
4. E. Freuder. „Programarea constrângerilor reprezintă una dintre cele mai apropiate abordări pe care informatică le-a făcut încă Sfântului Graal al programării: utilizatorul afirmă problema, computerul o rezolvă”.
5. Jean-Louis Laurière , Un limbaj și un program pentru a afirma și rezolva probleme combinatorii , Paris, Teză de stat, Universitatea Pierre și Marie Curie,1976, 227  p. ( SUDOC  029557313 )
6. (en) Jean-Louis Laurière , „  Un limbaj și un program pentru rezolvarea problemelor combinatorii și declararea  ” , Inteligență artificială , vol.  10, n o  1, Februarie 1978, p.  29-127 ( citit online , consultat la 7 ianuarie 2018 )
7. (în) Pierre Flener, „  Constraint Programming in a Nutshell  ” , ACP și GOR RO Joint Summer School 2017 pe link ,18-19 09 2017(accesat la 7 ianuarie 2018 )
8. Introducerea constrângerilor globale în CHIP N. Beldiceanu, E. Contejean, Modelare matematică și computerizată, decembrie 1994, Elsevier
9. „  www.minicp.org  ” , la www.minicp.org (accesat la 4 octombrie 2019 )
10. Limbajul de programare logică constrângere CHIP, Proceedings of international conference on Fifth Generation Computer Systems FGCS-88 (1988), pp. 693-702
11. (în) „  IBM ILOG CP Optimizer  ” pe ibm.com .
12. Laborie P, Rogerie J, Shaw P, Vilim P, „  IBM ILOG CP optimizer for scheduling  ”, Constraints , vol.  23, n o  22018, p.  210–250 ( DOI  10.1007 / s10601-018-9281-x )
13. (în) „  docplex 2.10.154  ” pe python.org .
14. Tendințe în programarea constrângerilor

Vezi și tu

Articole similare

• Problema satisfacției constrângerii
• Programare logică

linkuri externe

• AFPC  : Asociație franceză pentru programarea constrângerilor
• Articol despre utilizarea sudokuului ca instrument educațional pentru PPC
• (ro) Global Constraint Catalog  : catalog of global constraints (N. Beldiceanu)

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">