Optimizare pseudo-booleană quadratică

Optimizarea pseudo-booleană quadratică ( QPBO ) este o metodă de optimizare discretă a funcțiilor pseudo-booleene quadratice non- submodulare sub forma

f(\mathbf {x} )=w_{0}+\sum _{p\in V}w_{p}(x_{p})+\sum _{(p,q)\in E}w_{pq}(x_{p},x_{q})

{\ displaystyle f (\ mathbf {x}) = w_ {0} + \ sum _ {p \ in V} w_ {p} (x_ {p}) + \ sum _ {(p, q) \ in E} w_ {pq} (x_ {p}, x_ {q})}

{\ displaystyle f (\ mathbf {x}) = w_ {0} + \ sum _ {p \ in V} w_ {p} (x_ {p}) + \ sum _ {(p, q) \ in E} w_ {pq} (x_ {p}, x_ {q})}

în variabile binare $x_{p}\in \{0,1\}\;\forall p\in V=\{1,\dots ,n\}$ ${\ displaystyle x_ {p} \ in \ {0,1 \} \; \ forall p \ in V = \ {1, \ dots, n \}}$ ${\ displaystyle x_ {p} \ in \ {0,1 \} \; \ forall p \ in V = \ {1, \ dots, n \}}$ , cu $E\subseteq V\times V$ ${\ displaystyle E \ subseteq V \ times V}$ ${\ displaystyle E \ subseteq V \ times V}$ . De sine $f$ ${\ displaystyle f}$ $f$ este submodular QPBO produce un optim global într-un mod echivalent cu tăierea graficului , în timp ce dacă $f$ ${\ displaystyle f}$ $f$ conține termeni non-submodulari algoritmul produce o soluție parțială cu proprietăți de optimitate specifice, în ambele cazuri în timp polinomial. ^[1]

QPBO este utilizat în inferență asupra câmpurilor Markov aleatorii (MRF) și câmpurilor condiționate aleatorii (CRF) și are aplicații în probleme de vedere computerizată, cum ar fi segmentarea și potrivirea stereo . ^[2]

Optimizarea funcțiilor non-submodulare

Dacă coeficienții $w_{pq}$ ${\ displaystyle w_ {pq}}$ ${\ displaystyle w_ {pq}}$ unii termeni pătratici satisfac condiția submodularității

w_{pq}(0,0)+w_{pq}(1,1)\leq w_{pq}(0,1)+w_{pq}(1,0)

{\ displaystyle w_ {pq} (0,0) + w_ {pq} (1,1) \ leq w_ {pq} (0,1) + w_ {pq} (1,0)}

{\ displaystyle w_ {pq} (0,0) + w_ {pq} (1,1) \ leq w_ {pq} (0,1) + w_ {pq} (1,0)}

atunci funcția poate fi optimizată prin tăierea graficului . De fapt, este posibil să-l reprezentăm printr-un grafic cu greutăți non-negative, iar minimul global poate fi determinat în timp polinomial printr-o reducere minimă a graficului, care poate fi calculată eficient cu algoritmi precum cei de la Ford-Fulkerson , Edmonds-Karp și Boykov- Kolmogorov .

Dacă condiția submodularității nu este satisfăcută, problema în cazul general este NP-hard și nu poate fi întotdeauna rezolvată exact în timp polinomial cu o simplă tăiere grafică. Este posibilă aproximarea funcției obiective cu o funcție similară, dar submodulară, de exemplu prin eliminarea termenilor non-submodulari sau înlocuirea lor cu o aproximare submodulară, dar această abordare produce în general rezultate sub-optime a căror calitate este acceptabilă numai dacă numărul de termenii nu este submodular este relativ mic. ^[1]

QPBO construiește un grafic extins, introducând un set de variabile auxiliare ideal echivalent cu negarea variabilelor problemei. Funcția asociată acestui grafic este submodulară și poate fi optimizată prin tăierea graficului: dacă nodurile graficului asociate cu o variabilă sunt separate de tăierea minimă în diferite componente conectate, valoarea variabilei este definită, în timp ce dacă nodurile sunt în aceeași componentă, valoarea variabilei nu este definită, este posibil să se deducă valoarea optimă a variabilei corespunzătoare. Această metodă produce în general rezultate superioare în comparație cu soluția prin tăierea grafică a aproximărilor submodulare ale funcțiilor non-submodulare. ^[1]

Proprietate

QPBO produce o soluție în care variabilele pot lua trei valori diferite, adevărat , fals și nedefinit , notate mai jos cu 1, 0 și respectiv $\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$ . Soluția produsă de QPBO are două proprietăți, cunoscute sub numele de optimitate parțială și persistență .

