Opdracht probleem - Assignment problem

Het toewijzingsprobleem is een fundamenteel combinatorisch optimalisatieprobleem . In de meest algemene vorm is het probleem als volgt:

De probleeminstantie heeft een aantal agents en een aantal taken . Elke agent kan worden toegewezen om elke taak uit te voeren, wat kosten met zich meebrengt die kunnen variëren afhankelijk van de taaktoewijzing van de agent. Het is nodig om zoveel mogelijk taken uit te voeren door maximaal één agent aan elke taak toe te wijzen en maximaal één taak aan elke agent, zodanig dat de totale kosten van de toewijzing worden geminimaliseerd.

U kunt het probleem ook beschrijven met behulp van de grafentheorie:

Het toewijzingsprobleem bestaat uit het vinden, in een gewogen bipartiete grafiek , een matching van een gegeven grootte, waarbij de som van de gewichten van de randen minimaal is.

Als het aantal agenten en taken gelijk is, wordt het probleem gebalanceerde toewijzing genoemd . Anders wordt dit ongebalanceerde toewijzing genoemd . Als de totale kosten van de toewijzing voor alle taken gelijk zijn aan de som van de kosten voor elke agent (of de som van de kosten voor elke taak, wat in dit geval hetzelfde is), dan wordt het probleem lineaire toewijzing genoemd . Wanneer we spreken over het toewijzingsprobleem zonder enige aanvullende kwalificatie, wordt gewoonlijk het lineair gebalanceerde toewijzingsprobleem bedoeld.

Voorbeelden

Stel dat een taxibedrijf drie taxi's (de agenten) ter beschikking heeft, en drie klanten (de taken) die zo snel mogelijk opgehaald willen worden. Het bedrijf is trots op snelle pick-ups, dus voor elke taxi zijn de "kosten" voor het ophalen van een bepaalde klant afhankelijk van de tijd die de taxi nodig heeft om het ophaalpunt te bereiken. Dit is een evenwichtig toewijzingsprobleem . De oplossing is welke combinatie van taxi's en klanten de laagste totale kosten oplevert.

Stel nu dat er vier taxi's beschikbaar zijn, maar nog steeds slechts drie klanten. Dit is een onevenwichtig toewijzingsprobleem . Een manier om dit op te lossen is door een vierde dummy-taak uit te vinden, misschien "stilzitten en niets doen" genoemd, met een prijs van 0 voor de taxi die eraan is toegewezen. Dit reduceert het probleem tot een evenwichtig toewijzingsprobleem, dat dan op de gebruikelijke manier kan worden opgelost en toch de beste oplossing voor het probleem geeft.

Soortgelijke aanpassingen kunnen worden gedaan om meer taken dan agenten toe te staan, taken waaraan meerdere agenten moeten worden toegewezen (bijvoorbeeld een groep van meer klanten dan in één taxi passen), of om de winst te maximaliseren in plaats van de kosten te minimaliseren.

Formele definitie

De formele definitie van het toewijzingsprobleem (of lineair toewijzingsprobleem ) is

Gegeven twee sets, A en T , van gelijke grootte, samen met een gewichtsfunctie C : A × T → R . Zoek een bijectie f : A → T zodat de kostenfunctie :

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

wordt geminimaliseerd.

Gewoonlijk wordt de gewichtsfunctie gezien als een vierkante reële waarde matrix C , zodat de kostenfunctie wordt opgeschreven als:

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

Het probleem is "lineair", omdat de te optimaliseren kostenfunctie en alle beperkingen alleen lineaire termen bevatten.

Algoritmen

Een naïeve oplossing voor het opdrachtprobleem is om alle opdrachten te controleren en de kosten van elke opdracht te berekenen. Dit kan erg inefficiënt zijn, aangezien er met n agenten en n taken n ! ( faculteit van n ) verschillende opdrachten. Gelukkig zijn er veel algoritmen om het probleem in tijdpolynoom in n op te lossen .

