Forum Discussion
Solving 'The Assignment Problem' with Lambda
The Setup
The problem is simple. Given a 'cost matrix', assign tasks to workers to minimize total cost needed to complete the tasks. Workers may not perform more than 1 task.
Assignment problem - Wikipedia
Methods for Solving
The Hungarian algorithm is a very popular method for solving the problem. I don't think this method is transferrable to Excel and would not be capable of generating multiple solutions where there are ties for lowest cost.
Hungarian algorithm - Wikipedia
I believe another approach to solving the Assignment Problem is to essentialy generate all possible solutions to solving the rook's problem/rook polynomial.
Excel solution
I think my solution takes some inspiration from the rook's problem. My goal was to generate all possible combinations and then take only ones with minimal 'cost'. For this problem I built my solution to accomodate the addition of more 'workers' but locked the tasks at 3. Expanding the tasks beyond 3 is maybe something best handled in part by Python's itertools (A subject for another adventure!).
Discussion
I welcome any alternative approaches to solving this problem and/or any refinements to my solution. Attached you will find a workbook with the original cost matrix and a larger cost matrix for testing purposes. Happy Holidays!
'Solve
=LAMBDA(staff,cost_matrix,LET(
r, ROWS(staff),
c, COLUMNS(cost_matrix),
counter, SEQUENCE(r),
GenerateCombin, LAMBDA(a, v,
LET(
taskA, EXPAND(v, PRODUCT(r - 1, r - 2), , v),
filtered, FILTER(counter, counter <> v),
taskB, TOCOL(filtered * SEQUENCE(, r - 2, 1, 0)),
loop, LAMBDA(acc, val,
LET(
vector, TOCOL(FILTER(filtered, (filtered <> v) * (filtered <> val))),
VSTACK(acc, vector)
)
),
taskC, DROP(REDUCE("", filtered, loop), 1),
VSTACK(a, HSTACK(taskA, taskB, taskC))
)
),
combin_matrix, DROP(REDUCE("", counter, GenerateCombin), 1),
staff_matrix, INDEX(staff, combin_matrix),
val_matrix, INDEX(cost_matrix, combin_matrix, SEQUENCE(, c)),
totals, MMULT(val_matrix, SEQUENCE(c, , 1, 0)),
lowest, MIN(totals),
stack, DROP(HSTACK(staff_matrix, val_matrix, totals), , -1),
filtered_stack, TOCOL(FILTER(stack, totals = lowest)),
wrapped, WRAPROWS(filtered_stack, c),
IFERROR(VSTACK(Tasks, wrapped), "-")
))
In attached file PQ Assignment2 generates the required rows only
Though, it's slower than djclements initial approach (PQ Assignment1)
21 Replies
- No duplicates in the workers. A second entry for the same worker would make the second instance the 'B' entry, making it unique.
In attached file PQ Assignment2 generates the required rows only
Though, it's slower than djclements initial approach (PQ Assignment1)
Looked at doing it w/o generating the unecessary rows* - that's been a disaster so far 😞
Attached is consequently djclements' approach, automated when it comes to joining tables* > 2K with an input table of 25 rows
- =LET(
x,DROP(REDUCE(0,ROW(D6:D9),LAMBDA(a,d,VSTACK(a,LET(c,ROW(E6:E9)<>d,h,FILTER(ROW(E6:E9),c),
e,HSTACK(d,h,IF(MUNIT(3),,TOROW(h))),
v,IFNA(e,TAKE(e,1)),i,TOCOL(DROP(v,,2)),j,TAKE(v,,2),
HSTACK( SORTBY(VSTACK(j,j),MOD(SEQUENCE(ROWS(TAKE(v,,2))*2)-1,3)+1),FILTER(i,i))-5)))),1),v,INDEX(D6:F9,x,SEQUENCE(,3)),
s,BYROW(v,LAMBDA(a,SUM(a))),
VSTACK(D5:F5,INDEX(C6:C9,FILTER(x,s=MIN(s))),FILTER(v,s=MIN(s))))
Patrick2788 Nice solutions presented by everyone! Here's a Power Query option to add to the mix (see attached workbook). I am by no means a PQ expert... I just knew the logic/steps I wanted to follow and muddled my way through the editor until I found what I needed. Basically, I used table joins (many-to-many) to generate all possible permutations, then added custom columns to filter by unique workers and total cost. Enjoy!
This PQ solution is very clean and works well with the larger personnel matrix, too! It's amazing how many options are available to solve this problem in Excel 365 in 2023 vs 2018, for example. Lambda, PQ, Solver, etc. - take your pick.
Really Interesting Problem!! My approach is similar to yours - generate all the permutations and filter for minimum total.
=LET( workers, Workers, tasks, Tasks, matrix, Costs, nWorkers, ROWS(workers), nTasks, COLUMNS(tasks), s, SEQUENCE(, nTasks), div, nWorkers ^ s, permuta, ROUNDUP( (MOD(SEQUENCE(MAX(div)) - 1, div) + 1) / (div / nWorkers), ), permut, FILTER( permuta, BYROW(permuta, LAMBDA(x, COLUMNS(UNIQUE(x, 1)))) = nTasks ), mat, INDEX(matrix, permut, s), Ttl, BYROW(mat, LAMBDA(x, SUM(x))), arr, FILTER(permut, Ttl = MIN(Ttl)), REDUCE( tasks, SEQUENCE(ROWS(arr)), LAMBDA(a, b, VSTACK( a, LET( k, CHOOSEROWS(arr, b), VSTACK(INDEX(workers, k), INDEX(matrix, k, s)) ) ) ) ) )- Excellent
- This is excellent. I like the way you generated the permutations. It's similar to a method that was discussed in the 0-1 Knapsack discussion. It's short and very elegant.
I folded your formula into 'SolveX' and it handled the larger cost matrix with ease!Patrick2788 Thank you!! Glad to hear it worked on larger matrix.
Great work! I'm sure I can't offer any improvements to your formula, but this inspired me to create something demonstrating the same with Python in Excel, though it doesn't deal with the "multiple solutions" part.
In case it's of interest:
https://www.linkedin.com/posts/owenhprice_linear-sum-assignment-using-python-in-excel-activity-7141472947608666112-IUqb- Thanks for the reply! Your video looks interesting and I'll be watching it when I'm off work.