Optimitate parțială : dacă $f$ ${\ displaystyle f}$ $f$ este submodular, QPBO calculează minimul global exact într-un mod echivalent cu tăierea graficului și toate variabilele din soluție iau o valoare nedefinită, în timp ce dacă condiția de submodularitate nu este satisfăcută, rezultatul va fi o soluție parțială $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ în care numai pentru un subset ${\hat {V}}\subseteq V$ ${\ displaystyle {\ hat {V}} \ subseteq V}$ ${\ displaystyle {\ hat {V}} \ subseteq V}$ dintre variabile presupune o valoare care nu este nedeterminată. Această soluție parțială face întotdeauna parte dintr-o soluție optimă, adică există un punct minim global $\mathbf {x^{*}}$ ${\ displaystyle \ mathbf {x ^ {*}}}$ ${\ displaystyle \ mathbf {x ^ {*}}}$ din $f$ ${\ displaystyle f}$ $f$ astfel încât $x_{i}=x_{i}^{*}$ ${\ displaystyle x_ {i} = x_ {i} ^ {*}}$ ${\ displaystyle x_ {i} = x_ {i} ^ {*}}$ pentru fiecare $i\in {\hat {V}}$ ${\ displaystyle i \ in {\ hat {V}}}$ ${\ displaystyle i \ in {\ hat {V}}}$ .
Persistență : dată o soluție $\mathbf {x}$ ${\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ produs de QPBO și orice atribuire de valori $\mathbf {y}$ ${\ displaystyle \ mathbf {y}}$ ${\ mathbf {y}}$ la variabilele problemei, dacă se construiește o nouă soluție ${\hat {\mathbf {y} }}$ ${\ displaystyle {\ hat {\ mathbf {y}}}}$ ${\ hat {{\ mathbf {y}}}}$ înlocuind $y_{i}$ ${\ displaystyle y_ {i}}$ $y_ {i}$ cu $x_{i}$ ${\ displaystyle x_ {i}}$ $x_i$ pentru fiecare $i\in {\hat {V}}$ ${\ displaystyle i \ in {\ hat {V}}}$ ${\ displaystyle i \ in {\ hat {V}}}$ , da $f({\hat {\mathbf {y} }})\leq f(\mathbf {y} )$ ${\ displaystyle f ({\ hat {\ mathbf {y}}}) \ leq f (\ mathbf {y})}$ ${\ displaystyle f ({\ hat {\ mathbf {y}}}) \ leq f (\ mathbf {y})}$ . ^[1]

Algoritm

Grafic care reprezintă o funcție a două variabile

x_{p}

{\ displaystyle x_ {p}}

x_ {p}

Și

x_{q}

{\ displaystyle x_ {q}}

{\ displaystyle x_ {q}}

Algoritmul poate fi împărțit în trei părți principale: construcția graficului, calculul unei tăieturi minime și atribuirea valorilor rezultate variabilelor.

În construcția graficului, setul de noduri $V.$ ${\ displaystyle V}$ $V.$ constă din nodurile sursă $s$ ${\ displaystyle s}$ $s$ si bine $t$ ${\ displaystyle t}$ $t$ , plus o pereche de noduri $p$ ${\ displaystyle p}$ $p$ Și $p^{'}$ ${\ displaystyle p '}$ $p '$ pentru fiecare variabilă. După transformarea funcției obiective $f$ ${\ displaystyle f}$ $f$ în formă normală, ^[3] pentru fiecare termen $w$ ${\ displaystyle w}$ $w$ adăugați o pereche de margini în grafic:

la fiecare termen $w_{p}(0)$ ${\ displaystyle w_ {p} (0)}$ ${\ displaystyle w_ {p} (0)}$ arcurile se potrivesc $p\rightarrow t$ ${\ displaystyle p \ rightarrow t}$ ${\ displaystyle p \ rightarrow t}$ Și $s\rightarrow p'$ ${\ displaystyle s \ rightarrow p '}$ ${\ displaystyle s \ rightarrow p '}$ , cu greutăți ${\frac {1}{2}}w_{p}(0)$ ${\ displaystyle {\ frac {1} {2}} w_ {p} (0)}$ ${\ displaystyle {\ frac {1} {2}} w_ {p} (0)}$ ;
la fiecare termen $w_{p}(1)$ ${\ displaystyle w_ {p} (1)}$ ${\ displaystyle w_ {p} (1)}$ arcurile se potrivesc $s\rightarrow p$ ${\ displaystyle s \ rightarrow p}$ ${\ displaystyle s \ rightarrow p}$ Și $p'\rightarrow t$ ${\ displaystyle p '\ rightarrow t}$ ${\ displaystyle p '\ rightarrow t}$ , cu greutăți ${\frac {1}{2}}w_{p}(1)$ ${\ displaystyle {\ frac {1} {2}} w_ {p} (1)}$ ${\ displaystyle {\ frac {1} {2}} w_ {p} (1)}$ ;
la fiecare termen $w_{pq}(0,1)$ ${\ displaystyle w_ {pq} (0,1)}$ ${\ displaystyle w_ {pq} (0,1)}$ arcurile se potrivesc $p\rightarrow q$ ${\ displaystyle p \ rightarrow q}$ $p \ rightarrow q$ Și $q'\rightarrow p'$ ${\ displaystyle q '\ rightarrow p'}$ ${\ displaystyle q '\ rightarrow p'}$ , cu greutăți ${\frac {1}{2}}w_{pq}(0,1)$ ${\ displaystyle {\ frac {1} {2}} w_ {pq} (0,1)}$ ${\ displaystyle {\ frac {1} {2}} w_ {pq} (0,1)}$ ;
la fiecare termen $w_{pq}(1,0)$ ${\ displaystyle w_ {pq} (1,0)}$ ${\ displaystyle w_ {pq} (1,0)}$ arcurile se potrivesc $q\rightarrow p$ ${\ displaystyle q \ rightarrow p}$ ${\ displaystyle q \ rightarrow p}$ Și $p'\rightarrow q'$ ${\ displaystyle p '\ rightarrow q'}$ ${\ displaystyle p '\ rightarrow q'}$ , cu greutăți ${\frac {1}{2}}w_{pq}(1,0)$ ${\ displaystyle {\ frac {1} {2}} w_ {pq} (1,0)}$ ${\ displaystyle {\ frac {1} {2}} w_ {pq} (1,0)}$ ;
la fiecare termen $w_{pq}(0,0)$ ${\ displaystyle w_ {pq} (0,0)}$ ${\ displaystyle w_ {pq} (0,0)}$ arcurile se potrivesc $p\rightarrow q'$ ${\ displaystyle p \ rightarrow q '}$ ${\ displaystyle p \ rightarrow q '}$ Și $q\rightarrow p'$ ${\ displaystyle q \ rightarrow p '}$ ${\ displaystyle q \ rightarrow p '}$ , cu greutăți ${\frac {1}{2}}w_{pq}(0,0)$ ${\ displaystyle {\ frac {1} {2}} w_ {pq} (0,0)}$ ${\ displaystyle {\ frac {1} {2}} w_ {pq} (0,0)}$ ;
la fiecare termen $w_{pq}(1,1)$ ${\ displaystyle w_ {pq} (1,1)}$ ${\ displaystyle w_ {pq} (1,1)}$ arcurile se potrivesc $q'\rightarrow p$ ${\ displaystyle q '\ rightarrow p}$ ${\ displaystyle q '\ rightarrow p}$ Și $p'\rightarrow q$ ${\ displaystyle p '\ rightarrow q}$ ${\ displaystyle p '\ rightarrow q}$ , cu greutăți ${\frac {1}{2}}w_{pq}(1,1)$ ${\ displaystyle {\ frac {1} {2}} w_ {pq} (1,1)}$ ${\ displaystyle {\ frac {1} {2}} w_ {pq} (1,1)}$ .

Tăierea minimă a graficului poate fi calculată cu un algoritm de flux maxim . În general, graficul poate admite mai multe tăieturi minime, care corespund unor soluții parțiale diferite, totuși este posibil să se construiască o tăietură care să lase cel mai mic număr posibil de variabile nedefinite. Odată calculată reducerea minimă, fiecare variabilă primește o valoare în funcție de poziția nodurilor respective $p$ ${\ displaystyle p}$ $p$ Și $p^{'}$ ${\ displaystyle p '}$ $p '$ : de sine $p$ ${\ displaystyle p}$ $p$ aparține componentei conectate care conține sursa e $p^{'}$ ${\ displaystyle p '}$ $p '$ aparține componentei care conține fântâna, valoarea $p$ ${\ displaystyle p}$ $p$ va fi 0, invers dacă $p$ ${\ displaystyle p}$ $p$ aparține componentei care conține fântâna e $p^{'}$ ${\ displaystyle p '}$ $p '$ la cel care conține sursa, valoarea lui $p$ ${\ displaystyle p}$ $p$ va fi 1. Dacă ambele noduri $p$ ${\ displaystyle p}$ $p$ Și $p^{'}$ ${\ displaystyle p '}$ $p '$ aparțin aceleiași componente conectate, valoarea va fi nedefinită. ^[2]

În ceea ce privește variabilele a căror valoare rezultată este nedefinită, modul în care pot fi tratate depinde de problemă. În general, având în vedere două soluții optime pentru două partiții ale graficului, este posibil să le combinați într-o singură soluție optimă pentru întreaga problemă în timp liniar, ^[4] totuși găsirea unei soluții optime pentru variabilele nedeterminate rămâne un NP-hard problemă. În contextul algoritmilor iterativi, cum ar fi expansiunea α, o soluție rezonabilă este de a lăsa neschimbată valoarea lor, deoarece proprietatea de persistență garantează o valoare non-crescătoare a funcției obiective. ^[1] Există mai multe strategii exacte sau aproximative pentru a încerca să reducem numărul de variabile nedeterminate. ^[2]

Termeni de comandă superioară

Optimizarea funcțiilor pseudo-booleene de ordin superior, adică conținerea termenilor dependenți de trei sau mai multe variabile, este, în general, o problemă dificilă. Este întotdeauna posibil să se reducă în timp polinomial o funcție de ordin superior la o funcție pătratică echivalentă în ceea ce privește problema de optimizare (problema cunoscută sub numele de reducere a clicului de ordin superior , HOCR), iar rezultatul acestei reduceri poate fi optimizat cu QPBO. Metodele generale pentru reducerea funcțiilor arbitrare se bazează pe tehnici adecvate de substituire a sub-expresiei și necesită în general introducerea de variabile auxiliare. ^[5] În practică, pentru majoritatea termenilor de ordin superior este posibil să se calculeze exact o reducere fără a adăuga variabile auxiliare, rezultând o problemă de optimizare mai simplă; pentru termenii ireductibili rămași este posibil să se calculeze o reducere exactă cu metode mai generale, prin adăugarea de variabile auxiliare sau prin efectuarea unei reduceri aproximative fără a adăuga noi variabile. ^[6]

Notă

^ ^a ^b ^c ^d ^și Kolmogorov și Rother , pp. 1274-1279 .
^ ^a ^b ^c Rother și colab. , pp. 1-8 .
^ Reprezentarea unei funcții pseudo-booleene prin intermediul coeficienților $w$ $=$ $($ $w$ $0$ $,$ $w$ $1$ $,$ $...$ $,$ $w$ $n$ $n$ $)$ ${\ displaystyle \ mathbf {w} = (w_ {0}, w_ {1}, \ dots, w_ {nn})}$ ${\ displaystyle \ mathbf {w} = (w_ {0}, w_ {1}, \ dots, w_ {nn})}$ nu este unic și dacă există doi vectori de coeficient $w$ ${\ displaystyle \ mathbf {w}}$ $\ mathbf {w}$ Și $w$ $'$ ${\ displaystyle \ mathbf {w} '}$ ${\ displaystyle \ mathbf {w} '}$ pot reprezenta atunci aceeași funcție $w$ $'$ ${\ displaystyle \ mathbf {w} '}$ ${\ displaystyle \ mathbf {w} '}$ se numește reparameterizare a $w$ ${\ displaystyle \ mathbf {w}}$ $\ mathbf {w}$ si invers. În unele construcții este util să vă asigurați că funcția are o formă specială, numită formă normală, care este întotdeauna definită pentru fiecare funcție și nu este unică. O functie $f$ ${\ displaystyle f}$ $f$ se spune în formă normală dacă sunt îndeplinite următoarele două condiții ( Kolmogorov și Rother , pp. 1274-1279 ):
1. $\min\{w_{p}^{0},w_{p}^{1}\}=0$ ${\ displaystyle \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \} = 0}$ ${\ displaystyle \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \} = 0}$ pentru fiecare $p\in V$ ${\ displaystyle p \ în V}$ ${\ displaystyle p \ în V}$ ;
2. $\min\{w_{pq}^{0j},w_{pq}^{1j}\}=0$ ${\ displaystyle \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \} = 0}$ ${\ displaystyle \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \} = 0}$ pentru fiecare $(p,q)\in E$ ${\ displaystyle (p, q) \ în E}$ ${\ displaystyle (p, q) \ în E}$ și pentru fiecare $j\in \{0,1\}$ ${\ displaystyle j \ in \ {0,1 \}}$ ${\ displaystyle j \ in \ {0,1 \}}$ .
Având o funcție arbitrară $f$ {\ displaystyle f} $f$ , este întotdeauna posibil să se determine reparametrizarea sa în formă normală prin intermediul unui algoritm în două faze ( Kolmogorov și Rother , pp. 1274-1279 ):
1. atâta timp cât există indici $($ $p$ $,$ $q$ $)$ $\in$ $ȘI$ {\ displaystyle (p, q) \ în E} ${\ displaystyle (p, q) \ în E}$ Și $j$ $\in$ ${$ $0$ $,$ $1$ $}$ {\ displaystyle j \ in \ {0,1 \}} ${\ displaystyle j \ in \ {0,1 \}}$ care încalcă a doua condiție a normalității, se fac înlocuiri
  - $w_{pq}^{0j}$ ${\ displaystyle w_ {pq} ^ {0j}}$ ${\ displaystyle w_ {pq} ^ {0j}}$ cu $w_{pq}^{0j}-a$ ${\ displaystyle w_ {pq} ^ {0j} -a}$ ${\ displaystyle w_ {pq} ^ {0j} -a}$
  - $w_{pq}^{1j}$ ${\ displaystyle w_ {pq} ^ {1j}}$ ${\ displaystyle w_ {pq} ^ {1j}}$ cu $w_{pq}^{1j}-a$ ${\ displaystyle w_ {pq} ^ {1j} -a}$ ${\ displaystyle w_ {pq} ^ {1j} -a}$
  - $w_{q}^{j}$ ${\ displaystyle w_ {q} ^ {j}}$ ${\ displaystyle w_ {q} ^ {j}}$ cu $w_{q}^{j}+a$ ${\ displaystyle w_ {q} ^ {j} + a}$ ${\ displaystyle w_ {q} ^ {j} + a}$
  unde este $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ ${\ displaystyle a = \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \}}$ ${\ displaystyle a = \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \}}$ ;
