1
$\begingroup$

I am a bit stuck with this problem; I found a temporary (an perhaps suboptimal) solution using Excel, but I'd like to hear your opinion /advice, please.

9 people want to form a group and go on on a trip together.
They have 5 possible destinations and 5 possible dates.
Each person gives a score for each destination and each date (separately, so 10 scores in total per person, not 25).
A score equal to 0 means that the person won't participate if the corresponding destination or date is chosen.
All scores different from 0 are normalized to sum up to 1 for each person, by destination and by date.

These are the data (in R):

tr_op <- structure(list(Dest_A = c(0.333333333, 0.285714286, 0.1, 0.333333333, 
0.263157895, 0.2, 0.2, 0.25, 0), Dest_B = c(0.266666667, 0, 0.5, 
0.333333333, 0.105263158, 0.2, 0.2, 0, 0), Dest_C = c(0.133333333, 
0.214285714, 0.3, 0, 0.263157895, 0.2, 0.2, 0.25, 0.5), Dest_D = c(0.2, 
0.357142857, 0.1, 0, 0.105263158, 0.2, 0.2, 0.25, 0.5), Dest_E = c(0.066666667, 
0.142857143, 0, 0.333333333, 0.263157895, 0.2, 0.2, 0.25, 0), 
    Date_1 = c(0.119047619, 0.294117647, 0.2, 0.238095238, 0.111111111, 
    0, 0.2, 0.095238095, 0.333333333), Date_2 = c(0.166666667, 
    0.058823529, 0.2, 0.238095238, 0.111111111, 0, 0.2, 0.095238095, 
    0), Date_3 = c(0.238095238, 0.294117647, 0.2, 0.047619048, 
    0.111111111, 0, 0.2, 0.095238095, 0.333333333), Date_4 = c(0.238095238, 
    0.058823529, 0.2, 0.238095238, 0.111111111, 0, 0.2, 0.238095238, 
    0), Date_5 = c(0.238095238, 0.294117647, 0.2, 0.238095238, 
    0.555555556, 1, 0.2, 0.476190476, 0.333333333)), .Names = c("Dest_A", 
"Dest_B", "Dest_C", "Dest_D", "Dest_E", "Date_1", "Date_2", "Date_3", 
"Date_4", "Date_5"), class = "data.frame", row.names = c(NA, 
-9L))

Each row is one person.
Each cell is the normalized score expressed by the person in the corresponding row, for the destination or date in the corresponding column name.

As there is no single destination or date everyone agrees about, they can't all go together, so they decide to split into two groups and do two trips (2 different destinations and 2 different dates).

The problem is to assign each person to a destination and a date, at the same time choosing the destination-date combinations that maximize the sum of normalized scores.
There is no need to include all the people.
However, there can't be more than 2 destinations or more than 2 dates, and obviously the people in the same group must all agree on the destination and on the date (i.e. a person can't be assigned to a destination or a date for which they gave score 0).

I used Excel's Solver, setting up binary cells as solution vectors and constraining them and their sums as needed; it concluded that the people corresponding to row 1, 3 and 4 should go to destination B on date 4, and the rest to destination D on date 5.
However, the problem as I set it up is (apparently) not linear programming, it can't be solved by simplex, and only the evolutionary method worked. So I am not sure I got a globally optimal answer.

--> How would you solve this?
Do you see any analogy with already known problems?
Can you suggest further reading / other posts or literature I could consult?

Thanks!

$\endgroup$
  • $\begingroup$ This can be solved by integer programming. Do you need to solve it in R? $\endgroup$ – Marcus Ritt May 25 '19 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.