The importance of designing proteins to improve their interactions, such as designing high affinity monoclonal antibodies, has become ever more apparent as of late. Computational Protein Design, or CPD, can cast such design problems as an optimization problem with the objective of maximizing K*, an approximation of binding affinity based on a computational protein model. We introduce AOBB-K*MAP, a new branch-and-bound algorithm over AND/OR search spaces for solving the K*MAP problem. In addition to formulating CPD as a graphical model for K* optimization and providing an new efficient algorithm, we also introduce a statically compiled heuristics for K*MAP not previously used in CPD. As AOBB-K*MAP is inspired by algorithms from the well studied task of Marginal MAP, in addition to the algorithm itself, this work provides a framework for continued adaptation of existing state-of-the-art mixed inference schemes over AND/OR search spaces to the problem of protein design.