# Wedding Table Assignment Problem using Julia

This is a port from Python of the Wedding Table Assignment example from PuLP.

This is an example of a **set partitioning** problem. We have a *universe* of guests and subsets of tables that have to *exactly* cover our universe, i.e. the guests.

```
using JuMP, Cbc
using Combinatorics
```

We start with a little helper function to calculate “happiness” of a table, determined by how close the guests are (by their letter):

```
function happiness(table):
"""
Find the happiness of the table
- by calculating the maximum distance between the letters
"""
return abs(Int(table[1][1]) - Int(table[end][1]))
end
```

We set up the number of table, table size, and an array of our guests:

```
max_tables = 5
max_table_size = 4
guests = ["A" "B" "C" "D" "E" "F" "G" "I" "J" "K" "L" "M" "N" "O" "P" "Q" "R"]
```

```
1×17 Array{String,2}:
"A" "B" "C" "D" "E" "F" "G" "I" … "L" "M" "N" "O" "P" "Q" "R"
```

Then we generate the possible combinations of guests to tables up the maximum table size:

```
table_combos = [collect(combinations(guests, t)) for t in 1:max_table_size];
```

```
table_combos[end][end]
```

```
4-element Array{String,1}:
"O"
"P"
"Q"
"R"
```

And we flatten that out:

```
possible_tables = []
for i in 1:length(table_combos)
append!(possible_tables, table_combos[i])
end
```

We end up with `3,213`

possible tables. Time to run an optimizer to pick the best combos!

```
length(possible_tables)
```

`3213`

### Our Model:

```
m = Model(solver=CbcSolver())
num_possible_tables = length(possible_tables)
idx_possible_tables = 1:num_possible_tables
@variable(m, table_assignment[idx_possible_tables], Bin)
# Objective: maximize happiness = minimize happiness value
@objective(m, Min, sum([happiness(possible_tables[t]) * table_assignment[t]
for t in idx_possible_tables]))
@constraint(m, sum([table_assignment[t]
for t in idx_possible_tables]) <= max_tables)
# because this is a set partitioning problem, we enforce a strict equality constraint
# - i.e. every guest has to be seated
for guest in guests
@constraint(m, sum([table_assignment[t] for t in idx_possible_tables
if guest in possible_tables[t]]) == 1)
end
;
```

(This is a fairly large model, so we won’t print it)

```
status = solve(m)
println("Objective value: ", getobjectivevalue(m))
```

```
Objective value: 12.0
```

Collective happiness is 12, apparently. :)

```
table_assignment
```

We end up with the following table assignments, optimized by guest happiness:

```
[("Table: ", possible_tables[i], "Happiness: ", happiness(possible_tables[i]))
for i=1:length(table_assignment) if getvalue(table_assignment[i]) == 1 ]
```

```
5-element Array{Tuple{String,Array{String,1},String,Int64},1}:
("Table: ", String["Q", "R"], "Happiness: ", 1)
("Table: ", String["E", "F", "G"], "Happiness: ", 2)
("Table: ", String["A", "B", "C", "D"], "Happiness: ", 3)
("Table: ", String["I", "J", "K", "L"], "Happiness: ", 3)
("Table: ", String["M", "N", "O", "P"], "Happiness: ", 3)
```

## Comments