Branch and bound is the core algorithm behind many mixed integer programming (MIP) solvers. It is a great addition to your mathematical optimization toolkit, particularly useful for smaller problems or when the problem has numerous constraints. Additionally, its straightforward nature makes it accessible, no hard math formulas needed.
In this hands-on article, we will delve into a mathematical optimization problem. We will tackle it with the branch and bound algorithm, a great technique for solving such problems. Our focus will be on a cat-themed problem — because let’s face it, who doesn’t love cats? However, if you’re more of a dog person, feel free to mentally substitute ‘dog’ every time you come across ‘cat’ in our discussion. The principles and methods apply just the same!
Imagine you are the owner of a cat shelter. Every day, pet owners can bring their cats and you take care of them. Many people adopted a cat during COVID, but now everyone needs to be back at the office. Because of this your company is doing great.
Actually, a bit too great. You are having difficulties with placing all the cats in the rooms of your building. Sometimes you need to decline people because there are too many requests. That is why you decided to create an optimization algorithm to help you find the lowest number of rooms possible for all the cat registrations.
Let’s take a look at an example. Imagine that 3 cats requested to stay at your shelter. Their names are Lily, Charlie, and Meowster. How can we divide these three cats in different rooms? We need at most three rooms, and here are all the possible solutions of grouping the cats:
Partitions and the Bell number
As you can see, there are 5 possible ways to group the 3 cats. In math, the name for one way of grouping elements of a set is a partition. The Bell number corresponds to the total number of…