# Wedding Table Assignment Problem using Julia

This post has been upgraded to use Julia 1.1 and JuMP 0.19.

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) - Int(table[end]))
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(with_optimizer(Cbc.Optimizer))

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)

optimize!(m)

println("Objective value: ", objective_value(m))

Objective value: 12.0


Collective happiness is 12, apparently. :)

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 value(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)


Updated: