Ramură și legătură

Branch and bound este o tehnică generală pentru rezolvarea problemelor de optimizare combinatorie (adică probleme cu spațiul de soluție finită) și se bazează pe descompunerea problemei inițiale în subprobleme mai simple de rezolvat.

Această metodă a fost propusă pentru prima dată de AH Land și AG Doig în 1960 pentru a rezolva probleme de programare liniară întregi.

Algoritmii ramificați și legați sunt numiți algoritmi de enumerare implicită deoarece se comportă exact ca un algoritm de enumerare - adică „încearcă” toate soluțiile posibile până când găsesc cea optimă (sau corectă) - dar aruncă unele dintre ele, demonstrând a priori -optimitate.

Descriere ^[1]

Să presupunem că avem o problemă $P^{0}=(z,F(P^{0}))$ ${\ displaystyle P ^ {0} = (z, F (P ^ {0}))}$ $P ^ 0 = (z, F (P ^ 0))$ unde z este funcția obiectivă a problemei, în timp ce $F(P^{0})$ ${\ displaystyle F (P ^ {0})}$ $F (P ^ 0)$ este regiunea eligibilă. Cea mai bună soluție optimă va fi $z^{*}=z(P^{0})=\left\{z(x):x\in F(P^{0})\right\}$ ${\ displaystyle z ^ {*} = z (P ^ {0}) = \ left \ {z (x): x \ în F (P ^ {0}) \ right \}}$ $z ^ * = z (P ^ 0) = \ left \ {z (x): x \ in F (P ^ 0) \ right \}$ in timp ce $z^{best}$ ${\ displaystyle z ^ {best}}$ $z ^ {cel mai bun}$ reprezintă cea mai cunoscută soluție fezabilă. Să descompunem problema $P^{0}$ ${\ displaystyle P ^ {0}}$ $P ^ 0$ în subprobleme K: $P^{1},P^{2},...,P^{K}$ ${\ displaystyle P ^ {1}, P ^ {2}, ..., P ^ {K}}$ $P ^ 1, P ^ 2, ..., P ^ K$ totalitatea pe care o reprezentați $P^{0}$ ${\ displaystyle P ^ {0}}$ $P ^ 0$ , de exemplu, poate fi subdivizat $F(P^{0})$ ${\ displaystyle F (P ^ {0})}$ $F (P ^ 0)$ în subseturi K $F(P^{1}),F(P^{2}),...,F(P^{K})$ ${\ displaystyle F (P ^ {1}), F (P ^ {2}), ..., F (P ^ {K})}$ $F (P ^ 1), F (P ^ 2), ..., F (P ^ K)$ astfel încât:

$\bigcup _{i=1}^{K}F(P^{i})=F(P^{0})$ ${\ displaystyle \ bigcup _ {i = 1} ^ {K} F (P ^ {i}) = F (P ^ {0})}$ $\ bigcup_ {i = 1} ^ K F (P ^ i) = F (P ^ 0)$

De preferință, subregiunile ar trebui să fie partiționate astfel încât:

$F(P^{i})\cap F(P^{j})=\varnothing \qquad \forall P^{i},P^{j}:i\neq j$ ${\ displaystyle F (P ^ {i}) \ cap F (P ^ {j}) = \ varnothing \ qquad \ forall P ^ {i}, P ^ {j}: i \ neq j}$ $F (P ^ i) \ cap F (P ^ j) = \ varnothing \ qquad \ forall P ^ i, P ^ j: i \ n și j$

Acest proces de ramificare (ramificare) poate fi reprezentat de un arbore de decizie ( arbore de decizie a ramurilor), în care fiecare nod reprezintă subproblema în timp ce fiecare arc al relației descendente.

Rezolva problema $P^{0}$ ${\ displaystyle P ^ {0}}$ $P ^ 0$ este deci echivalent cu rezolvarea totalității propriei sale $P^{K}$ ${\ displaystyle P ^ {K}}$ $P ^ K$ subprobleme generate:

