Integer Programming - packing wolves and sheep

Question

I'm new to linear/integer programming and I'm trying to solve a little problem I made up. I want to "pack" animals into a minimum number of bins where some of the animals cannot co-exist (wolves and sheep). Here is a picture of my little flow network that's guiding me.

• Imagine that each animal node outputs 1 animal of that type.
• The maximum each bin can hold is 2 animals
• You don't want wolves together with sheep

I've figured out how to write constraints that would allow me to minimize the number of bins if there is no distinction in input type.

What I've tried so far is the following. I take two inputs and sum them. I also take the input type and compare them so that I get either a zero or 1. At the final node, multiple the 0 or 1 with the summation and you get either the sum or nothing.

My questions come into play here in the following:

• Is there such a thing as a comparison operation that you can use in Integer Programming? I can subtract two types and if it's zero, they're the same, otherwise no. I'm not sure how one would represent this mathematically if one wanted to solve something like this in software.
• My "solution" below won't work for just one sheep node since I can't compare sheep to anything to get the sheep through. Actually, if I were to do wolf and sheep first, and then wolf, this would return 0 as well. Would I have to duplicate my little tree snippet and run through all combinations of input nodes? Is there a more scalable way to do this?

Any suggestions are appreciated.

mj

Answer 1

I would approach it in the following way:

Suppose that I have the following sets:

• $A$ - the set of all type of animals, i.e. $A = \{\text{wolf},\text{sheep}\}$
• $B$ - the set of all possible bins. $B = \{B_1, \ldots, B_{n_B} \}$

Suppose I have the following parameters:

• $c$ - a 1-dimensional matrix of the size of $A$, indicating the number of animals, per type that exist. Example: $c = \{2,3\}$ would mean that there are 2 wolfs and 3 sheeps.
• $n_B$ - the number of bins available.

And suppose I have the following variable:

• $M$ - is the integer matrix $A \times B$ that represents the number of animals per bin. Rows are animals, columns are bins. $M(\text{wolf},B_1) = 2$, for example, would mean that there are 2 wolfs in bin $B_1$.

So, for example, the following matrix:

$$ M = \left[ \begin{array}{ccc} 2 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right] $$

would indicate that there are 2 wolfs in $B_1$, 1 in $B_2$ and 1 sheep in $B_3$.

Your model would be:

$$ \begin{align} & \text{Minimize} & & U = \sum_{i = 1}^{n_B} 1 & \text{such that} \sum_A M_{ab_{i}} > 0 \\ & \text{subject to} & & \sum_A M_{ab} \leq 2 & \forall b, \\ &&& \prod_A M_{ab} = 0 & \forall b, \\ &&& \sum_B M_{ab} = c_a & \forall a, \\ \end{align}$$

where $a$ is an element of $A$ and $b$ an element of $B$ and $b_i$ is the element of set $B$ at position $i$.

The OBJECTIVE FUNCTION U is the sum of all bins that are actually being used, and it is this sum that you want to minimize. There might be more elegant ways of defining that, but this is what I could think at the moment. Essentially you would count all bins that contain at least one animal - $\sum_A M_{ab_{i}} > 0$ represents that. In GAMS Programming language, I could represent this as what they call a dollar sign condition ($), check the language you are using to see how to impose this condition to the equation.

The FIRST CONSTRAINT indicates that there can be a maximum of 2 animals per bin - it translates to the following equations:

$$ \begin{align} & M_{\text{wolf},B_1} + M_{\text{sheep},B_1} \leq 2 &\text{(rules for bin $B_1$)} \\ & M_{\text{wolf},B_2} + M_{\text{sheep},B_2} \leq 2 &\text{(rules for bin $B_2$)} \\ ... \\ & M_{\text{wolf},B_{n_B}} + M_{\text{sheep},B_{n_B}} \leq 2 &\text{(rules for bin $B_{n_B}$)} \\ \end{align}$$

The SECOND CONSTRAINT limits the type of animals that can be put together - there can only be animals of one type in the bin, so that $M_{\text{wolf},B_1} \cdot M_{\text{sheep},B_1} = 0$, etc.

The THIRD CONSTRAINT limits the number of animals to be put in the bins to the number of animals available.