2. pentru fiecare $p$ $=$ $1$ $,$ $...$ $,$ $n$ {\ displaystyle p = 1, \ dots, n} ${\ displaystyle p = 1, \ dots, n}$ , se fac înlocuiri
  - $w_{0}$ ${\ displaystyle w_ {0}}$ $w_ {0}$ cu $w_{0}+a$ ${\ displaystyle w_ {0} + a}$ ${\ displaystyle w_ {0} + a}$
  - $w_{p}^{0}$ ${\ displaystyle w_ {p} ^ {0}}$ ${\ displaystyle w_ {p} ^ {0}}$ cu $w_{p}^{0}-a$ ${\ displaystyle w_ {p} ^ {0} -a}$ ${\ displaystyle w_ {p} ^ {0} -a}$
  - $w_{p}^{1}$ ${\ displaystyle w_ {p} ^ {1}}$ ${\ displaystyle w_ {p} ^ {1}}$ cu $w_{p}^{1}-a$ ${\ displaystyle w_ {p} ^ {1} -a}$ ${\ displaystyle w_ {p} ^ {1} -a}$
  unde este $a=\min\{w_{p}^{0},w_{p}^{1}\}$ ${\ displaystyle a = \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \}}$ ${\ displaystyle a = \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \}}$ .
^ Billionnet și Jaumard , pp. 161-163 .
^ Fix și colab. , pp. 1020-1027 .
^ Ishikawa , pp. 1362-1369 .

