# Designing a Drama-Free Guest List

So, you’re gonna have a **rad kickback at your place** and wanna invite your friends **Abby, Becky, Carl, Dan, Elise, and Francine**.

*But ….*

If you’re inviting Abby, you ** have** to invite Becky because they’re dating and it would look sooo

**shady**if you just invited one of them.

Alsooo if Becky’s gonna be there, then you ** absolutely cannot** invite Francine because they used to date and it

**did not end well**.

Oh yea, and Carl and Dan are both trying to get with Elise so if Elise is coming, then ** there’s no way** that Dan or Carl can be there.

Also, you sit down and **score how much you want each person at your party** and come up with this list:

**Who ends up getting an invite to your party?**

Well, since this is a pretty simple case, we can just logic it out here.

Let’s say we invite **Abby**. Then we have to also invite **Becky**. Also, then we cannot invite **Francine**. So it’s either **Abby + Becky or Francine**. **Abby + Becky gives us 25 points** while **Francine gives us just 10**. Too bad for Francine … **bye Felicia**. Abby and Becky are in.

Also, let’s say we invite **Carl and Dan**. Then **Elise** cannot be there. Vice versa, we can invite **Elise** but then we cannot invite **Carl or Dan**. **Carl + Dan gives us 25** and **Elise gives us 40**. So Elise gets an invite.

So, our final guest list is ** Abby, Becky, and Elise**, for a total of 65 points out of a possible 100. Not Bad!!

But what if it’s **more complicated**. Consider a bunch of amigos and the following restrictions:

Also, this is our **points list** for all our friends:

*Now what do we do??*

We can use a powerful mathematical solving technique called Linear Programming to solve this problem.

First, we set up the problem by having a **bunch of binary (0 or 1) variables**, each corresponding to one of our potential guests. For example, in Abby’s case:

and all other variables are defined similarly.

So **how do we say mathematically that Becky and Francine can’t both be at the party?**

Well, it’s fine if **Becky is there without Francine \((B=1, F=0)\)** or if **Francine is there without Becky \((B=0, F=1)\)**. It’s also fine if **neither is there \((B=0, F=0)\)**. So basically, we need that **\(B+F \leq 1\)** since the only unacceptable case is if both of them are there \((B=1,F=1 \to B+F=2)\).

How about if some people have to be at the party together? If **Abby and Becky have to be at the party together**, then **either \(A=0,B=0 \to A+B=0\)** or **\(A=1,B=1 \to A+B=2\)**. (See the notes for discussion on how to encode this as a set of constraints compatible with Linear Programming).

We can also get a bit fancier. For example if **we can either invite one couple (Louise and John) or another couple (Kal and Heidi)** (because of the lawnmower snafu), then we can encode that as: **\((L+J) + (K+H) \leq 2\)** (this works because \(L+J\) is either \(0\) or \(2\) and same with \(K+H\), so this constraint ensures that \(L+J\) and \(K+H\) are not both \(2\)).

Putting all our **constraints** into our Linear Programming model, along with our **preference points** for the potential guests, we quickly generate the optimal drama-free guest list:

Let’s do a quick check to make sure we can’t do better. The **highest scoring person**, Carl with 13 points, didn’t get an invite! But if he did, then we have to invite **Heidi and Louise** too because of the tennis team constraint. But then we have ** DRAMA** because we invited Heidi and Louise, whose

**husbands hate each other**. Don’t wanna get caught up in that mess!

So … yea. Let’s be honest. There’s just some people who can’t be around other people at your **kickback, bat mitzvah, wedding, etc.** And you don’t wanna deal with all that drama so just *let the math take care if it for you. :)*

Thanks for reading and please leave comments!

# Notes

For those familiar with the procedure of Linear Programming, you know that we are only allowed to combine our constraints using AND, i.e. we can say \(x + y \leq 4\) AND \(x - y \geq 3\) AND etc.

The constraint we mentioned in this post about making sure two people either attend a party together or not at all is actually an OR constraint. i.e. something like \(x = 0\) OR \(x = 2\). We can use something called the Big M method to convert this or constraint into a group of OR constraints. Namely, we convert the constraint \(x = 0\) OR \(x = 2\) into:

\[x \geq 0 \\ x - M \times z_1 \leq 0 \\ x + M \times z_2 \geq 2 \\ z1 + z2 = 1\]where we have introduced two new variables, \(z_1\) and \(z_2\), which are **both binary variables** and which **add up to 1**. We have also introduced a constant called **M** which is very large. We will set it to be **100**.

Note that the only two possible cases are \((z_1, z_2) = (0, 1)\) or \((z_1, z_2) = (1, 0)\). In the **former case**, our constraints reduce to:

which all just reduces to \(x = 0\).

In the **latter case**, our constraints reduce to:

which reduces to

\[2 \leq x \leq 100\]In our case, x is actually the sum of the two **binary** variables representing the two people we need at the party together and so it all reduces to \(x = 2\).

Thus, by introducing an extra set of variables, \(z_1\) and \(z_2\), **we are able to capture our OR constraint**.