  Scientific computing has experienced a surge empowered by advancements in
technologies such as neural networks. However, certain important tasks are less
amenable to these technologies, benefiting from innovations to traditional
inference schemes. One such task is protein re-design. Recently a new re-design
algorithm, AOBB-K*, was introduced and was competitive with state-of-the-art
BBK* on small protein re-design problems. However, AOBB-K* did not scale well.
In this work we focus on scaling up AOBB-K* and introduce three new versions:
AOBB-K*-b (boosted), AOBB-K*-DH (with dynamic heuristics), and AOBB-K*-UFO
(with underflow optimization) that significantly enhance scalability.