Bibliografie

Alain Billionnet, Brigitte Jaumard, O metodă de descompunere pentru minimizarea funcțiilor pseudo-booleene pătratice , în Operations Research Letters , vol. 8, nr. 3, Elsevier, 1989, pp. 161–163.
Alexander Fix, Aritanan Gruber, Endre Boros și Ramin Zabih, IEEE International Conference on Computer Vision , Un algoritm tăiat grafic pentru câmpuri aleatorii Markov de ordin superior , 2011, pp. 1020-1027.
Hiroshi Ishikawa, Reducerea clicii de ordin superior fără variabile auxiliare , IEEE Conference on Computer Vision and Pattern Recognition , IEEE, 2014, pp. 1362-1269.
Vladimir Kolmogorov și Carsten Rother, Minimizarea funcțiilor nesubmodulare: o revizuire , în IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 29, nr. 7, IEEE, iulie 2007, pp. 1274-1279.
Carsten Rother, Vladimir Kolmogorov, Victor Lempitsky, Martin Szummer, Optimizarea MRF-urilor binare prin dualitatea extinsă a acoperișului , IEEE Conference on Computer Vision and Pattern Recognition , 2007, pp. 1-8.

linkuri externe

Implementarea C ++ a QPBO , distribuită sub licența GPL , de Vladimir Kolmogorov.
Implementarea C ++ a HOCR , distribuită sub licența MIT , de către Hiroshi Ishikawa.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[review-1] și Kolmogorov și Rother , pp. 1274-1279 .

