Algorithms for mixed-integer optimization problems are based on the sequential construction of tractable relaxations of the discrete problem, until the relaxations are sufficiently tight to guarantee optimality of the resulting solution. For classical operational and logistics problems, which can be formulated as mixed-integer linear optimization problems, it is well-known that such relaxations should be polyhedral. Thus, there has been a sustained stream of research spanning several decades on constructing and exploiting linear relaxations. As a consequence, mixed-integer linear optimization problems deemed to be intractable 30 years old can be solved to optimality in seconds or minutes nowadays. Modern statistical and decision-making problems call for mixed-integer nonlinear optimization (MINLO) formulations, which inherently lead to non-polyhedral relaxations. There has been a substantial progress in extending and adapting techniques for both the mixed-integer linear optimization and continuous nonlinear literatures, but there may a fundamental limit on the effectiveness of such approaches as they fail to exploit the specific characteristics of MINLO problems. In this talk, we discuss recent progress in studying the fundamental structure of MINLO problems. In particular, we show that such problems have a hidden polyhedral substructure that captures the non-convexities associated with discrete variables. Thus, by exploiting this substructure, convexification theory and methods based on polyhedral theory can naturally be used study non-polyhedral sets. We also provide insights into how to design algorithms that tackle the ensuing relaxations.