AbstractTo incorporate protein polarization effects within a protein combinatorial optimization framework, we decompose the polarizable force field AMOEBA into low order terms. Including terms up to the third‐order provides a fair approximation to the full energy while maintaining tractability. We represent the polarizable packing problem for protein G as a hypergraph and solve for optimal rotamers with the FASTER combinatorial optimization algorithm. These approximate energy models can be improved to high accuracy [root mean square deviation (rmsd) < 1 kJ mol−1] via ridge regression. The resulting trained approximations are used to efficiently identify new, low‐energy solutions. The approach is general and should allow combinatorial optimization of other many‐body problems. © 2011 Wiley Periodicals, Inc. J Comput Chem, 2011