Snelle toewijzingsapplicaties met het Hongaars algoritme

We hebben allemaal wel eens te maken met één of andere toewijzingsapplicatie. Bijvoorbeeld: studenten een examenversie toewijzen, een uur toewijzen voor een bepaalde afspraak op basis van beschikbaarheid, een werkgroep toewijzen aan bepaalde werknemers, ...

In veel gevallen kan dit simpel opgevangen worden, denk maar aan een biedingssite waar het product automatisch wordt toegewezen aan het hoogste bod. Echter doen er zich vaak ook veel complexere situaties voor. Bijvoorbeeld: toewijzing van een tijdslot om een examen af te leggen waarbij studenten zelf een voorkeur kunnen doorgeven.

Voor die laatste situatie gaan we een voorbeeldscenario uitwerken, waarbij we aan zoveel mogelijk studenten hun nummer één kunnen toewijzen.

We hebben een variabel aantal studenten en een array met tijdslots die elk x-aantal beschikbare plaatsen hebben (in totaal zijn er zo 78 beschikbare plaatsen):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
$students = range(0,10);

$slotsAvailability = [
    '10:00' => 2,
    '10:15' => 6,
    '10:30' => 3,
    '10:45' => 2,
    '11:00' => 8,
    '11:15' => 5,
    '11:30' => 10,
    '11:45' => 2,
    '12:00' => 10,
    '12:15' => 20,
    '12:30' => 2,
    '12:45' => 8,
];

We laten het script een willekeurige array aan voorkeuren genereren en maken nadien de vergelijking tussen een combinatorische oplossing en een oplossing die gebruikt maakt van het Hongaars algoritme.

Om de meest optimale combinatie te vinden, zouden we eerst alle combinaties moeten samenstellen en nadien aflopen welke mogelijk zijn.

Om alle combinaties te berekenen hebben we gebruik gemaakt van onderstaande functie:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public function combinations($arrays, $i = 0) {
    if (!isset($arrays[$i])) {
        return [];
    }
    if ($i == count($arrays) - 1) {
        return $arrays[$i];
    }

    // get combinations from subsequent arrays
    $tmp = $this->combinations($arrays, $i + 1);

    $result = [];

    // concat each array from tmp with each element from $arrays[$i]
    foreach ($arrays[$i] as $k => $v) {
        foreach ($tmp as $x => $t) {
            $result[] = is_array($t) ?
                array_merge([$v], $t) :
                [$v, $t];
        }
    }

    return $result;
}

Daarna bekijken we per combinatie of deze combinatie mogelijk is met het aantal beschikbare plaatsen voor een bepaald slot.
De eerste combinatie die we tegenkomen en waarvan alle plaatsen beschikbaar zijn, markeren we als $finalCombination.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
foreach ($combinations as $combination) {
    // Check if available
    $combinationOk = true;
    foreach ($slotsAvailability as $slot => $amount) {
        $arrayCountValues = array_count_values($combination);
        if (isset($arrayCountValues[$slot]) && $arrayCountValues[$slot] > $amount) {
            $combinationOk = false;
            break;
        }
    }
    if ($combinationOk) {
        $finalCombination = $combination;
        break;
    }
}

Deze oplossing is perfect doenbaar voor kleine toewijzingsmatrices.
Wanneer we naar een matrix gaan met meer studenten, merken we al snel dat deze oplossing tegen zijn limieten zit en bij ongeveer 15 studenten al out of memory gaat.

Er zijn dan twee manieren om dit op te lossen, het PHP proces meer geheugen geven of kijken naar een andere oplossing, zoals het Hongaars algoritme.

Het Hongaars algoritme is een zogenaamd combinatorisch optimalisatiealgoritme. Dit wil zeggen dat we de meest optimale combinatie gaan zoeken binnen een zeer grote collectie mogelijke combinaties, zonder al die combinaties te berekenen en te overlopen.

Er bestaan reeds verschillende uitgewerkte PHP classes waarmee je direct aan de slag kan.
Wij namen munkres.php (Munkres algoritme = Hongaars algoritme) als basis en herwerkten deze class naar HungarianAlgorithm.php zodat de class ook non-square matrices kan verwerken.

De class verwacht een niet-associatieve array als matrix. Het is belangrijk om dus ergens een mapping te hebben met de waardes die overeenstemmen met de indexes in onze matrix.

