In the following we are facing the problem of multiple assignments of the hungarian algorithm.
Scenario:
We have 100 students and 5 courses, which the students can vote with priority. So every student will get assigned for one specific course.
Priority from 1 to 5. 1 lowest, 5 highest
The raw data would look like this:
Obviously there are more rows than columns.
The problem we are facing is: we need more than one assignment per column.
Here is the PHP code which is responsible to do assignments with the Hungarian algorithm returning invalid results.
<?php
class Hungarian {
function Hungarian() {
//Default constructor
}
function do_hungarian($matrix)
{
$h = count($matrix);
$w = count($matrix[0]);
if ($h < $w)
{
for ($i = $h; $i < $w; ++$i)
{
$matrix[$i] = array_fill(0, $w, INF);
}
}
elseif ($w < $h)
{
foreach ($matrix as &$row)
{
for ($i = $w; $i < $h; ++$i)
{
$row[$i] = INF;
}
}
}
$h = $w = max($h, $w);
$u = array_fill(0, $h, 0);
$v = array_fill(0, $w, 0);
$ind = array_fill(0, $w, -1);
foreach (range(0, $h - 1) as $i)
{
$links = array_fill(0, $w, -1);
$mins = array_fill(0, $w, INF);
$visited = array_fill(0, $w, false);
$markedI = $i;
$markedJ = -1;
$j = 0;
while (true)
{
$j = -1;
foreach (range(0, $h - 1) as $j1)
{
if (!$visited[$j1])
{
$cur = $matrix[$markedI][$j1] - $u[$markedI] - $v[$j1];
if ($cur < $mins[$j1])
{
$mins[$j1] = $cur;
$links[$j1] = $markedJ;
}
if ($j == -1 || $mins[$j1] < $mins[$j])
{
$j = $j1;
}
}
}
$delta = $mins[$j];
foreach (range(0, $w - 1) as $j1)
{
if ($visited[$j1])
{
$u[$ind[$j1]] += $delta;
$v[$j1] -= $delta;
}
else
{
$mins[$j1] -= $delta;
}
}
$u[$i] += $delta;
$visited[$j] = true;
$markedJ = $j;
$markedI = $ind[$j];
if ($markedI == -1)
{
break;
}
}
while (true)
{
if ($links[$j] != -1)
{
$ind[$j] = $ind[$links[$j]];
$j = $links[$j];
}
else
{
break;
}
}
$ind[$j] = $i;
}
$result = array();
foreach (range(0, $w - 1) as $j)
{
$result[$j] = $ind[$j];
}
return $result;
}
/*$m = [
[ INF, 7858, 8743, 17325, 18510, 9231, 4920, 7056, 9701, 5034, 7825],
[ 8128, INF, 5021, 13603, 19635, 11386, 7075, 8840, 1843, 7189, 9256],
[ 6809, 5364, INF, 8582, 14614, 10067, 5756, 5904, 7207, 3882, 4235],
[ 7849, 5515, 1040, INF, 15654, 11107, 6796, 4713, 7358, 4900, 5275],
[10918, 8365, 4109, 5808, INF, 14176, 9865, 7928, 931, 7991, 8344],
[ 336, 7285, 2830, 11412, 17444, INF, 4347, 6483, 6688, 4461, 7065],
[ 1053, 2938, 3823, 12405, 15835, 4311, INF, 2136, 4781, 114, 2905],
[ 8930, 802, 5823, 14405, 20437, 12188, 7877, INF, 2645, 7429, 10058],
[ 9987, 7434, 3178, 11760, 17792, 13245, 8934, 6997, INF, 7060, 7413],
[10518, 2824, 3709, 12291, 15721, 13776, 9465, 2022, 4667, INF, 7944],
[ 2574, 4459, 5344, 9561, 17356, 5832, 1521, 3657, 6302, 1635, INF]
];
print_r(hungarian($m));*/
}
?>
EDIT: Here is the Sktip returning VALID RESULTS.
<?php
/*
Author: © Noli
Edited: 21.06.2015
Description: Klasse zur Verwendung der Ungarischem Methode
- Ermittlung des optimalzustands einer relation anhand von bipatite graph matching.
Portierung von © Noli
*/
class HungarianBipatiteMatching {
public $costMatrix = array();
public $rows = 0;
public $cols = 0;
public $dim = 0;
public $labelByWorker = array();
public $labelByJob =array();
public $minSlackWorkerByJob=array();
public $minSlackValueByJob=array();
public $matchJobByWorker=array();
public $matchWorkerByJob=array();
public $parentWorkerByCommittedJob=array();
public $committedWorkers=array();
public function HungarianBipatiteMatching($intMatrix) {
$this->rows = sizeof($intMatrix);
$this->cols = sizeof($intMatrix[0]);
$this->dim = max($this->rows,$this->cols);
for($i = 0;$i<$this->dim;$i++) {
$costMatrix[$i] = array_fill(0,$this->dim,0);
}
for ($w = 0; $w < $this->dim; $w++) {
if ($w < sizeof($intMatrix)){
if (sizeof($intMatrix[$w]) != $this->cols){
throw new InvalidArgumentException("Irregular cost matrix");
}
$this->costMatrix[$w] = $this->arrayCopyOf($intMatrix[$w],$this->dim);
}
else {
$this->costMatrix[$w] = array();
for($i = 0;$i<$this->dim;$i++){
$this->costMatrix[$w][] = 0;
}
}
}
for($i = 0;$i<$this->dim;$i++) {
$this->labelByWorker[] = 0;
$this->labelByJob[] = 0;
$this->minSlackWorkerByJob[] = 0;
$this->minSlackValueByJob[] = 0;
$this->parentWorkerByCommittedJob[] = 0;
$this->matchJobByWorker[] = 0;
$this->matchWorkerByJob[] = 0;
}
$this->committedWorkers = array_fill(0, $this->dim, false);
$this->matchJobByWorker = array_fill(0,$this->dim,-1);
$this->matchWorkerByJob = array_fill(0,$this->dim,-1);
}
public function computeInitialFeasibleSolution() {
for ($j = 0; $j < $this->dim; $j++) {
$this->labelByJob[$j] = INF;
}
for ($w = 0; $w < $this->dim; $w++) {
for ($j = 0; $j < $this->dim; $j++) {
if ($this->costMatrix[$w][$j] < $this->labelByJob[$j]) {
$this->labelByJob[$j] = $this->costMatrix[$w][$j];
}
}
}
}
public function execute() {
$this->reduce();
$this->computeInitialFeasibleSolution();
$this->greedyMatch();
$w = $this->fetchUnmatchedWorker();
while ($w < $this->dim) {
$this->initializePhase($w);
$this->executePhase();
$w = $this->fetchUnmatchedWorker();
}
$result = $this->arrayCopyOf($this->matchJobByWorker, $this->rows);
for ($w = 0; $w < sizeof($result); $w++){
if ($result[$w] >= $this->cols){
$result[$w] = -1;
}
}
return $result;
}
protected function executePhase() {
while (true)
{
$minSlackWorker = -1;
$minSlackJob = -1;
$minSlackValue = INF;
for ($j = 0; $j < $this->dim; $j++)
{
if ($this->parentWorkerByCommittedJob[$j] == -1)
{
if ($this->minSlackValueByJob[$j] < $minSlackValue)
{
$minSlackValue = $this->minSlackValueByJob[$j];
$minSlackWorker = $this->minSlackWorkerByJob[$j];
$minSlackJob = $j;
}
}
}
if ($minSlackValue > 0)
{
$this->updateLabeling($minSlackValue);
}
$this->parentWorkerByCommittedJob[$minSlackJob] = $minSlackWorker;
if ($this->matchWorkerByJob[$minSlackJob] == -1)
{
$committedJob = $minSlackJob;
$parentWorker = $this->parentWorkerByCommittedJob[$committedJob];
while (true)
{
$temp = $this->matchJobByWorker[$parentWorker];
$this->match($parentWorker, $committedJob);
$committedJob = $temp;
if ($committedJob == -1)
{
break;
}
$parentWorker = $this->parentWorkerByCommittedJob[$committedJob];
}
return;
}
else
{
$worker = $this->matchWorkerByJob[$minSlackJob];
$this->committedWorkers[$worker] = true;
for ($j = 0; $j < $this->dim; $j++)
{
if ($this->parentWorkerByCommittedJob[$j] == -1)
{
$slack = $this->costMatrix[$worker][$j]
- $this->labelByWorker[$worker] - $this->labelByJob[$j];
if ($this->minSlackValueByJob[$j] > $slack)
{
$this->minSlackValueByJob[$j] = $slack;
$this->minSlackWorkerByJob[$j] = $worker;
}
}
}
}
}
}
protected function fetchUnmatchedWorker()
{
$w;
for ($w = 0; $w < $this->dim; $w++)
{
if ($this->matchJobByWorker[$w] == -1)
{
break;
}
}
return $w;
}
protected function greedyMatch()
{
for ($w = 0; $w < $this->dim; $w++)
{
for ($j = 0; $j < $this->dim; $j++)
{
if ($this->matchJobByWorker[$w] == -1
&& $this->matchWorkerByJob[$j] == -1
&& $this->costMatrix[$w][$j] - $this->labelByWorker[$w] - $this->labelByJob[$j] == 0)
{
$this->match($w, $j);
}
}
}
}
protected function initializePhase($w)
{
$this->committedWorkers = array_fill(0,sizeof($this->committedWorkers),false);
//Arrays.fill(committedWorkers, false);
$this->parentWorkerByCommittedJob = array_fill(0,sizeof($this->parentWorkerByCommittedJob),-1);
//Arrays.fill(parentWorkerByCommittedJob, -1);
$this->committedWorkers[$w] = true;
for ($j = 0; $j < $this->dim; $j++)
{
$this->minSlackValueByJob[$j] = $this->costMatrix[$w][$j] - $this->labelByWorker[$w]
- $this->labelByJob[$j];
$this->minSlackWorkerByJob[$j] = $w;
}
}
protected function match($w, $j)
{
$this->matchJobByWorker[$w] = $j;
$this->matchWorkerByJob[$j] = $w;
}
protected function reduce()
{
for ($w = 0; $w < $this->dim; $w++)
{
$min = INF;
for ($j = 0; $j < $this->dim; $j++)
{
if ($this->costMatrix[$w][$j] < $min)
{
$min = $this->costMatrix[$w][$j];
}
}
for ($j = 0; $j < $this->dim; $j++)
{
$this->costMatrix[$w][$j] -= $min;
}
}
$min = array_fill(0,$this->dim,0); //ALERT
for ($j = 0; $j < $this->dim; $j++)
{
$min[$j] = INF;
}
for ($w = 0; $w < $this->dim; $w++)
{
for ($j = 0; $j < $this->dim; $j++)
{
if ($this->costMatrix[$w][$j] < $min[$j])
{
$min[$j] = $this->costMatrix[$w][$j];
}
}
}
for ($w = 0; $w < $this->dim; $w++)
{
for ($j = 0; $j < $this->dim; $j++)
{
$this->costMatrix[$w][$j] -= $min[$j];
}
}
}
protected function updateLabeling($slack)
{
for ($w = 0; $w < $this->dim; $w++)
{
if ($this->committedWorkers[$w])
{
$this->labelByWorker[$w] += $slack;
}
}
for ($j = 0; $j < $this->dim; $j++)
{
if ($this->parentWorkerByCommittedJob[$j] != -1)
{
$this->labelByJob[$j] -= $slack;
}
else
{
$this->minSlackValueByJob[$j] -= $slack;
}
}
}
public function arrayCopyOf($array, $size) { // Java API port
$tmp = array();
foreach($array as $arr) {
$tmp[] = $arr;
}
if(sizeof($array) < $size) {
for($i = 0; $i < $size-sizeof($array); $i++) {
$tmp[]=0;
}
}
return $tmp;
}
}
/*$m = array(
array(73, 52, 35, 83, 97, 18, 74, 58),
array(39, 61, 69, 93, 8, 29, 21, 80),
array(88, 54, 55, 28, 80, 32, 77, 86),
array(73, 82, 25, 34, 26, 13, 74, 25),
array(65, 65, 17, 92, 71, 85, 69, 39),
array(40, 32, 43, 45, 12, 41, 72, 41),
array(75, 33, 82, 48, 25, 65, 71, 9),
array(39, 32, 12, 48, 86, 77, 36, 69)
);
$hungarian = new HungarianBipatiteMatching($m);
$result = $hungarian->execute();
echo("RESULT");
print_r($result);
echo("<br>done");*/
?>
Note: Please be patient, this is a low quality port from Java.
Hence the algorithm is making a square matrix of this one, the result presents corrupted data.
I thought about diverse solutions.
Cut the matrix according to the column size, to produce a lot of square matrizes. This may break the algorithms main function.
Another solution is to assign as much as possible, and handle the rest in a new routine until there are no more entries left.
Apparently the algorithm does not yet provide this ability.
Is there maybe a solution to do this in MySQL, hence the raw data is stored in an MySQL DBS.
Assuming that course 1 can accommodate x_1 students, course 2 can accommodate x_2 students, ..., course 5 can accommodate x_5 students, create your initial matrix with x_1 columns for course 1, x_2 columns for course 2, ..., x_5 columns for course 5. Replicate each student's rating for course i within each of its x_i columns. There will be unassigned columns when the algorithm terminates unless your course capacity is not more than your number of students, and unassigned rows unless your course capacity is not less than your number of students.