[rother-2] Rother și colab. , pp. 1-8 .

[normal_form-3] Reprezentarea unei funcții pseudo-booleene prin intermediul coeficienților $\mathbf {w} =(w_{0},w_{1},\dots ,w_{nn})$ ${\ displaystyle \ mathbf {w} = (w_ {0}, w_ {1}, \ dots, w_ {nn})}$ ${\ displaystyle \ mathbf {w} = (w_ {0}, w_ {1}, \ dots, w_ {nn})}$ nu este unic și dacă există doi vectori de coeficient $\mathbf {w}$ ${\ displaystyle \ mathbf {w}}$ $\ mathbf {w}$ Și $\mathbf {w} '$ ${\ displaystyle \ mathbf {w} '}$ ${\ displaystyle \ mathbf {w} '}$ pot reprezenta atunci aceeași funcție $\mathbf {w} '$ ${\ displaystyle \ mathbf {w} '}$ ${\ displaystyle \ mathbf {w} '}$ se numește reparameterizare a $\mathbf {w}$ ${\ displaystyle \ mathbf {w}}$ $\ mathbf {w}$ si invers. În unele construcții este util să vă asigurați că funcția are o formă specială, numită formă normală, care este întotdeauna definită pentru fiecare funcție și nu este unică. O functie $f$ ${\ displaystyle f}$ $f$ se spune în formă normală dacă sunt îndeplinite următoarele două condiții ( Kolmogorov și Rother , pp. 1274-1279 ):
$\min\{w_{p}^{0},w_{p}^{1}\}=0$ ${\ displaystyle \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \} = 0}$ ${\ displaystyle \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \} = 0}$ pentru fiecare $p\in V$ ${\ displaystyle p \ în V}$ ${\ displaystyle p \ în V}$ ;
$\min\{w_{pq}^{0j},w_{pq}^{1j}\}=0$ ${\ displaystyle \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \} = 0}$ ${\ displaystyle \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \} = 0}$ pentru fiecare $(p,q)\in E$ ${\ displaystyle (p, q) \ în E}$ ${\ displaystyle (p, q) \ în E}$ și pentru fiecare $j\in \{0,1\}$ ${\ displaystyle j \ in \ {0,1 \}}$ ${\ displaystyle j \ in \ {0,1 \}}$ .
Având o funcție arbitrară $f$ ${\ displaystyle f}$ $f$ , este întotdeauna posibil să se determine reparametrizarea sa în formă normală prin intermediul unui algoritm în două faze ( Kolmogorov și Rother , pp. 1274-1279 ):
atâta timp cât există indici $(p,q)\in E$ ${\ displaystyle (p, q) \ în E}$ ${\ displaystyle (p, q) \ în E}$ Și $j\in \{0,1\}$ ${\ displaystyle j \ in \ {0,1 \}}$ ${\ displaystyle j \ in \ {0,1 \}}$ care încalcă a doua condiție a normalității, se fac înlocuiri
$w_{pq}^{0j}$ ${\ displaystyle w_ {pq} ^ {0j}}$ ${\ displaystyle w_ {pq} ^ {0j}}$ cu $w_{pq}^{0j}-a$ ${\ displaystyle w_ {pq} ^ {0j} -a}$ ${\ displaystyle w_ {pq} ^ {0j} -a}$
$w_{pq}^{1j}$ ${\ displaystyle w_ {pq} ^ {1j}}$ ${\ displaystyle w_ {pq} ^ {1j}}$ cu $w_{pq}^{1j}-a$ ${\ displaystyle w_ {pq} ^ {1j} -a}$ ${\ displaystyle w_ {pq} ^ {1j} -a}$
$w_{q}^{j}$ ${\ displaystyle w_ {q} ^ {j}}$ ${\ displaystyle w_ {q} ^ {j}}$ cu $w_{q}^{j}+a$ ${\ displaystyle w_ {q} ^ {j} + a}$ ${\ displaystyle w_ {q} ^ {j} + a}$
unde este $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ ${\ displaystyle a = \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \}}$ ${\ displaystyle a = \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \}}$ ;
pentru fiecare $p=1,\dots ,n$ ${\ displaystyle p = 1, \ dots, n}$ ${\ displaystyle p = 1, \ dots, n}$ , se fac înlocuiri
$w_{0}$ ${\ displaystyle w_ {0}}$ $w_ {0}$ cu $w_{0}+a$ ${\ displaystyle w_ {0} + a}$ ${\ displaystyle w_ {0} + a}$
$w_{p}^{0}$ ${\ displaystyle w_ {p} ^ {0}}$ ${\ displaystyle w_ {p} ^ {0}}$ cu $w_{p}^{0}-a$ ${\ displaystyle w_ {p} ^ {0} -a}$ ${\ displaystyle w_ {p} ^ {0} -a}$
$w_{p}^{1}$ ${\ displaystyle w_ {p} ^ {1}}$ ${\ displaystyle w_ {p} ^ {1}}$ cu $w_{p}^{1}-a$ ${\ displaystyle w_ {p} ^ {1} -a}$ ${\ displaystyle w_ {p} ^ {1} -a}$
unde este $a=\min\{w_{p}^{0},w_{p}^{1}\}$ ${\ displaystyle a = \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \}}$ ${\ displaystyle a = \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \}}$ .

