Lineær flaskehals tildelingsproblem

I kombinatorisk optimering forstås linear bottleneck assignment problem (LBAP ) som et problem svarende til tildelingsproblemet [1] .

Med enkle ord er opgaven stillet som følger:

Der er et vist antal udøvende kunstnere og et vist antal værker . Enhver udøvende kunstner kan udføre et hvilket som helst arbejde, hvis udførelse kan koste en bestemt pris , som afhænger af udførelsens tildeling. Det er påkrævet at fuldføre alle opgaver, samtidig med at der tildeles præcis én udøver til hvert job på en sådan måde, at den maksimale pris , der opstår under opgaverne, minimeres.

Begrebet " flaskehals " forklares ved den sædvanlige måde, opgaven bruges på, når varigheden af udførerens arbejde tages som prisen. Under disse forhold bliver "maksimumprisen" til "maksimal varighed", som er flaskehalsen i planlægningen af et komplet værk, og denne maksimale varighed bør gøres så lille som muligt.

Det lineære flaskehals-tildelingsproblem blev først introduceret af Fulkerson, Glicksberg og Gross i deres arbejde med at tildele job til maskiner for at minimere gennemløbstiden [2] .

Formel definition

Den formelle definition af flaskehals-tildelingsproblemet er som følger:

Givet to sæt, A og T , sammen med en vægtfunktion C : A × T → R . Find en bijektion f : A → T , således at omkostningsfunktionen er:

\max _{a\in A}C(a,f(a))

minimal.

Normalt er vægtfunktionen givet som en kvadratisk reel matrix C , så omkostningsfunktionen kan skrives som følger:

{\displaystyle \max _{a\in A}C_{a,f(a)))

Problemformulering som et matematisk programmeringsproblem

{\displaystyle \min \,\max _{i,j}c_{i,j}x_{i,j))

under forhold:

\sum _{j=1}^{n}x_{i,j}=1\ (i=1,2,\dots ,n),

\sum _{i=1}^{n}x_{i,j}=1\ (j=1,2,\dots ,n),

x_{i,j}\in \{0,1\}\ (i,j=1,2,\dots ,n)

Løsningsmetoder

Følgende lemma er nyttigt til at løse problemet:

Lemma. [1] Lad os være omkostningsmatrixen for problemet $C=(c_{i,j})$

1. Den optimale værdi af problemet bestemmes af et af elementerne i matricen .

{\displaystyle c_{i,j))

2. Den optimale løsning afhænger kun af den relative rækkefølge af matrixelementerne og ikke af deres numeriske værdier

Eksempel. Lad matrixen

$C={\begin{pmatrix}\pi &{\sqrt {3}}&54392\\0&e^{3}&e^{3}\\{-}2&\sin {(\pi /8)} &4\\\end{pmatrix}}$

Arranger elementerne i matrixen . $-2<0<\sin {(\pi /8)}<{\sqrt {3}}<\pi <4<e^{3}=e^{3}<54392$

Vi erstatter det mindste element −2 med 0, det næste 0 med 1, så erstatter vi med 2, og så videre. Vi får følgende matrix :. ${\displaystyle \sin {(\pi /8)))$ $C'={\begin{pmatrix}4&3&7\\1&6&6\\0&2&5\\\end{pmatrix}}$

Den optimale løsning på problemet vil være permutationen {2, 1, 3} med den maksimale værdi for matricen 5, som svarer til værdien 4 i den oprindelige matrix . $C'$ $C$

Tærskelalgoritme

Ideen om at bruge tærskelmetoden tilhører Garfinkel [3] .

Vi tildeler begyndelsesværdier .

t_{\min }=\min _{i,j}{c_{i,j)),t_{\max }=\max _{i,j}{c_{i,j))

Hvis , så

{\displaystyle t_{\min }=t_{\max ))

optimal værdi = og enhver permutation {1, 2, . . . , n} er optimal.

{\displaystyle t_{\min ))

Ellers, mens de eksisterer , udføres

{\displaystyle c_{i,j}:t_{\min }<c_{i,j}<t_{\max ))

Vi finder medianen , t tal Vi bygger en graf Hvis den indeholder en perfekt match , så accepterer vi

{\displaystyle t_{\min }<c_{i,j}<t_{\max ))

T

T

t_{\min }=t

ellers acceptere

t_{\max }=t

Afslut Hvis slutningen af cyklussen Hvis kontrollen for eksistensen af en perfekt matchning for ikke blev udført, udfører vi den.

{\displaystyle t_{\min ))

Vi bygger en graf for Hvis indeholder en perfekt matchning, vi tager

T

{\displaystyle t_{\min ))

T

{\displaystyle t_{\max }=t_{\min ))

Afslut Hvis Afslut Hvis

Den optimale værdi vil være , og den optimale løsning kan findes ud fra den tilsvarende graf. ${\displaystyle t_{\max ))$

Som du kan se, gennemgår 'tærskelalgoritmen' to trin ved hvert trin i cyklussen. I det første trin vælges en 'tærskelværdi' og en 'tærskelmatrix' , som er defineret som følger: $t$ $T$