Het toewijzingsprobleem is een speciaal geval van het transportprobleem , wat een speciaal geval is van het minimumkostenstroomprobleem , dat op zijn beurt een speciaal geval is van een lineair programma . Hoewel het mogelijk is om elk van deze problemen op te lossen met behulp van het simplex-algoritme , heeft elke specialisatie een kleine oplossingsruimte en dus efficiëntere algoritmen die zijn ontworpen om te profiteren van de speciale structuur.

Evenwichtige opdracht

In het gebalanceerde toewijzingsprobleem hebben beide delen van de bipartiete graaf hetzelfde aantal hoekpunten, aangeduid met n .

Een van de eerste polynomiale tijdalgoritmen voor gebalanceerde toewijzing was het Hongaarse algoritme . Het is een globaal algoritme - het is gebaseerd op het verbeteren van een matching langs augmenterende paden (alternerende paden tussen niet-overeenkomende hoekpunten). De runtime-complexiteit ervan, bij gebruik van Fibonacci-heaps , is , waarbij m een aantal randen is. Dit is momenteel de snelste runtime van een sterk polynoom algoritme voor dit probleem. Als alle gewichten gehele getallen zijn, kan de runtime worden verbeterd tot , maar het resulterende algoritme is slechts zwak polynoom. Als de gewichten gehele getallen zijn en alle gewichten maximaal C zijn (waarbij C >1 een geheel getal is), dan kan het probleem worden opgelost in zwak-polynomiale tijd in een methode die weight scaling wordt genoemd . $O(mn+n^{2}\log n)$ $O(mn+n^{2}\log \log n)$ ${\ Displaystyle O (m {\ sqrt {n}} \ log (n \ cdot C))}$

Naast de globale methoden zijn er lokale methoden die gebaseerd zijn op het vinden van lokale updates (in plaats van volledige augmenterende paden). Deze methoden hebben slechtere asymptotische runtime-garanties, maar in de praktijk werken ze vaak beter. Deze algoritmen worden veilingalgoritmen , push-relabel-algoritmen of preflow-push-algoritmen genoemd. Sommige van deze algoritmen bleken equivalent te zijn.

Sommige lokale methoden gaan ervan uit dat de grafiek een perfecte overeenkomst toelaat ; als dit niet het geval is, kunnen sommige van deze methoden voor altijd worden uitgevoerd. Een eenvoudige technische manier om dit probleem op te lossen is om de invoergrafiek uit te breiden tot een volledige bipartiete grafiek, door kunstmatige randen met zeer grote gewichten toe te voegen. Deze gewichten moeten de gewichten van alle bestaande koppelingen overschrijden, om te voorkomen dat er kunstmatige randen in de mogelijke oplossing verschijnen.

Zoals Mulmuley, Vazirani en Vazirani laten zien, wordt het probleem van een perfecte afstemming van het minimumgewicht omgezet in het vinden van minderjarigen in de aangrenzende matrix van een grafiek. Met behulp van het isolatielemma kan in een graaf een perfect passend minimumgewicht worden gevonden met een waarschijnlijkheid van ten minste ½. Voor een graaf met n hoekpunten is tijd nodig. $O(\log ^{2}(n))$

Onevenwichtige toewijzing

In het ongebalanceerde toewijzingsprobleem heeft het grootste deel van de bipartiete grafiek n hoekpunten en het kleinere deel heeft r < n hoekpunten. Er is ook een constante s die hoogstens de kardinaliteit is van een maximale matching in de grafiek. Het doel is om een minimale kostenovereenkomst te vinden met de maat s . Het meest voorkomende geval is het geval waarin de grafiek een eenzijdige perfecte matching toelaat (dwz een matching van grootte r ), en s = r .

Onevenwichtige toewijzing kan worden teruggebracht tot een gebalanceerde toewijzing. De naïeve reductie is om nieuwe hoekpunten aan het kleinere deel toe te voegen en ze te verbinden met het grotere deel met behulp van randen van kosten 0. Dit vereist echter nieuwe randen. Een efficiëntere reductie wordt de verdubbelingstechniek genoemd . Hier wordt een nieuwe graaf G' opgebouwd uit twee kopieën van de originele graaf G : een voorwaartse kopie Gf en een achterwaartse kopie Gb. De achterwaartse kopie wordt "omgedraaid", zodat er aan elke kant van G' nu n + r hoekpunten zijn. Tussen de kopieën moeten we twee soorten koppelranden toevoegen: $nr$ $n(nr)$

