Teaching Note—Using the Maximum Clique Problem Brand-and-Bound

Dawn M. Strickland - stricklandd@winthrop.edu
Department of Mathematics, Winthrop University, Rock Hill, South Carolina

Abstract

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.

Key words
integer programming, branch-and-bound, graph theory, graph color, cliques

History
Received: March 6, 2007; accepted December 18, 2007. This paper was with the author 5 months for 1 revision.

Download the PDF
10.1287/ited.8.2.96

Citation Information
Strickland, D. M. 2008. Teaching Note—Using the maximum clique problem branch-and-bound. INFORMS Trans. Ed. 8(2) 96-99. Available online at http://ite.pubs.informs.org/.

DOI: 10.1287/ited.1070.0005