Deze matrix is als volgt opgebouwd (template + voorbeeld)
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$matrix = [
    '<student>' => [
        '<slot_1>' => '<hoeveelste keuze>',
        '<slot_2>' => '<hoeveelste keuze>',
        '<slot_3>' => '<hoeveelste keuze>',
    ],
    1 => [
        0 => 2,
        1 => 1,
        2 => 1,
        3 => 3,
        4 => 3,
        5 => 999,
    ]
];

Enkele opmerkingen hierbij:

• Indien een slot meerdere plaatsen heeft, moet dit meerdere keren in de matrix voorkomen. (bvb. slot 1 en 2 zijn beiden 10u15, slot 3 en 4 zijn beiden 10u45)
• Als er meerdere plaatsen zijn voor een bepaald slot, dient hier ook dezelfde voorkeur aan meegegeven te worden
• Indien er meer slots zijn dan mogelijkheden die een student mag kiezen. Er zijn bvb 12 slots, maar student mag slechts top 3 doorgeven, geven we voor de overige slots keuze 999 door, zodat deze zeker niet gekozen worden door het algoritme.

Wanneer we onze matrix hebben opgesteld, kunnen we deze doorgeven aan het algoritme en het algoritme zijn werk laten doen.
Als resultaat krijgen we een matrix in dezelfde vorm terug als de matrix die wij als input hebben meegegeven, enkel zijn de “hoeveelste keuzes” nu vervangen door nulletjes en een eentje. De waarde waar één bij staat is het slot dat voor die student geselecteerd werd.

Het enige wat je nu nog moet doen is deze selectie terug mappen naar de werkelijke waarde van het slot.
Als we in onderstaand voorbeeld bij slot 4 een 1 terugkrijgen, mappen we dat terug naar 10u45 voor Jane aan de hand van de SlotMapping en StudentMapping arrays.

Input	Output	SlotMapping	StudentMapping
$matrix = [     1 => [         0 => 2,         1 => 1,         2 => 1,         3 => 3,         4 => 3,         5 => 999,     ] ];	$matrix = [     1 (student) => [         0 => 0,         1 => 0,         2 => 0,         3 => 0,         4 => 1 (gekozen slot),         5 => 0,     ] ];	$slots = [     0 => 10u00,     1 => 10u15,     2 => 10u15,     3 => 10u45,     4 => 10u45,     5 => 11u00 ]	$students = [     0 => 'John',     1 => 'Jane',     3 => 'Chris' ]

 

Zoals eerder gezegd, ging de combinatorische oplossing reeds bij 15 studenten OOM op het berekenen van de combinaties. 
Wanneer we het Hongaars algoritme laten lopen voor hetzelfde aantal studenten, verloopt dit zonder enig probleem.

Wat kan het Hongaars algoritme nu precies betekenen qua performantie? We maken de vergelijking.
Het aantal tijdsslots bedraagt nog steeds 78 zoals aangegeven in het initiële voorbeeld. Elk resultaat is het gemiddelde van 5 tests.

Aantal studenten	Array combinations (s)	Hungarian Algorithm (s)
5	0.00143981	0.002079821
10	0.168286848	0.011980629
15	OOM	0.028774214
20	OOM	0.070318842
40	OOM	0.342720747
75	OOM	2.176020622

Voor kleine, simpele toewijzingen zal de combinatorische oplossing volstaan, maar moet je grote toewijzingsmatrices verwerken, dan is het Hongaars algoritme zeker een aan te raden oplossing. Heel snel te implementeren en inzetbaar voor verschillende doeleinden.

Wanneer gebruikmaken van het Hongaars algoritme, hieronder een overzicht:

• Wanneer we grote matrices moeten verwerken
• Toewijzing op basis van voorkeur en beschikbaarheid. Hierbij wijzen we zoveel mogelijk personen hun favoriete keuze toe.
• Toewijzing op basis van kosten. Hierbij wijzen we een taakverdeling zo toe, zodat de totale kost zo laag mogelijk is.

Wanneer gebruikmaken van de combinatorische oplossing of een andere oplossing:

• Kleine matrices van bijvoorbeeld 5x3. Hier zien we ook dat de combinatorische oplossing net iets sneller is.
• Toewijzing op basis van logische vergelijking. Bijvoorbeeld: hoogste bod, beste reputatie, diegene die het eerst was, ...
• Volledig willekeurige toewijzing. Bijvoorbeeld "secret santa"
• Wanneer er verschillende parameters in acht genomen moeten worden bij de toewijzing. Eventueel kunnen we hier ook kijken naar mogelijke uitbreidingen van het Hongaars algoritme, afhankelijk van welke parameters we moeten vergelijken.