[Alg] Assignment probleem met categorieen

[Zoijar]

Ik wil het volgende oplossen, maar ik weet niet zo goed welk algoritme ik daarvoor moet gebruiken, of hoe ik een bestaand algoritme aan moet passen. Ik weet ook niet zo goed in welke klasse dit probleem valt, aangezien kleine aanpassingen kunnen iets soms ineens NPC maken...

Anyway, dit wil ik doen. Een vorm van het assignment probleem, waar een N aantal Agents gekoppeld moeten worden aan een M aantal Tasks, zodat er een 1-op-1 relatie tussen Agents en Tasks ontstaat. Elke koppeling heeft een bepaalde cost. Dit standaard probleem kan je beschrijven met een (2D) Cost matrix, en vervolgens oplossen in polynomiale tijd met het munkres of hongaarse algoritme. Dat heb ik gedaan, dat werkt.

Het uitgebreide probleem is nu dat ik categorieen in zowel Tasks als Agents heb. De extra constraint is nu dat elke Task categorie slecht 1 agent uit dezelfde Agent categorie toegewezen kan krijgen. Dus stel dat je Rode en Blauwe agents hebt, en je hebt Lange en Korte tasks, dan mogen twee tasks uit de Lange categorie niet twee rode of blauwe agents gekoppeld krijgen, maar alleen een rode en een blauwe. Wat wel mag is dat er in de Korte task categorie een rode voorkomt zowel als in de Lange categorie.

Iemand een idee? Ik vind een (goed) benaderend algoritme ook best als optimaal lastig is. Verder heb ik het idee dat dit te formuleren is als een flow algoritme, maar ik heb geen idee hoe.

Uitgebreider voorbeeld:

Je hebt letter-cijfer combinaties: A1, A2, A3, ... A9, B1, B2, B3, ..., B9, ... Z1, Z2, Z3, ..., Z9
En je hebt 5 slots: met 3 vrij posities: 1{. . .}, 2{. . .}, ..., 5{. . .}

Verder is er een cost voor elke cijfer slot combinatie: C(i,j) = n_ij. Dus een A1 in slot 1 heeft dezelfde cost als een B1 of C1 in slot 1, maar een andere cost dan een A2 in slot 1. Allemaal ongeacht de (een van de drie) positie in het slot.

Hoe assign ik nu (1-op-1) letter-combinaties aan de vrij plaatsen in de slots, zodat de cost minimaal is? Met de constraint dat er in elk slot nooit twee keer hetzelfde cijfer voorkomt?

Dit mag: 1{ A1, B2, A3}, 2{B1, C2, D3}

Dit niet: 1{A1, B1, ...} (cijfer 1 twee keer in zelfde slot)
Dit ook niet: 1{A1, B2, A3}, {A1, ...} (niet 1-op-1, A1 dubbel)

[ Voor 26% gewijzigd door Zoijar op 10-04-2009 22:43 ]

[Soultaker]

Hmm, toch géén multi-commodity flow?

Ik heb er een tijdje mee zitten puzzelen en ik heb sterk de indruk dat het wel in polynomiale tijd zou moeten kunnen, maar ik krijg het ook niet zo 1-2-3 gemapt op een standaardprobleem.

Wel een leuk probleem in ieder geval; ik ga er nog wel een nachtje over slapen...

[Zoijar]

Soultaker schreef op zaterdag 11 april 2009 @ 00:34:
Hmm, toch géén multi-commodity flow?

Hehe, nee, volgens mij toch niet. multi-commodity mag alles van elke node naar elke andere node in een flow netwerk, i.e. willekeurige sources en sinks. Volgens mij kan dit met de standaard enkele source en enkele sink. Het is erg lang geleden dat ik dit op "school" heb gehad...

Ik heb er een tijdje mee zitten puzzelen en ik heb sterk de indruk dat het wel in polynomiale tijd zou moeten kunnen, maar ik krijg het ook niet zo 1-2-3 gemapt op een standaardprobleem.

Wel een leuk probleem in ieder geval; ik ga er nog wel een nachtje over slapen...

Het idee dat ik nu heb is volgens mij goed.... en te doen, nog niet zeker, morgen proberen.

Schrijf het als flow netwerk, aangenomen bovenstaande voorbeeld, met een source S en een sink T node. Voor elke categorie is er een C_n node, en voor elk Slot is er een S_n node. Voeg edges toe van de Source S naar alle C_n nodes met capaciteit 26 (items per categorie), van alle Slots naar de sink node T met capaciteit 3 (aantal vrije posities per slot), en van elke node C_n naar elke node S_n met capaciteit 1 (een mogelijke assignment). Dan heb je een flow netwerk met capaciteiten, en vervolgens boeg je nog de costs toe voor elke edge C_n - S_n, en cost 0 voor de nodes van en naar source en sink.