Groot-naar-groot: voeg vanaf elk hoekpunt in het grootste deel van Gf een kostenvrije rand toe aan het corresponderende hoekpunt in Gb .
Klein-naar-klein: als de originele grafiek geen eenzijdige perfecte overeenkomst heeft , voeg dan van elk hoekpunt in het kleinere deel van Gf een zeer dure rand toe aan het corresponderende hoekpunt in Gb .

Al met al zijn hooguit nieuwe randen nodig. De resulterende grafiek heeft altijd een perfecte match van grootte . Een minimale kosten perfecte matching in deze grafiek moet bestaan uit minimale kosten maximale kardinaliteit matchings in Gf en Gb. Het grootste probleem met deze verdubbelingstechniek is dat er geen snelheidswinst is wanneer . $n+r$ $n+r$ $r\ll n$

In plaats van reductie te gebruiken, kan het ongebalanceerde toewijzingsprobleem worden opgelost door bestaande algoritmen voor gebalanceerde toewijzing direct te generaliseren. Het Hongaarse algoritme kan worden gegeneraliseerd om het probleem in sterk polynomiale tijd op te lossen . In het bijzonder, als s = r dan is de runtime . Als de gewichten gehele getallen zijn, kan de methode van Thorup worden gebruikt om een runtime van te krijgen . $O(ms+s^{2}\log r)$ $O(mr+r^{2}\log r)$ $O(ms+s^{2}\log \log r)$

Oplossing door lineair programmeren

Het toewijzingsprobleem kan worden opgelost door het te presenteren als een lineair programma . Voor het gemak zullen we het maximalisatieprobleem presenteren. Elke rand $(i, j)$ , waarbij i in A is en j in T , heeft een gewicht . Voor elke rand hebben we een variabele _.De variabele is 1 als de rand in de overeenkomst zit en 0 anders, dus stellen we de domeinbeperkingen in: ${\textstyle w_{ij}}$ $(i,j)$ ${\textstyle x_{ij}}$

0\leq x_{ij}\leq 1{\text{ for }}i,j\in A,T,\,

x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T.

Het totale gewicht van de matching is: . Het doel is om een perfecte match met het maximale gewicht te vinden. $\sum _{(i,j)\in A\times T}w_{ij}x_{ij}$

Om te garanderen dat de variabelen inderdaad een perfecte overeenkomst vertegenwoordigen, voegen we beperkingen toe die zeggen dat elk hoekpunt grenst aan precies één rand in de overeenkomst, dat wil zeggen,

\sum _{j\in T}x_{ij}=1{\text{ for }}i\in A,\,~~~\sum _{i\in A}x_{ij}=1 {\text{ voor }}j\in T,\,

.

Al met al hebben we de volgende LP:

{\text{maximaliseren}}~~\sum _{(i,j)\in A\times T}w_{ij}x_{ij}

{\text{behoudens}}~~\sum _{j\in T}x_{ij}=1{\text{ for }}i\in A,\,~~~\sum _{i \in A}x_{ij}=1{\text{ voor }}j\in T

0\leq x_{ij}\leq 1{\text{ for }}i,j\in A,T,\,

x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T.

Dit is een integer lineair programma. We kunnen het echter oplossen zonder de integraliteitsbeperkingen (dwz de laatste beperking laten vallen), met behulp van standaardmethoden voor het oplossen van continue lineaire programma's. Hoewel deze formulering ook fractionele variabele waarden toelaat, heeft de LP in dit speciale geval altijd een optimale oplossing waarbij de variabelen gehele waarden aannemen. Dit komt omdat de beperkingsmatrix van de fractionele LP volledig unimodulair is - het voldoet aan de vier voorwaarden van Hoffman en Gale.