$z^{*}=z(P^{0})=\min \left\{z(P^{1}),z(P^{2}),...,z(P^{K})\right\}$ ${\ displaystyle z ^ {*} = z (P ^ {0}) = \ min \ left \ {z (P ^ {1}), z (P ^ {2}), ..., z (P ^ {K}) \ right \}}$ $z ^ * = z (P ^ 0) = \ min \ left \ {z (P ^ 1), z (P ^ 2), ..., z (P ^ K) \ right \}$

O subproblemă $P^{i}$ ${\ displaystyle P ^ {i}}$ $P ^ i$ poate fi considerat rezolvat dacă apare cel puțin unul dintre următoarele cazuri:

Soluția optimă de $P^{i}$ ${\ displaystyle P ^ {i}}$ $P ^ i$ ;
Dovedește că $F(P^{i})$ ${\ displaystyle F (P ^ {i})}$ $F (P ^ i)$ este gol (adică $P^{i}$ ${\ displaystyle P ^ {i}}$ $P ^ i$ este inadmisibil);
Dovedește că $z(P^{i})\geq z^{best}$ ${\ displaystyle z (P ^ {i}) \ geq z ^ {best}}$ $z (P ^ i) \ ge z ^ {cel mai bun}$ (soluția la subproblemă este mai proastă decât cea mai cunoscută).

Dacă nu pot rezolva un nod, trebuie să îl descompun în alte subprobleme. De asemenea, pentru fiecare subproblemă $P^{i}$ ${\ displaystyle P ^ {i}}$ $P ^ i$ , este posibil să se determine o limită inferioară a soluției pentru a urma o strategie de navigare în arbore mai eficientă.

$L(P^{i})\leq (P^{i})$ ${\ displaystyle L (P ^ {i}) \ leq (P ^ {i})}$ $L (P ^ i) \ le (P ^ i)$

Dacă verific asta $L(P^{i})\geq z^{best}$ ${\ displaystyle L (P ^ {i}) \ geq z ^ {best}}$ $L (P ^ i) \ ge z ^ {cel mai bun}$ Pot exclude acel nod, deoarece cea mai bună soluție pe care sper să o obțin este mai proastă decât soluția fezabilă a problemei inițiale. Pentru a obține o limită inferioară a $P^{i}=(z,F(P^{0}))$ ${\ displaystyle P ^ {i} = (z, F (P ^ {0}))}$ $P ^ i = (z, F (P ^ 0))$ Trebuie să găsesc o relaxare a problemei $R(P^{i})=(z_{r},F_{r}(P^{i}))$ ${\ displaystyle R (P ^ {i}) = (z_ {r}, F_ {r} (P ^ {i}))}$ $R (P ^ i) = (z_r, F_r (P ^ i))$ astfel încât:

$F_{r}(P^{i})\supseteq F(P^{i})$ ${\ displaystyle F_ {r} (P ^ {i}) \ supseteq F (P ^ {i})}$ $F_r (P ^ i) \ supseteq F (P ^ i)$ ;
$z_{r}(y)\leq z(y)\qquad \forall y\in F(P^{i})$ ${\ displaystyle z_ {r} (y) \ leq z (y) \ qquad \ forall y \ în F (P ^ {i})}$ $z_r (y) \ le z (y) \ qquad \ forall y \ în F (P ^ i)$ ;

Problema relaxată poate fi rezolvată într-un mod mai simplu decât problema inițială, așa că pot găsi soluția optimă care reprezintă limita inferioară a problemei inițiale. Relaxarea trebuie, de asemenea, aleasă astfel încât să fie cât mai aproape posibil ( strânsă ) de problema inițială, în unele cazuri este suficientă o relaxare continuă (ușor de rezolvat prin algoritmul simplex ), în alte cazuri poate fi convenabil să folosiți alte relaxări, cum ar fi ca surogat de relaxare sau relaxare lagrangiană .

