Optimization problem: make as many friends as possible

General Usage
1

Julians, I heard you like performance contests, here is one.
Problem statement:
A company wants to teach its employees how to work on tasks. It also wants them to make as many friends as possible. Two people become friends if they’ve worked with each other. The problem is to maximize a pair of friends that are made.
There are R rounds.
There are N<=R tasks, each task requires k people. There are N*k people in total.
To make sure everyone understands the entire process, everyone must attend all N tasks.
For example, with R=3, N=3, k=3
You could assign the tasks as follows.
Round 1:
Task 1: 1 2 3
Task 2: 4 5 6
Task 3: 7 8 9
Round 2:
Task 1: 4 8 9
Task 2: 2 3 7
Task 3: 1 5 6
Round 3:
Task 1: 5 6 7
Task 2: 1 8 9
Task 3: 2 3 4
For any task, the better solution found in under 1 minute wins. If there is a tie, the faster one wins.
To encourage CPU-agnostic optimizations, code may be run on multiple CPUs.
GPU versions are also accepted, they will be considered a separate category.
All Julia libraries are allowed.

1 Like
2

I’ve moved this to the ‘Optimization (Mathematical)’ section. It seems like a problem you should be able to model as a MIP with JuMP, and solve very large problems in seconds, not minutes :smile:

1 Like
3

I’m afraid I’m not sure. MIP is NP-hard and there could be thousands of variables with the input as low as 10. I’m not sure if it would fall into the “easy” case or the “hard” case. Do you have an experience to know if an MIP problem would be easy or hard?

4

What size of R, N, k are you looking to solve?

But also, can’t you just design a rolling schedule? Optimization might only be useful if there are different constraints:

julia> function next(x::Matrix{Int})
           y = similar(x)
           i, j = 1, 1
           for k in 1:length(x)
               y[i, j] = x[k]
               j += 1
               if j > size(y, 2)
                   j = 1
                   i += 1
               end
           end
           return y
       end
next (generic function with 1 method)

julia> x = [1 2 3; 4 5 6; 7 8 9; 10 11 12]
4×3 Matrix{Int64}:
  1   2   3
  4   5   6
  7   8   9
 10  11  12

julia> x = next(x)
4×3 Matrix{Int64}:
  1   4   7
 10   2   5
  8  11   3
  6   9  12

julia> x = next(x)
4×3 Matrix{Int64}:
  1  10   8
  6   4   2
 11   9   7
  5   3  12

julia> x = next(x)
4×3 Matrix{Int64}:
 1   6  11
 5  10   4
 9   3   8
 2   7  12

julia> x = next(x)
4×3 Matrix{Int64}:
 1  5   9
 2  6  10
 3  7  11
 4  8  12

(I guess this doesn’t work for square systems, but you get the idea.)

5

It was a toy problem adapted from a problem I received several years ago. I’d say R,K,N of at least 10 but could be fun if you could solve for R,K,N = 100-200. Also, the rolling schedule you gave me doesn’t exactly work because everyone must have attended every task at least once.

6

Ah, I missed this requirement.

7

100-200 might be too large for MILP.

Not Julia, but take a look at https://www.localsolver.com. They’re quite good for this sort of problem.

8

Several years ago, I was given this problem with R=8, n=k=6. I could hand-solve it or computer-solve it. Initially, there was no extra constraint and you could optimize for friends-making fully. I did something like a rolling schedule but was not sure if it would be optimal and with my limited knowledge at the time, I settled with random trials and having the best solution win. However, with this new extra requirement, it became much harder. I could no longer just randomly assign people to tasks and wish it would work. It was a fiendishly difficult problem for me several years ago and I couldn’t solve it. I brought it up again because I think it would be a fun problem.

1 Like
9

Also, I’m a bit doubtful this belongs in the mathematical optimization category. While reformulating it as an MILP may work, so might other methods, so I was doubtful it belongs in this category.

10

I moved it back to general usage.

1 Like
11

I’ve implemented the evaluation and printing function here.

function print_tasks(x::Array{Int,3})
    for round in axes(x)[3]
        println("round ",round)
        for task in axes(x)[2]
            print("Task ",task,": ")
            println(join(x[:,task,round]," "))
        end
    end
end

function evaluation(x::Array{Int,3})
    occupied = falses(size(x)[2]*size(x)[1],size(x)[3])
    for round in axes(x)[3], task in axes(x)[2], person in x[:,task,round]
        occupied[person,task] = true
    end
    if !all(occupied)
        return -1
    end
    A = Set{Tuple{Int,Int}}()
    for round in axes(x)[3]
        for task in axes(x)[2]
            Tmp = x[:,task,round]
            for i in axes(x)[1], j in axes(x)[1]
                if Tmp[i]!=Tmp[j]
                    push!(A,(Tmp[i],Tmp[j]))
                end
            end
        end
    end
    return length(A)÷2
end
1 Like