# Optimization problem: make as many friends as possible
**URL:** https://discourse.julialang.org/t/optimization-problem-make-as-many-friends-as-possible/105694
**Category:** General Usage
**Tags:** optimization
**Created:** [November 2, 2023, 12:20pm UTC](https://discourse.julialang.org/t/optimization-problem-make-as-many-friends-as-possible/105694 "2023-11-02T12:20:03Z")
**Posts on this page:** 11
**Page:** 1
### Author:  [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)
#### Post date: [November 2, 2023, 12:20pm UTC](https://discourse.julialang.org/t/optimization-problem-make-as-many-friends-as-possible/105694/1 "2023-11-02T12:20:03Z")
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.
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [November 2, 2023, 7:24pm UTC](https://discourse.julialang.org/t/optimization-problem-make-as-many-friends-as-possible/105694/2 "2023-11-02T19:24:50Z")
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 😄
---
### Author:  [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)
#### Post date: [November 3, 2023, 12:35am UTC](https://discourse.julialang.org/t/optimization-problem-make-as-many-friends-as-possible/105694/3 "2023-11-03T00:35:41Z")
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?
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [November 3, 2023, 12:47am UTC](https://discourse.julialang.org/t/optimization-problem-make-as-many-friends-as-possible/105694/4 "2023-11-03T00:47:41Z")
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
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.)
---
### Author:  [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)
#### Post date: [November 3, 2023, 1:09am UTC](https://discourse.julialang.org/t/optimization-problem-make-as-many-friends-as-possible/105694/5 "2023-11-03T01:09:46Z")
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.
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [November 3, 2023, 1:16am UTC](https://discourse.julialang.org/t/optimization-problem-make-as-many-friends-as-possible/105694/6 "2023-11-03T01:16:16Z")
> [@Tarny\_GG\_Channie](#):
>
> because everyone must have attended every task at least once.
Ah, I missed this requirement.
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [November 3, 2023, 1:18am UTC](https://discourse.julialang.org/t/optimization-problem-make-as-many-friends-as-possible/105694/7 "2023-11-03T01:18:07Z")
100-200 might be too large for MILP.
Not Julia, but take a look at [https://www.localsolver.com](https://www.localsolver.com). They’re quite good for this sort of problem.
---
### Author:  [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)
#### Post date: [November 3, 2023, 1:25am UTC](https://discourse.julialang.org/t/optimization-problem-make-as-many-friends-as-possible/105694/8 "2023-11-03T01:25:17Z")
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.
---
### Author:  [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)
#### Post date: [November 3, 2023, 1:50am UTC](https://discourse.julialang.org/t/optimization-problem-make-as-many-friends-as-possible/105694/9 "2023-11-03T01:50:16Z")
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.
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [November 3, 2023, 1:52am UTC](https://discourse.julialang.org/t/optimization-problem-make-as-many-friends-as-possible/105694/10 "2023-11-03T01:52:14Z")
I moved it back to general usage.
---
### Author:  [@Tarny\_GG\_Channie](https://discourse.julialang.org/u/Tarny_GG_Channie)
#### Post date: [November 3, 2023, 1:44pm UTC](https://discourse.julialang.org/t/optimization-problem-make-as-many-friends-as-possible/105694/11 "2023-11-03T13:44:54Z")
I’ve implemented the evaluation and printing function here.
```julia
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
```