Find the combination of variables in base of their score

Question

I want to solve a problem with Python (like a programming riddle). It isn't an exercise or anything related with this, but something I figure and I want to find a solution for it.

Problem description:

• Let's say that I have a business with 10 different working positions.
• Each position has a few different sub-positions. For example (aggressive, relaxed, normal). But, the sub-positions do not be the same for every position. Other have 1, other have 2, other 3.
• I have 20 people with their performance-score in every position and sub-position.

The final score of the business production will be the sum of each score in every position. I want to find the combination that will have the highest score.

A few thoughts:

• Not all the people will get the job, since the positions are less than the number of people.
• I cannot have two people in the same position.
• My first attempt was to take the highest score of each people and trying to fill all the positions one by one. But this ended up with a problem. A problem similar to the traveling salesman.

So, what should be my next option? Any Python implementation ideas?

Edit: A few more details closer to Python

positionslist = [pos1, pos2, pos3, pos4, pos5, pos6, pos7, pos8, pos9, pos10]
subpositions = {"pos1":["A","B"], "pos2":["B","C"],"pos3":["A","B","C"],"pos4":["A"],"pos5":["A","B"],"pos6":["A","B","C"],"pos7":["B"],"pos8":["C"],"pos9":["A","C"],"pos10":["A"]

peoplelist = [{"pos1 A":15,"pos1 B": 8, "pos2 B": 2, "pos2 C": 4, "po3 A": 2, "pos3 B":5...}, {"pos1 A":1, "pos1 B":23,"pos2 B":11,.....},.........]

#run the code

print "best combination:" result

best combination:
pos1 B, person 3, score 23
pos2 C, person 5, score 11
pos3 A, person 18, score  ..
pos4 
pos5
pos6
pos7
pos8
pos9
pos10
Total Score: ....

As I said, my implementation in pseudo-code is:

for position in positionlist:
    for every sub-position:
        find the highest score from every person
    find the highest sub-position from the previous step
    remove that person from the peoplelist
    store the position with the sub-position and the person

However, this is similar to Traveling Salesman Problem and it will end up with not the highest combination.

Answer 1

Problem is called maximum matching in bipartite graph or assignment problem. It is done by Hungarian algorithm.

On Wikipedia page are implementations in different languages. There is python library munkres with an implementation.

Answer 2

If I have read this right every person has a different score for each position, and you want to find the highest score across all the combinations of people and positions - i.e. you have to calculate everyones score for each position.

I can't think of a way of expressing this that isn't the same as the Travelling salesman problem - although this is it in reverse - effectively finding the highest score combination rather than the lowest combinations.

If that is the case, then all you will be able to do reliably in a reasonable time (for any large data set) is to get a sub-optimal score which is close to and maybe exactly the optimal, but impossible to prove it is sub-optimal or optimal.

One way to try to make this simpler would be to prioritise the positions you want to fill, and get the highest score for each position in priority order - however this may not even be a close to optimal solution when compared to the non-prioritised position list.