Exemplu

Scopul este de a găsi întreaga soluție optimă pentru problema rucsacului atribuit:

{\begin{cases}\max \ 6x_{1}+3x_{2}+4x_{3}+2x_{4}+x_{5}\\2x_{1}+x_{2}+2x_{3}+x_{4}+x_{5}\leq 4\\x\in \left\{0,1\right\}\\\end{cases}}

{\ displaystyle {\ begin {cases} \ max \ 6x_ {1} + 3x_ {2} + 4x_ {3} + 2x_ {4} + x_ {5} \\ 2x_ {1} + x_ {2} + 2x_ { 3} + x_ {4} + x_ {5} \ leq 4 \\ x \ in \ left \ {0,1 \ right \} \\\ end {cases}}}

{\ displaystyle {\ begin {cases} \ max \ 6x_ {1} + 3x_ {2} + 4x_ {3} + 2x_ {4} + x_ {5} \\ 2x_ {1} + x_ {2} + 2x_ { 3} + x_ {4} + x_ {5} \ leq 4 \\ x \ in \ left \ {0,1 \ right \} \\\ end {cases}}}

Deoarece fiecare variabilă are un cost $c_{i}$ ${\ displaystyle c_ {i}}$ $Acolo}$ și o greutate $a_{i}$ ${\ displaystyle a_ {i}}$ $la}$ , primul pas este să ordonați variabilele în funcție de criteriul: ${\frac {c_{1}}{a_{1}}}\geq {\frac {c_{2}}{a_{2}}}\geq ...\geq {\frac {c_{n}}{a_{n}}}$ ${\ displaystyle {\ frac {c_ {1}} {a_ {1}}} \ geq {\ frac {c_ {2}} {a_ {2}}} \ geq ... \ geq {\ frac {c_ { n}} {a_ {n}}}}$ ${\ displaystyle {\ frac {c_ {1}} {a_ {1}}} \ geq {\ frac {c_ {2}} {a_ {2}}} \ geq ... \ geq {\ frac {c_ { n}} {a_ {n}}}}$ .

În acest caz, variabilele sunt deja sortate din ${\frac {6}{2}}\geq {\frac {3}{1}}\geq {\frac {4}{2}}\geq {\frac {2}{1}}\geq {\frac {1}{1}}$ ${\ displaystyle {\ frac {6} {2}} \ geq {\ frac {3} {1}} \ geq {\ frac {4} {2}} \ geq {\ frac {2} {1}} \ geq {\ frac {1} {1}}}$ ${\ displaystyle {\ frac {6} {2}} \ geq {\ frac {3} {1}} \ geq {\ frac {4} {2}} \ geq {\ frac {2} {1}} \ geq {\ frac {1} {1}}}$ , apoi pot trece la determinarea unei soluții întregi optime curente la care corespunde o valoare optimă a funcției obiective.

