Teaching Note—Using the Maximum Clique Problem to Motivate Branch-and-Bound

In the typical OR classroom, the method of branch-and-bound is most often introduced when solving integer programs. In this note, we discuss teaching a branch-and-bound procedure motivated by the maximum clique problem rather than by a more traditional integer program. This teaching method is beneficial not only because it provides an alternate perspective on branch-and-bound for students, but also because it requires no optimization software to illustrate. The method is particularly useful in early optimization courses where students have math and engineering backgrounds. There is much literature focused on optimization students with non-technical backgrounds; we present a teaching method specifically intended to enhance the learning process for the more technical students.