$2$ The Problem

A bride and groom recently got engaged and are currently planning their wedding, to which they have invited $29$ guests. After the ceremony, all the guests will sit down for a banquet. However, the bride and groom are having difficulty deciding where everyone should sit. The venue has $5$ tables available and each table seats $6$ people. They would like their guests to sit with as many familiar people as possible and, to this aim, they have organised their guests into groups as shown in Table $1.$ Ideally, all groups would remain intact, but the bride and groom understand that this might not be possible and that some groups might need to be split between tables. However, they have requested that groups should not be split between more than $2$ tables. They have asked you to find the optimal seating positions such as to minimise the number of split groups.

$1$

$\backslash$table$[[$Group$,$Members$],[1,$Rachel, Marah, Sam$],[2,$Andrew, Daisy, Ben, Abby$],[3,$Briony, Henry$],[4,$Emma, Edward, Arun, Will, Lilly$],[5,$Steve, Lucy, Lewis, Harry, Emily, Katie$],[6,$Lisa, Jessica, Rhiannon, Jake$],[7,$Sophie, Claire, Nick, Terry, Amy$]]$

Table $1$: Guest Groups

$3$ Questions

Q$1$ Formulate a mathematical program to model the seat assignment problem.

$(25$ Marks$)$

Q$2$ Solve the model in Xpress and present your solution $($use default options for the solver$).$

$(25$ Marks$)$

Q$3$ The bride and groom are concerned that the current model might cause exactly one person to be separated from the rest of their group. Find a way to update your model such that groups cannot be split into single individuals. Find and present the new solution.

$(15$ Marks$)$

Q$4$ The day before the wedding, one of the tables breaks. There aren't any spares and instead the venue replaces it with $2$ tables, one of which seats $4$ and the other seats $2($for a total of $6$ tables$).$ Update your model to accommodate this change. Find and present the new solution.

$(15$ Marks$)$

Q$5$ The bride and groom understand that some groups might need to be split in order to accommodate all of their guests. However, when deciding which groups to split, they state that some groups should not be split with high priority over others. As a motivating example, think about the case when, e$.$g$.,$ group $1$ contains the bridesmaids and should not be split unless absolutely necessary. The same might hold for group $2,$ which contains close family members, and ideally should not be split, but this is not as important as it is for group $1.$

Demonstrate how you can modify your model to accommodate the groups having varying priorities. In particular, supported by experimental results, choose an assignment of the parameters in the new model for which the group$($s$)$ that was split in Q$4$ is $($are$)$ now not split.

$(20$ Marks$)$