[4] $\min\{w_{p}^{0},w_{p}^{1}\}=0$ ${\ displaystyle \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \} = 0}$ ${\ displaystyle \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \} = 0}$ pentru fiecare $p\in V$ ${\ displaystyle p \ în V}$ ${\ displaystyle p \ în V}$ ;

[5] $\min\{w_{pq}^{0j},w_{pq}^{1j}\}=0$ ${\ displaystyle \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \} = 0}$ ${\ displaystyle \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \} = 0}$ pentru fiecare $(p,q)\in E$ ${\ displaystyle (p, q) \ în E}$ ${\ displaystyle (p, q) \ în E}$ și pentru fiecare $j\in \{0,1\}$ ${\ displaystyle j \ in \ {0,1 \}}$ ${\ displaystyle j \ in \ {0,1 \}}$ .

[6] tâta timp cât există indici $(p,q)\in E$ ${\ displaystyle (p, q) \ în E}$ ${\ displaystyle (p, q) \ în E}$ Și $j\in \{0,1\}$ ${\ displaystyle j \ in \ {0,1 \}}$ ${\ displaystyle j \ in \ {0,1 \}}$ care încalcă a doua condiție a normalității, se fac înlocuiri
$w_{pq}^{0j}$ ${\ displaystyle w_ {pq} ^ {0j}}$ ${\ displaystyle w_ {pq} ^ {0j}}$ cu $w_{pq}^{0j}-a$ ${\ displaystyle w_ {pq} ^ {0j} -a}$ ${\ displaystyle w_ {pq} ^ {0j} -a}$
$w_{pq}^{1j}$ ${\ displaystyle w_ {pq} ^ {1j}}$ ${\ displaystyle w_ {pq} ^ {1j}}$ cu $w_{pq}^{1j}-a$ ${\ displaystyle w_ {pq} ^ {1j} -a}$ ${\ displaystyle w_ {pq} ^ {1j} -a}$
$w_{q}^{j}$ ${\ displaystyle w_ {q} ^ {j}}$ ${\ displaystyle w_ {q} ^ {j}}$ cu $w_{q}^{j}+a$ ${\ displaystyle w_ {q} ^ {j} + a}$ ${\ displaystyle w_ {q} ^ {j} + a}$
unde este $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ ${\ displaystyle a = \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \}}$ ${\ displaystyle a = \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \}}$ ;