Dit kan ook direct worden aangetoond. Laat x een optimale oplossing zijn van de fractionele LP, het totale gewicht en het aantal niet-integrale variabelen. Als we klaar zijn. Anders is er een fractionele variabele, laten we zeggen . Omdat de som van variabelen aangrenzend aan 1 is, wat in een geheel getal is, moet er een andere variabele zijn naast j ₂ met een fractionele waarde, laten we zeggen . Door soortgelijke overwegingen op i ₃ , moet er een andere variabele naast i _{3 zijn} met een fractionele waarde, laten we zeggen . Door soortgelijke overwegingen gaan we van het ene hoekpunt naar het andere, waarbij we randen met fractionele waarden verzamelen. Omdat de grafiek eindig is, moeten we op een gegeven moment een cyclus hebben. Zonder verlies van algemeenheid kunnen we aannemen dat de cyclus eindigt op hoekpunt i ₁ , dus de laatste fractionele variabele in de cyclus is . Het aantal randen in de cyclus is dus 2 m – het moet even zijn aangezien de graaf bipartiet is. $w(x)$ $k(x)$ $k(x)=0$ ${\textstyle x_{i_{1},j_{2}}}$ $j_{2}$ ${\textstyle x_{i_{3},j_{2}}}$ ${\textstyle x_{i_{3},j_{4}}}$ ${\textstyle x_{i_{1},j_{2m}}}$

Stel dat we een bepaalde constante e toevoegen aan alle even variabelen in de cyclus, en dezelfde constante e verwijderen van alle oneven variabelen in de cyclus. Voor zo'n e blijft de som van variabelen nabij elk hoekpunt hetzelfde (1), dus aan de hoekpuntbeperkingen wordt nog steeds voldaan. Bovendien, als e klein genoeg is, blijven alle variabelen tussen 0 en 1, zodat ook aan de domeinbeperkingen wordt voldaan. Het is gemakkelijk om een grootste e te vinden die de domeinbeperkingen handhaaft: het is ofwel het kleinste verschil tussen een oneven variabele en 0, of het kleinste verschil tussen een even variabele en 1. Nu hebben we één fractionele variabele minder, dus k ( x ) neemt af met 1. De objectieve waarde blijft hetzelfde, omdat we deze anders zouden kunnen verhogen door e als positief of negatief te selecteren, in tegenstelling tot de aanname dat deze maximaal is.

Door het cyclusverwijderingsproces te herhalen komen we, na hoogstens n stappen, tot een oplossing waarin alle variabelen integraal zijn.

Andere methoden en benaderingsalgoritmen

Er bestaan andere benaderingen voor het toewijzingsprobleem en deze worden beoordeeld door Duan en Pettie (zie tabel II). Hun werk stelt een benaderingsalgoritme voor voor het toewijzingsprobleem (en het meer algemene maximale gewichtsafstemmingsprobleem ), dat in lineaire tijd loopt voor elke vaste foutgrens.

Generalisatie

Wanneer geformuleerd als een grafentheorieprobleem, kan het toewijzingsprobleem worden uitgebreid van bipartiete grafieken naar willekeurige grafieken. Het overeenkomstige probleem, van het vinden van een matching in een gewogen grafiek waarbij de som van de gewichten is gemaximaliseerd, wordt het maximale gewichtsafstemmingsprobleem genoemd .

Zie ook

Referenties en verder lezen

Brualdi, Richard A. (2006). Combinatorische matrixklassen . Encyclopedia of Mathematics en haar toepassingen. 108 . Cambridge: Cambridge University Press . ISBN 978-0-521-86565-4. Zbl 1.106,05001 .
Burkard, Rainer ; M. Dell'Amico; S. Martello (2012). Opdrachtproblemen (herziene herdruk) . SIAM. ISBN 978-1-61197-222-1.
Bertsekas, Dimitri (1998). Netwerkoptimalisatie: continue en discrete modellen . Athene Wetenschappelijk. ISBN 978-1-886529-02-1.

Languages

In other projects