O posibilă soluție $x^{*}$ ${\ displaystyle x ^ {*}}$ $x ^ {*}$ excelent întreg este $x^{*}={\begin{bmatrix}1\\0\\0\\0\\0\end{bmatrix}}$ ${\ displaystyle x ^ {*} = {\ begin {bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \ end {bmatrix}}}$ ${\ displaystyle x ^ {*} = {\ begin {bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \ end {bmatrix}}}$ care corespunde unei valori optime a funcției obiective $z^{*}=6$ ${\ displaystyle z ^ {*} = 6}$ ${\ displaystyle z ^ {*} = 6}$ .

Conform acestor ipoteze, constrângerea este respectată, dar nu este pe deplin optimizată, de fapt obțin inegalitatea $2x_{1}+x_{2}+2x_{3}+x_{4}+x_{5}\leq 4\longrightarrow 2\leq 4$ ${\ displaystyle 2x_ {1} + x_ {2} + 2x_ {3} + x_ {4} + x_ {5} \ leq 4 \ longrightarrow 2 \ leq 4}$ ${\ displaystyle 2x_ {1} + x_ {2} + 2x_ {3} + x_ {4} + x_ {5} \ leq 4 \ longrightarrow 2 \ leq 4}$ . Prin urmare, trebuie căutate soluții astfel încât constrângerea capacității să poată fi saturată.

Apoi este plasat $x_{1}=1,\;x_{2}=1,\;x_{3}={\frac {1}{2}},\;x_{4}=0,\;x_{5}=0$ ${\ displaystyle x_ {1} = 1, \; x_ {2} = 1, \; x_ {3} = {\ frac {1} {2}}, \; x_ {4} = 0, \; x_ { 5} = 0}$ ${\ displaystyle x_ {1} = 1, \; x_ {2} = 1, \; x_ {3} = {\ frac {1} {2}}, \; x_ {4} = 0, \; x_ { 5} = 0}$ , adică $x^{*}={\begin{bmatrix}1\\1\\{\frac {1}{2}}\\0\\0\end{bmatrix}}$ ${\ displaystyle x ^ {*} = {\ begin {bmatrix} 1 \\ 1 \\ {\ frac {1} {2}} \\ 0 \\ 0 \ end {bmatrix}}}$ ${\ displaystyle x ^ {*} = {\ begin {bmatrix} 1 \\ 1 \\ {\ frac {1} {2}} \\ 0 \\ 0 \ end {bmatrix}}}$ care corespunde valorii optime $z^{*}=11$ ${\ displaystyle z ^ {*} = 11}$ ${\ displaystyle z ^ {*} = 11}$ . Soluția $x^{*}$ ${\ displaystyle x ^ {*}}$ $x ^ {*}$ totuși nu este întreg, așa că generez două subprobleme corespunzătoare componentei non-întregi, adică $x_{3}$ ${\ displaystyle x_ {3}}$ $x_3$ :

$P_{1})\;{\bar {x}}_{3}=\lfloor x_{3}\rfloor =\lfloor {\frac {1}{2}}\rfloor \longrightarrow {\bar {x}}_{3}=0$ ${\ displaystyle P_ {1}) \; {\ bar {x}} _ {3} = \ lfloor x_ {3} \ rfloor = \ lfloor {\ frac {1} {2}} \ rfloor \ longrightarrow {\ bar {x}} _ {3} = 0}$ ${\ displaystyle P_ {1}) \; {\ bar {x}} _ {3} = \ lfloor x_ {3} \ rfloor = \ lfloor {\ frac {1} {2}} \ rfloor \ longrightarrow {\ bar {x}} _ {3} = 0}$

${\bar {x}}_{3}=0\longrightarrow x^{(1)}={\begin{bmatrix}1\\1\\0\\1\\0\end{bmatrix}}$ ${\ displaystyle {\ bar {x}} _ {3} = 0 \ longrightarrow x ^ {(1)} = {\ begin {bmatrix} 1 \\ 1 \\ 0 \\ 1 \\ 0 \ end {bmatrix} }}$ ${\ displaystyle {\ bar {x}} _ {3} = 0 \ longrightarrow x ^ {(1)} = {\ begin {bmatrix} 1 \\ 1 \\ 0 \\ 1 \\ 0 \ end {bmatrix} }}$ care corespunde excelentului $z^{(1)}=11$ ${\ displaystyle z ^ {(1)} = 11}$ ${\ displaystyle z ^ {(1)} = 11}$ (mai bun decât excelentul anterior). În acest caz, întrucât valoarea optimă este mai bună și soluția este întreagă, mă pot închide $P_{1}$ ${\ displaystyle P_ {1}}$ $P_1$ și actualizați soluția $x^{*}$ ${\ displaystyle x ^ {*}}$ $x ^ {*}$ și curentul excelent $z^{*}$ ${\ displaystyle z ^ {*}}$ $z ^ {*}$ respectiv cu valorile de $x^{(1)}$ ${\ displaystyle x ^ {(1)}}$ ${\ displaystyle x ^ {(1)}}$ Și $z^{(1)}$ ${\ displaystyle z ^ {(1)}}$ ${\ displaystyle z ^ {(1)}}$ tocmai găsit.

