Help me out - optimization problem

Question

Hi everyone!

I work in the personalization/CRM/CVM area. I have a problem that I would appreciate some input. I am fairly certain that there exists algorithms to solve this problem. But I haven't worked with problems like this before.

A silly example to present the problem.

Assume that we have 10 people. Each of them will be served one dish. We have three different dishes. Everyone have scored each dish between 1 and 10.

Now our task is to serve this dishes such that we get the highest sum of scores. But we have some limits. We need to serve dish 1 to at least two people, dish 2 to at least three people and dish 3 is free from limits.

So I'm looking for some reading in this area. I have a vague memory of a similar problem, but with ranked preferences.

Edit: In reality I have close to 20 dishes and millions of people.

Answer 1

Linear programming. It’s really just a summation of all the possible combinations and selecting the highest possible combination under the set constraints. So you have your objective, being the max sum, your decision variables, which are the relevant variables as inputs, such as the number of people you mention, the number of them you need to feed each dish to, the number of dishes etc. and finally your constraints. So optimization programs typically take a form similar to

Max(sum(x1+x2+x3)) (etc.)  
Subject to

Constraints, (of course specified with the required math for each decision variable specified as constraints). Basically you just need to come up with a set of equations for relating all of your variables to each other and the constraints, so whatever that looks like mathematically.

You can look in Python like SciKit or other open source platforms like Lingo but it’s all basically linear algebra. It can be computationally ‘expensive’ though which is why such programs help to make it faster and make it easy to plug in the variables to functions.

Answer 2

This is basically a constrained optimization problem, look up nloptr library in R, it should have multiple algos to deal with this.

Answer 3

Harmonic means thank me later

Answer 4

Would pyomo in Python work?

Answer 5

In your example the total is 2(avg1) + 3(avg2) + 5(avg of served)

You only have control over 5 plates, so serve the highest rated dish.

Answer 6

there are only 3\^10=59049 possible ways to distribute the dishes even before the restriction of having required numbers for dishes 1 and 2.  At this size I think it would be simplest to just run through all 59049 possibilities and find the best score among those with the required number of dishes 1 and 2.  


As an illustration I wrote up this quick and ugly python code  


    from random import randrange

score_grid = [[randrange(1,10) for j in range(3)] for i in range(10)]
for i in range(10):
    print(score_grid[i])

best_score = 0
best_choice = []
for p1 in range(3):
    for p2 in range(3):
        for p3 in range(3):
            for p4 in range(3):
                for p5 in range(3):
                    for p6 in range(3):
                        for p7 in range(3):
                            for p8 in range(3):
                                for p9 in range(3):
                                    for p10 in range(3):
                                        choices = [p1,p2,p3,p4,p5,p6,p7,p8,p9,p10]
                                        scores = [score_grid[i][choices[i]] for i in range(10)]
                                        total_score = sum(scores)
                                        d1_count = sum([1 if c==0 else 0 for c in choices])
                                        d2_count = sum([1 if c==1 else 0 for c in choices])
                                        if d1_count>=1 and d2_count>=3:
                                            if total_score > best_score:
                                                best_score = total_score
                                                best_choice = choices
print(best_score)
print(best_choice)


This first generates a random set of scores for each person and dish.  Then it runs through all the possibilities and finds the best possible score.  Here is an example result  


\[3, 4, 3\]
  
\[4, 5, 6\]
  
\[9, 2, 3\]
  
\[6, 1, 9\]
  
\[7, 5, 7\]
  
\[1, 8, 3\]
  
\[2, 3, 3\]
  
\[6, 3, 4\]
  
\[5, 6, 7\]
  
\[8, 1, 4\]
  
PS C:\\Users\\danie> & C:/Users/danie/AppData/Local/Programs/Python/Python310/python.exe c:/Users/danie/Downloads/great\_snakes\_35381fca29d68d8f3f25c9fa0a9026fb.py
  
\[2, 6, 1\]
  
\[3, 3, 1\]
  
\[5, 3, 7\]
  
\[6, 2, 7\]
  
\[1, 9, 7\]
  
\[1, 6, 4\]
  
\[9, 9, 6\]
  
\[4, 9, 5\]
  
\[8, 5, 2\]
  
\[2, 5, 5\]
  
69
  
\[1, 0, 2, 2, 1, 1, 0, 1, 0, 1\]  


First set of 10 lists are the scores of each player and dish so \[2,6,1\] means person 1 gave scores of 2,6, and 1 to dishes 1,2, and 3 respectively.  


Then 69 was the best possible score found with   
\[1,0,2,2,1,0,1,0,1\] being the best possible choice of dishes for each player where 0 is dish 1, 1 is dish 2, and 2 is dish 3.

Answer 7

Gurobipy is also a very intuitive package for LP problems