Als ik het goed begrijp is dit op te lossen in iets van O(n^3) met een (complex) push-relabel minimum cost / maximum flow algoritme. Het netwerk is bijna exact gelijk aan een linear assignment netwerk, waarvan ik weet dat je het op deze manier kan oplossen. Het enige verschil is dat de capiteiten van en naar de source en sink nodes nu niet ook 1 zijn, maar 26 resp. 3 (of wat dan ook)

[ Voor 7% gewijzigd door Zoijar op 11-04-2009 01:18 ]

[Soultaker]

Ah, ik geloof dat ik het probleem dan toch niet goed begrepen had. Het lijkt er op dat kosten alleen bepaald worden door de categoriën en niet voor individuele agents/taken, en dat agents/taken niet 1-op-1 toegekend worden (want als je vijf keer drie slots hebt, dan kun je daar nooit alle tien keer zesentwintig items in assignen), klopt dat? Dat is toch net wat anders dan een assignment problem waaraan je categorie-restricties toevoegt.

In dat scenario lijkt jouw oplossing me prima; alle agents en alle tasks in één categorie zijn uitwisselbaar, dus kun je ze bundelen in een enkele edge. Het algemene geval (waarbij agents/taken in dezelfde categorie kunnen zitten maar verschillende kosten kunnen hebben) is lastiger.

[ Voor 9% gewijzigd door Soultaker op 11-04-2009 01:45 ]

[Zoijar]

Soultaker schreef op zaterdag 11 april 2009 @ 01:43:
Ah, ik geloof dat ik het probleem dan toch niet goed begrepen had. Het lijkt er op dat kosten alleen bepaald worden door de categoriën en niet voor individuele agents/taken, en dat agents/taken niet 1-op-1 toegekend worden (want als je vijf keer drie slots hebt, dan kun je daar nooit alle tien keer zesentwintig items in assignen), klopt dat? Dat is toch net wat anders dan een assignment problem waaraan je categorie-restricties toevoegt.

Ehmm ja, ik denk het wel. De kosten zijn per categorie/slot combinatie wel anders. Eigenlijk is het dus een assignment van categorieen aan slots, waarbij elke categorie N keer (26) assigned mag worden, en elk slot M (3) keer (maar nog steeds 1-op-1). Het kan idd dat een volledige assignment niet mogelijk is, maar in de praktijk denk ik dat het wel moet lukken en anders is het ook niet zo erg. iha heb ik 2x zoveel tasks als agents en maar een paar categorieen.

In dat scenario lijkt jouw oplossing me prima; alle agents en alle tasks in één categorie zijn uitwisselbaar, dus kun je ze bundelen in een enkele edge. Het algemene geval (waarbij agents/taken in dezelfde categorie kunnen zitten maar verschillende kosten kunnen hebben) is lastiger.

In het algemene geval krijg ik idd de uniqueness constraint er niet in op deze manier. Je kan wel nog andere costs per agent per slot hebben door de categorie nodes op te splitsen, maar niet verschillende cost per agent en task, want dan kan je niet de lijnen zo trekken dat er maar 1 agent uit een categorie in hetzelfde slot valt.

Een ander puntje bij mijn probleem is nog wat ik liever heb: maximum flow, of minimum cost. Daar bedoel ik mee dat de algoritmes proberen een maximale flow te krijgen, en onder de maxima de minimum cost. Maar misschien is er een oplossing met een iets lagere flow die een veel kleinere cost heeft. Dan zou ik liever die oplossing hebben. Maarja, als je dat doortrekt dan assign je gewoon helemaal niets met cost 0, en dat is ook niet de bedoeling.