$P_{2})\;{\bar {x}}_{3}=\lceil x_{3}\rceil =\lceil {\frac {1}{2}}\rceil \longrightarrow {\bar {x}}_{3}=1$ ${\ displaystyle P_ {2}) \; {\ bar {x}} _ {3} = \ lceil x_ {3} \ rceil = \ lceil {\ frac {1} {2}} \ rceil \ longrightarrow {\ bar {x}} _ {3} = 1}$ ${\ displaystyle P_ {2}) \; {\ bar {x}} _ {3} = \ lceil x_ {3} \ rceil = \ lceil {\ frac {1} {2}} \ rceil \ longrightarrow {\ bar {x}} _ {3} = 1}$

${\bar {x}}_{3}=1\longrightarrow x^{(2)}={\begin{bmatrix}1\\0\\1\\0\\0\end{bmatrix}}$ ${\ displaystyle {\ bar {x}} _ {3} = 1 \ longrightarrow x ^ {(2)} = {\ begin {bmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 0 \ end {bmatrix} }}$ ${\ displaystyle {\ bar {x}} _ {3} = 1 \ longrightarrow x ^ {(2)} = {\ begin {bmatrix} 1 \\ 0 \\ 1 \\ 0 \\ 0 \ end {bmatrix} }}$ care corespunde excelentului $z^{(2)}=10$ ${\ displaystyle z ^ {(2)} = 10}$ ${\ displaystyle z ^ {(2)} = 10}$ (mai rău decât excelentul anterior). De vreme ce soluția $x^{(2)}$ ${\ displaystyle x ^ {(2)}}$ ${\ displaystyle x ^ {(2)}}$ este întreg dar $z^{(2)}<z^{*}$ ${\ displaystyle z ^ {(2)} <z ^ {*}}$ ${\ displaystyle z ^ {(2)} <z ^ {*}}$ , Pot închide $P_{2}$ ${\ displaystyle P_ {2}}$ $P_ {2}$ fără a actualiza niciun parametru.

Neavând alte subprobleme deschise, rezultă soluția optimă întreagă și valoarea optimă a funcției obiective $x^{*}={\begin{bmatrix}1\\1\\0\\1\\0\end{bmatrix}}$ ${\ displaystyle x ^ {*} = {\ begin {bmatrix} 1 \\ 1 \\ 0 \\ 1 \\ 0 \ end {bmatrix}}}$ ${\ displaystyle x ^ {*} = {\ begin {bmatrix} 1 \\ 1 \\ 0 \\ 1 \\ 0 \ end {bmatrix}}}$ Și $z^{*}=11$ ${\ displaystyle z ^ {*} = 11}$ ${\ displaystyle z ^ {*} = 11}$ .

Aplicații

Această abordare a fost utilizată pentru unele probleme NP-hard , de exemplu

Poate fi folosit și ca bază pentru diferiți algoritmi euristici . De exemplu, este posibil să opriți ramificarea atunci când diferența dintre soluția găsită și limita inferioară devine mai mică decât un anumit prag. Acest lucru este util atunci când soluția găsită este „suficient de bună” pentru scopurile noastre, cu avantajul de a reduce semnificativ timpul de calcul.

Notă

^ S. Martello, "Algoritmi ramificați și legați: strategii de explorare și relaxare", în Metode de optimizare a deciziilor (editat de G. Di Pillo) , Milano, Masson, 1994.

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

[1] S. Martello, "Algoritmi ramificați și legați: strategii de explorare și relaxare", în Metode de optimizare a deciziilor (editat de G. Di Pillo) , Milano, Masson, 1994.

[1]

Ramură și legătură

Descriere [1]

Exemplu

Aplicații

Notă

Descriere ^[1]