T_{i,j}=

1 hvis

c_{ij}>t

0 ellers.

Det andet trin tjekker, om der er en aftale med en pris på nul (for prismatricen ). For at kontrollere dette konstruerer vi en todelt graf G = (U, V; E) med |U| = |V| = n og buer hvis og kun hvis . (Med andre ord skal vi kontrollere, om den todelte graf, der svarer til tærskelmatricen, indeholder en perfekt matchning eller ej). Den mindste tærskelværdi , for hvilken den tilsvarende todelte graf indeholder en perfekt matchning, er den optimale værdi af problemet. Der er flere måder at implementere tærskelalgoritmen på. En mulighed er at bruge binær søgning i det første trin. Dette vil føre til en algoritme, hvor der er tidskompleksitet for at kontrollere eksistensen af en perfekt matchning. Vi kan bruge matrixalgoritmen fra Ybarre og Moran [4] til at finde ud af, om der findes en perfekt matchning. Så kan den optimale løsning findes med bitkompleksitet . Multiplikation af to n × n matricer kræver aritmetiske operationer, og k er et heltal, der opstår fra operationer på lange heltal. Coppersmith og Winograd [5] viste, at matrixmultiplikation kan udføres med . Hvis vi ønsker at få den tilsvarende optimale løsning, kan vi bruge metoden fra Alt, Blum, Mehlhorn og Paul [6] og få den fulde kompleksitet i tilfælde af en tæt matrix. Her betyder tæthed, at antallet af matrixelementer, der ikke er nul , er . $T$ $[i,j]\in E$ $T_{i,j}=0$ $t$ $O(M(n)\log(n))$ $M(n)$ $O(n^{\beta}\log ^{k}n)$ $O(n^{\beta })$ $\beta =2{,}376$ $O\left(n^{2{,}5}\left/{\sqrt {\log(n)))\right.\right)$ ${\displaystyle T_{i,j))$ $O(n^{2})$

Denne metode er teoretisk set den bedst kendte metode til at løse problemet.

Dobbelt algoritme

Nært forbundet med tærskelmetoden er følgende dobbeltalgoritme.

Beregn Lad (tomt sæt).

t=\max _{k=1,2,\dots ,n}(\min _{r=1,2,\dots ,n}c_{r,k},\min _{j=1 ,2,\dots ,n}c_{k,j})

M=\varnothing

Mens |M| < n, udføre Lad os definere en todelt graf G svarende til tærskelværdien t. Find den maksimale match i G. Hvis |M| < n altså Lad og være sæt af hjørner i den minimale dækning af grafen G.

R\subseteq U

J\subseteq V

Lad os sætte

{\displaystyle t=\min _{r\in R,j\in J}c_{r,j))

Afslut Hvis slutningen af cyklussen

Algoritmen bruger nogle oplysninger om tærskelværdien t, nemlig det faktum, at den optimale værdi ikke kan være mindre end den maksimale værdi af minimumselementerne i rækkerne, samt maksimumværdien af minimumselementerne i kolonnerne i matricen C Som den første tærskelværdi kan du således tage $t=\max _{1\leqslant k\leqslant n}(\min _{1\leqslant r\leqslant n}c_{r,k},\min _{1\leqslant j\leqslant n}c_ {k,j})$

Den dobbelte metode starter med denne værdi af t og skaber minimumssæt (indekser) af kolonner og rækker , der dækker alle elementer i matrixen . Dette kan gøres ved at finde det maksimale sæt af buer i grafen G, der definerer matchningen. Her er grafen G en todelt graf med buer (r,j) for hvilke . Hvis matchningen ikke indeholder alle rækker og kolonner, er der matrixelementer, der bestemmer den optimale værdi, og disse elementer er større end t. Som et resultat kan vi tage en ny værdi og bygge en ny graf G. Denne graf indeholder alle kanterne af den forrige graf og mindst én ny kant, så vi kan starte søgningen efter den maksimale matchning fra den, der allerede findes i det forrige trin. Vi fortsætter, indtil vi finder et perfekt match. $J$ $R$ $c_{r,j}\leqslant t$ $c_{r,j}\leqslant t$ ${\displaystyle t=\min _{r\in R,j\in J}c_{r,j))$

Sekventiel stigningsalgoritme

En anden tilgang til at løse problemet kan være brugen af ideerne fra den ungarske metode [7] . I Rusland er denne metode kendt som 'Gross Algorithm'. Vi præsenterer metoden i implementeringen af Derigs og Zimmerman [8] .

Lad os introducere nogle definitioner.

En komplementær matchningssti er en sti, der indeholder de matchende buer, mens en af de to nabobuer nødvendigvis hører til matchningen (dvs. buerne er sammenflettet - en bue fra matchningen efterfølges af en bue, der ikke hører til den, og vice omvendt).

Lad være en komplementær vej til at matche M. $P=([i_{1},j_{1}],[i_{2},j_{1}],[i_{2},j_{2}],\dots ,[i_{k} ,j_{k}])$

