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