[7] $w_{pq}^{0j}$ ${\ displaystyle w_ {pq} ^ {0j}}$ ${\ displaystyle w_ {pq} ^ {0j}}$ cu $w_{pq}^{0j}-a$ ${\ displaystyle w_ {pq} ^ {0j} -a}$ ${\ displaystyle w_ {pq} ^ {0j} -a}$

[8] $w_{pq}^{1j}$ ${\ displaystyle w_ {pq} ^ {1j}}$ ${\ displaystyle w_ {pq} ^ {1j}}$ cu $w_{pq}^{1j}-a$ ${\ displaystyle w_ {pq} ^ {1j} -a}$ ${\ displaystyle w_ {pq} ^ {1j} -a}$

[9] $w_{q}^{j}$ ${\ displaystyle w_ {q} ^ {j}}$ ${\ displaystyle w_ {q} ^ {j}}$ cu $w_{q}^{j}+a$ ${\ displaystyle w_ {q} ^ {j} + a}$ ${\ displaystyle w_ {q} ^ {j} + a}$

[10] tru fiecare $p=1,\dots ,n$ ${\ displaystyle p = 1, \ dots, n}$ ${\ displaystyle p = 1, \ dots, n}$ , se fac înlocuiri
$w_{0}$ ${\ displaystyle w_ {0}}$ $w_ {0}$ cu $w_{0}+a$ ${\ displaystyle w_ {0} + a}$ ${\ displaystyle w_ {0} + a}$
$w_{p}^{0}$ ${\ displaystyle w_ {p} ^ {0}}$ ${\ displaystyle w_ {p} ^ {0}}$ cu $w_{p}^{0}-a$ ${\ displaystyle w_ {p} ^ {0} -a}$ ${\ displaystyle w_ {p} ^ {0} -a}$
$w_{p}^{1}$ ${\ displaystyle w_ {p} ^ {1}}$ ${\ displaystyle w_ {p} ^ {1}}$ cu $w_{p}^{1}-a$ ${\ displaystyle w_ {p} ^ {1} -a}$ ${\ displaystyle w_ {p} ^ {1} -a}$
unde este $a=\min\{w_{p}^{0},w_{p}^{1}\}$ ${\ displaystyle a = \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \}}$ ${\ displaystyle a = \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \}}$ .

[11] $w_{0}$ ${\ displaystyle w_ {0}}$ $w_ {0}$ cu $w_{0}+a$ ${\ displaystyle w_ {0} + a}$ ${\ displaystyle w_ {0} + a}$

[12] $w_{p}^{0}$ ${\ displaystyle w_ {p} ^ {0}}$ ${\ displaystyle w_ {p} ^ {0}}$ cu $w_{p}^{0}-a$ ${\ displaystyle w_ {p} ^ {0} -a}$ ${\ displaystyle w_ {p} ^ {0} -a}$

[13] $w_{p}^{1}$ ${\ displaystyle w_ {p} ^ {1}}$ ${\ displaystyle w_ {p} ^ {1}}$ cu $w_{p}^{1}-a$ ${\ displaystyle w_ {p} ^ {1} -a}$ ${\ displaystyle w_ {p} ^ {1} -a}$

[billionnet-4] Billionnet și Jaumard , pp. 161-163 .

[fix-5] Fix și colab. , pp. 1020-1027 .

[elc-6] Ishikawa , pp. 1362-1369 .

[17] $\min\{w_{p}^{0},w_{p}^{1}\}=0$ ${\ displaystyle \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \} = 0}$ ${\ displaystyle \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \} = 0}$ pentru fiecare $p\in V$ ${\ displaystyle p \ în V}$ ${\ displaystyle p \ în V}$ ;

[18] $\min\{w_{pq}^{0j},w_{pq}^{1j}\}=0$ ${\ displaystyle \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \} = 0}$ ${\ displaystyle \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \} = 0}$ pentru fiecare $(p,q)\in E$ ${\ displaystyle (p, q) \ în E}$ ${\ displaystyle (p, q) \ în E}$ și pentru fiecare $j\in \{0,1\}$ ${\ displaystyle j \ in \ {0,1 \}}$ ${\ displaystyle j \ in \ {0,1 \}}$ .