Flaskehalsens størrelse er defineret som $\ell (P)$

\ell (P)=\max(c([i_{1},j_{1}]),c([i_{2},j_{2}]),\dots ,c([i_{ k},j_{k}]))

En komplementær sti kaldes en b-korteste sti, hvis størrelsen af flaskehalsen er minimal blandt alle komplementære stier M.

Lad være en todelt graf med buelængder for buer

G=(U,V;E)

{\displaystyle c_{i,j))

[i,j]\in E

Find den nedre grænse t for objektivfunktionen (dvs. )

t=\max {(\max _{u\in U}\min _{v\in V}c_{u,v},\max _{v\in V}\min _{u\in U}c_{u},v)}

Find den maksimale matchende M i en graf G med buer [i, j] if

c_{i,j}\leqslant t

hvis |M| = |U|, så har vi fået en optimal løsning t med et optimalt forhold M, og vi er færdige. Afslut Hvis Lad L være det sæt af elementer i U, som der ikke er nogen overensstemmelse for. indtil L er tomt, udfør Vælg et toppunkt

i\in L

L=L\backslash \{i\}

P = Dijkstra(i) Kommentar: Dijkstra(i)-funktionen returnerer den komplementære sti, der starter ved node i Hvis stien ikke findes, så Lad os sætte Lad os sætte

M=M\ominus P

t=\max(t,\ell (P))

Afslut Hvis ende farvel Kommentar: M er den maksimale matchning med minimumsprisen t.

Den B-korteste komplementære sti findes af Dijkstra()-funktionen.

Under søgningen efter den b-korteste vej mærker vi toppunktet med værdien , hvor er størrelsen på flaskehalsen på den b-korteste vej fra til dette toppunkt, og betyder den umiddelbare forgænger i den b-korteste vej fra til toppunkt . $x\i U$ $({\overline {\alpha }}(x),{\overline {\beta }}(x))$ ${\overline {\alpha }}(x)$ $i_1$ ${\overline {\beta }}(x)$ $i_1$ $x$

På samme måde mærker vi vertexet med værdien , hvor er størrelsen af flaskehalsen på den b-korteste vej fra til dette vertex, og betyder den umiddelbare forgænger i den b-korteste vej fra til toppunktet . $x \i V$ $(\alpha (x),\beta (x))$ $\alpha (x)$ $i_1$ $\beta (x)$ $i_1$ $x$

Dijkstra(i) funktion Kommentar: Ændret Dijkstras algoritme for flaskehals-tildelingsproblemet. Vi mærker alle hjørner ved at indstille .

j\in V

(\alpha (j),\beta (j))=(\infty ,\varnothing )

Lad R = V Kommentar: R indeholder uscannede hjørner V a(i) = t, P = tom For alle naboer til vertex i, udfør

j\in R

Hvis , så

\alpha (j)>\max({\overline {\alpha }}(i),c_{i,j})

Lad os sætte

\alpha (j)=\max({\overline {\alpha }}(i),c_{i,j})

\beta (j)=i

Afslut Hvis slutningen af cyklussen mens R er tom, udfør Lad os finde toppunktet med minimum ;

r\in R

\alpha (r)

Hvis , så

\alpha (r)=\infty

Lad os sætte

R=\varnothing

Ellers hvis r ikke er i matchningen, så Find stien P dannet af sekvensen af toppunkter

(i,\dots ,{\overline {\beta ))(\beta (r)),\beta (r),r)

\ell (P)=\alpha (r)

R=\varnothing

Ellers Lad [s, r] være en kant af matchningen Mark s: Lad For alle naboer til toppunkt s, udfør

({\overline {\alpha }}(s),{\overline {\beta }}(s))=(\alpha (r),r)

R=R\backslash \{r\}

j\in R

Hvis , så

\alpha (j)>\max({\overline {\alpha }}(s),c_{s,j})

Lad os sætte

\alpha (j)=\max({\overline {\alpha }}(s),c_{s,j})

\beta (j)=s

Afslut Hvis slutningen af cyklussen Afslut Hvis Afslut Hvis ende farvel

Asymptotisk adfærd

Lad betegne den optimale værdi af funktionen for n udøvere og n job. Hvis priserne vælges fra en ensartet fordeling på segmentet (0,1), så [9] $c_{n}^{*}$ $c_{ij}$

E[c_{n}^{*}]={\frac {\log n+\log 2+\gamma }{n))+O\left({\frac {(\log n)^{2 }}{n^{7/5}}}}\right)

\mathrm {Var} [c_{n}^{*}]={\frac {\zeta (2)-2(\log 2)^{2}}{n^{2}}}+O \venstre({\frac {(\log n)^{2}}{n^{7/3}}}\højre).

Lineær flaskehals tildelingsproblem

Formel definition

Problemformulering som et matematisk programmeringsproblem

Løsningsmetoder

Tærskelalgoritme

Dobbelt algoritme

Sekventiel stigningsalgoritme

Asymptotisk adfærd

Links