Je kan trouwens die constraints wel heel makkelijk in een linear program uitdrukken door te zeggen dat de som van de slot edges/vars kleiner gelijk 3 is, etc. Volgens mij... is dat gewoon een LP omdat de constraint matrix unimodulair is (in dit geval allemaal 0 of 1) en efficient op te lossen, itt een integer programmering (IP) (alleen weet ik niet hoe je twee objective functies gebruikt; maximum flow (ie max. sum of flow on all edges) en minimum cost(min. sum cost for all edges)

[ Voor 10% gewijzigd door Zoijar op 11-04-2009 10:42 ]

[Creepy]

Even een stikje door naar SEA aangezien het over het algoritme gaat en niet de implementatie zelf.

[Soultaker]

Zoijar schreef op zaterdag 11 april 2009 @ 10:25:
Een ander puntje bij mijn probleem is nog wat ik liever heb: maximum flow, of minimum cost. Daar bedoel ik mee dat de algoritmes proberen een maximale flow te krijgen, en onder de maxima de minimum cost. Maar misschien is er een oplossing met een iets lagere flow die een veel kleinere cost heeft. Dan zou ik liever die oplossing hebben. Maarja, als je dat doortrekt dan assign je gewoon helemaal niets met cost 0, en dat is ook niet de bedoeling.

Je zou een augmenting path algoritme kunnen implementeren dat de flow steeds met één vergroot, en dan bereken je effectief voor alle flows van 1 tot N de minimale kosten per totale flow; dan kun je ondertussen of achteraf beslissen dat je liever b.v. N-1 of N-2 hebt (op basis van een domeinspecifieke afweging van de kosten en de flow).

Je kan trouwens die constraints wel heel makkelijk in een linear program uitdrukken door te zeggen dat de som van de slot edges/vars kleiner gelijk 3 is, etc. Volgens mij... is dat gewoon een LP omdat de constraint matrix unimodulair is (in dit geval allemaal 0 of 1) en efficient op te lossen, itt een integer programmering (IP)

Of unimodulariteit van de matrix er wat mee te maken heeft, weet ik niet, maar elk standaard minimum-cost maximum-flow probleem is uit te drukken als LP probleem, dus dat moet zeker kunnen. Er zijn geen echte integer constraints (behalve dat "toevallig" al je capaciteiten integer zijn, en je flow dat dus ook zal zijn).

alleen weet ik niet hoe je twee objective functies gebruikt; maximum flow (ie max. sum of flow on all edges) en minimum cost(min. sum cost for all edges

Ik denk dat de truc hetzelfde is als b.v. bij minimum-cost circulations: als x je totale flow is, en y de kosten, dan maximaliseer je 1000*x - y waarbij 1000 een getal is dat zo gekozen wordt dat 'ie groter is dan maximale kosten van een unit flow in het netwerk (b.v. som van alle unit-kosten in het netwerk).

Trouwens, wat dit betreft:

Als ik het goed begrijp is dit op te lossen in iets van O(n^3) met een (complex) push-relabel minimum cost / maximum flow algoritme.

Ik heb wel eens een preflow-push algoritme (zie Goldberg & Tarjan) geïmplementeerd dat in theorie een goede complexiteit had, maar in de praktijk was het eigenlijk altijd trager dan een simpel maar efficiënt geïmplementeerd augmenting path algoritme (Ford-Fulkerson). Ik zou dus beginnen met een augmenting path algoritme, wat véél eenvoudiger te implementeren is (zeker als je minimum-cost flows wil berekenen) en in de praktijk meestal ook best snel is (vooral voor integer flows met een laag maximum).

De worst-case complexiteit van Ford-Fulkerson is O(E*max_flow) en max_flow is in dit geval gelijk aan het minimum van het totale aantal agents en taken, en E het product van het aantal categoriën in agents en taken, dus alles bij elkaar lijkt me dat nog vrij goed te doen.

[ Voor 19% gewijzigd door Soultaker op 11-04-2009 14:44 ]

[Zoijar]

Soultaker schreef op zaterdag 11 april 2009 @ 14:37:
Je zou een augmenting path algoritme kunnen implementeren dat de flow steeds met één vergroot, en dan bereken je effectief voor alle flows van 1 tot N de minimale kosten per totale flow; dan kun je ondertussen of achteraf beslissen dat je liever b.v. N-1 of N-2 hebt (op basis van een domeinspecifieke afweging van de kosten en de flow).

Ik heb niet zo veel tijd, dus ik gebruik liever iets dat er al is. Ik heb nu de "lemon" graph library waar je max flow, min cost, en LP (via GLPK), etc kan oplossen. Zal er nog eens over denken, als het uberhaupt werkt

Of unimodulariteit van de matrix er wat mee te maken heeft, weet ik niet, maar elk standaard minimum-cost maximum-flow probleem is uit te drukken als LP probleem, dus dat moet zeker kunnen. Er zijn geen echte integer constraints (behalve dat "toevallig" al je capaciteiten integer zijn, en je flow dat dus ook zal zijn).

Je krijgt gegarandeerd een integer oplossing als je matrix unimodulair is (en de rest allemaal integer); bij flow problemen is dat idd zo

Ik denk dat de truc hetzelfde is als b.v. bij minimum-cost circulations: als x je totale flow is, en y de kosten, dan maximaliseer je 1000*x - y waarbij 1000 een getal is dat zo gekozen wordt dat 'ie groter is dan maximale kosten van een unit flow in het netwerk (b.v. som van alle unit-kosten in het netwerk).

Dat is wel een goeie om te onthouden

De worst-case complexiteit van Ford-Fulkerson is O(E*max_flow) en max_flow is in dit geval gelijk aan het minimum van het totale aantal agents en taken, en E het product van het aantal categoriën in agents en taken, dus alles bij elkaar lijkt me dat nog vrij goed te doen.

Oh, ok, zal eens kijken of er verschillende implementaties zijn. Ben toch van plan libraries te gebruiken.


Mijn requirements zijn trouwens veranderd... Ik moet nu voor elke individuele agent een cost assignen per multi-slot, dus niet uniform per categorie.

Ik heb nu dit bedacht, denk je dat dat werkt? Of efficienter kan?



Je ziet hier een source S, een Sink T, 3 categorieen met elk 2 agents (links), en 3 multi-slots met elk 3 vrij posities (rechts). Alle capaciteiten zijn 1, behalve naar de sink waar ze 3 zijn (aantal posities per multi-slot). Per categorie (links) heb ik de multi-slots gedupliceerd (midden, 3 keer 3, categorieen * multi-slots). De cost om een agent aan een multi-slot te assignen is nu C(I,J). Alle andere costs zijn 0.

[Soultaker]

Dat lijkt allemaal wel te kloppen, en ik zie ook geen mogelijkheid om nog edges weg te bezuinigen, dus ik zou zeggen implementeren maar.

Grappig trouwens dat je nu nog vrij dicht bij de algemene variant van het probleem (kosten voor individuele agent/slot combinaties) gekomen bent. Enig idee of je deze aanpak daartoe kan uitbreiden? (Ik kwam er iig met max flow niet uit.)

[Zoijar]

Soultaker schreef op zondag 12 april 2009 @ 14:47:
Dat lijkt allemaal wel te kloppen, en ik zie ook geen mogelijkheid om nog edges weg te bezuinigen, dus ik zou zeggen implementeren maar.

Grappig trouwens dat je nu nog vrij dicht bij de algemene variant van het probleem (kosten voor individuele agent/slot combinaties) gekomen bent. Enig idee of je deze aanpak daartoe kan uitbreiden? (Ik kwam er iig met max flow niet uit.)

Niet echt over nagedacht nog; ik denk misschien met een zelfde soort truckje aan de andere kant... weet ik niet

Hmm... ik hoop dat het een beetje haalbaar is om op te lossen. Mijn probleem heeft typisch iets van 3000 agents in 50 categorieen en 3000 slots van 3. Complexiteit met categorieen ten opzichte van klassiek linear assignment neemt linear toe met het aantal categorieen (aantal edges wordt ongeveer #categorieen keer zo groot); maw, het duurt in deze setting 50 keer zo lang. Ik vraag me af of dat een beetje redelijke complexiteit is. Het klinkt wel aannemelijk. Een assignment probleem oplossen met 10k (3000 x3 met dummy vars) agents en tasks duurde een minuut ofzo met het munkres algoritme. Munkres is O(n^3). ford-fulkerson is O(edges*maxflow), en #edges is in O(agents^3) dus dat is hetzelfde... 50x zo lang dan, een uur. Schaalt toch niet echt lekker...

Zit te denken om het te benaderen. Wellicht gewoon simpel door eerst eerst positie 1 van alle slots te vullen met een linear assignment, vervolgens positie 2 te vullen en dan alle edges van niet-unieke categorie assignments aan die slots weg te laten...

[ Voor 8% gewijzigd door Zoijar op 12-04-2009 15:21 ]

[Soultaker]

Het aantal edges is eerder iets als O(NM). Met Ford-Fulkerson komt daar nog wel een factor max_flow bij, dus dan kom je uiteindelijk toch op ongeveer O(NM²) uit.

Maar voor minimum cost flow moet je een kortste pad vinden, wat lastig is te implementeren in O(E), dus waarschijnlijk komt er nog een factor log V bij ergens. Wellicht maakt het voor de theoretische complexiteit niet uit, maar in de praktijk waarschijnlijk wel. (Het is het verschil tussen een simpele DFS of BFS om een willekeurig augmenting path te vinden, en b.v. Dijkstra's algoritme om een minimum cost augmenting path te vinden).

Dus ja, ik denk dat je met je tijdschatting wel aardig zit, maar ik zou het toch echt uitproberen voordat je een conclusie trekt of het wel/niet geschikt is. (Als het dan te traag is, heb je in ieder geval de optimale score waarmee je een benaderend algoritme kunt vergelijken, en dan kun je een betere afweging maken welk algoritme je in de praktijk wil gebruiken.)

[Zoijar]

Ja, ik maakte wat foutjes in mn vorige post, maar het idee klopte

Heb het geimplementeerd, en zo te zien werkt het. Best snel zelfs. Ik heb als optimalisatie alleen de laagste 100 "costs" per agent gepakt, dan kan je er nooit heel ver naast zitten volgens mij. (en het scheelt een factor 10-50 in het aantal edges)

[ Voor 18% gewijzigd door Zoijar op 14-04-2009 21:11 ]