The recent explosion of capabilities to fabricate nanostructured materials to atomic precision has opened many avenues for technological advances but has also posed unique questions regarding the identification of structures that should serve as targets for fabrication. One material class for which identifying such targets is challenging are transition-metal crystalline surfaces, which enjoy wide application in heterogeneous catalysis. The high combinatorial complexity with which patterns can form on such surfaces calls for a rigorous design approach. In this article, we formalize the identification of the optimal periodic pattern of a metallic surface as an optimization problem, which can be addressed via established algorithms. We conduct extensive computational studies involving an array of crystallographic lattices and structure-function relationships, validating patterns that were previously known to be promising but also revealing a number of new, nonintuitive designs. (C) 2016 American Institute of Chemical Engineers