Robocat and cat playing together. Image created with Dall·E by the author.

Finding Optimal Solutions with Branch and Bound

A powerful algorithm for solving discrete optimization problems

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!

Problem Introduction

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…