Linear Program with Mutually Exclusive Variables - Best Method to Solve

Question

So I'm pretty sure that its not possible to set up a linear-program that has non-binary mutually exclusive variables (but would love to be wrong here).

It seems like it would be possible to solve the problem through "brute force" and create a bunch of "sub-linear-programs" by removing all exclusive variables except one, and iterating until you've gone through each combination.

However, this seems wasteful and prone to combinatorial explosion.

For example, say you're solving a problem where you have the mutually exclusive variables of :

Set A: [dog, cat]

Set B: [diet-coke, Mentos]

This approach would require me to build 4 linear programs; and take the best result.

Is there a better way to tackle this problem?

Answer 1

Let $y_{dog}$ and $y_{cat}$ be binary variables that take value $1$ if and only if the dog and cat are selected, respectively. Let $x_{dog}$ and $x_{cat}$ be the number of dogs, cats that are selected.

You cannot select a cat and a dog : $$ y_{dog}+y_{cat} = 1 $$

If the number of dogs/cats that are selected is larger than $1$, then the corresonding binary variables takes value $1$: $$ x_{dog} \le M y_{dog} \\ x_{cat} \le M y_{cat} $$

$M$ is a large constant. This way, if $x_{dog} \ge 1$, then $y_{dog}$ must take value $1$. And if $y_{dog}=0$, then necessarily $x_{dog}=0$. Likewise for $x_{cat}$.

Answer 2

Just tried @JWally's approach and I think I can explain a bit further.

You want a couple of things to happen:

First, you want to separate your variables. For each animal (dog, bird, cat, worm, elephant, etc.) you'll now have two x's: x_include and x_quantity.

You'll want to create a restriction to set the domain for all x_include_animal as binary straight away.

Next, you want to make them mutually exclusive. For each set of mutually exclusive animals, you create a restriction as follows:

x_include_dog + x_include_cat + x_include_mouse = 1 x_include_cat + x_include_fish = 1

Now you'll have a variable telling you whether an animal will be included. This is a neat format because you can have an arbitrary number of sets of mutually exclusive variables in the same model.

At this point, the program does not make sense as you could have x_dog_include be 0 and still have x_dog_quantity be any number. In other words, you haven't yet linked the x_include variables to their corresponding x_quantity variables. To solve this, we add another set of restrictions:

(HUGE NUMBER) * x_include_animal >= x_quantity_animal

Multiplying by the big number, aka M, is the key here as it ensures that as soon as you include an animal, you get a number that will for all intents and purposes be bigger than your quantity of animals and therefore fulfills the restriction. (If you're working with thousands of animals, pick a number in the millions or billions to be safe.)

I struggled a bit to understand this last part because I was thinking of the restriction as directional, so to speak. I was understanding the goal as making the x_quantity_animal depend on whether or not the include variable was set to 1. But it is actually perfectly ok to think of it the other way around. You're making it so the x_include_animal variable HAS to go to 1 to fulfill this restriction as soon as you pick a non-zero quantity. The program then sees that you're now breaking the exclusivity restriction and looks for another solution by altering quantities in a way that does not break it.

Here's a neat thing: You could expand this further say by having more inclusion variables.For example, (x_includeROOM1_animal and x_includeROOM2_animal), ensures mutually exclusive animals are not placed in the same room. The intuitive explanation of this method are left as an exercise to the writer, as I just figured out how to deal with OP's original question.

PS: I'm new to using LP so apologies if I'm using the wrong terms. This answer expands on @JWally's answer (thanks a lot btw!), so it would have probably been a better idea to post it as a comment (but this is a brand new account lol).

Hope this answer to a months-old thread helps!