[19] tâta timp cât există indici $(p,q)\in E$ ${\ displaystyle (p, q) \ în E}$ ${\ displaystyle (p, q) \ în E}$ Și $j\in \{0,1\}$ ${\ displaystyle j \ in \ {0,1 \}}$ ${\ displaystyle j \ in \ {0,1 \}}$ care încalcă a doua condiție a normalității, se fac înlocuiri
$w_{pq}^{0j}$ ${\ displaystyle w_ {pq} ^ {0j}}$ ${\ displaystyle w_ {pq} ^ {0j}}$ cu $w_{pq}^{0j}-a$ ${\ displaystyle w_ {pq} ^ {0j} -a}$ ${\ displaystyle w_ {pq} ^ {0j} -a}$
$w_{pq}^{1j}$ ${\ displaystyle w_ {pq} ^ {1j}}$ ${\ displaystyle w_ {pq} ^ {1j}}$ cu $w_{pq}^{1j}-a$ ${\ displaystyle w_ {pq} ^ {1j} -a}$ ${\ displaystyle w_ {pq} ^ {1j} -a}$
$w_{q}^{j}$ ${\ displaystyle w_ {q} ^ {j}}$ ${\ displaystyle w_ {q} ^ {j}}$ cu $w_{q}^{j}+a$ ${\ displaystyle w_ {q} ^ {j} + a}$ ${\ displaystyle w_ {q} ^ {j} + a}$
unde este $a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}$ ${\ displaystyle a = \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \}}$ ${\ displaystyle a = \ min \ {w_ {pq} ^ {0j}, w_ {pq} ^ {1j} \}}$ ;

[20] $w_{pq}^{0j}$ ${\ displaystyle w_ {pq} ^ {0j}}$ ${\ displaystyle w_ {pq} ^ {0j}}$ cu $w_{pq}^{0j}-a$ ${\ displaystyle w_ {pq} ^ {0j} -a}$ ${\ displaystyle w_ {pq} ^ {0j} -a}$

[21] $w_{pq}^{1j}$ ${\ displaystyle w_ {pq} ^ {1j}}$ ${\ displaystyle w_ {pq} ^ {1j}}$ cu $w_{pq}^{1j}-a$ ${\ displaystyle w_ {pq} ^ {1j} -a}$ ${\ displaystyle w_ {pq} ^ {1j} -a}$

[22] $w_{q}^{j}$ ${\ displaystyle w_ {q} ^ {j}}$ ${\ displaystyle w_ {q} ^ {j}}$ cu $w_{q}^{j}+a$ ${\ displaystyle w_ {q} ^ {j} + a}$ ${\ displaystyle w_ {q} ^ {j} + a}$

[23] tru fiecare $p=1,\dots ,n$ ${\ displaystyle p = 1, \ dots, n}$ ${\ displaystyle p = 1, \ dots, n}$ , se fac înlocuiri
$w_{0}$ ${\ displaystyle w_ {0}}$ $w_ {0}$ cu $w_{0}+a$ ${\ displaystyle w_ {0} + a}$ ${\ displaystyle w_ {0} + a}$
$w_{p}^{0}$ ${\ displaystyle w_ {p} ^ {0}}$ ${\ displaystyle w_ {p} ^ {0}}$ cu $w_{p}^{0}-a$ ${\ displaystyle w_ {p} ^ {0} -a}$ ${\ displaystyle w_ {p} ^ {0} -a}$
$w_{p}^{1}$ ${\ displaystyle w_ {p} ^ {1}}$ ${\ displaystyle w_ {p} ^ {1}}$ cu $w_{p}^{1}-a$ ${\ displaystyle w_ {p} ^ {1} -a}$ ${\ displaystyle w_ {p} ^ {1} -a}$
unde este $a=\min\{w_{p}^{0},w_{p}^{1}\}$ ${\ displaystyle a = \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \}}$ ${\ displaystyle a = \ min \ {w_ {p} ^ {0}, w_ {p} ^ {1} \}}$ .

[24] $w_{0}$ ${\ displaystyle w_ {0}}$ $w_ {0}$ cu $w_{0}+a$ ${\ displaystyle w_ {0} + a}$ ${\ displaystyle w_ {0} + a}$

[25] $w_{p}^{0}$ ${\ displaystyle w_ {p} ^ {0}}$ ${\ displaystyle w_ {p} ^ {0}}$ cu $w_{p}^{0}-a$ ${\ displaystyle w_ {p} ^ {0} -a}$ ${\ displaystyle w_ {p} ^ {0} -a}$

[26] $w_{p}^{1}$ ${\ displaystyle w_ {p} ^ {1}}$ ${\ displaystyle w_ {p} ^ {1}}$ cu $w_{p}^{1}-a$ ${\ displaystyle w_ {p} ^ {1} -a}$ ${\ displaystyle w_ {p} ^ {1} -a}$

[1]

[2]

[3]

[4]

[5]

[6]