  In this paper, we develop new discrete relaxations for nonlinear expressions
in factorable programming. We utilize specialized convexification results as
well as composite relaxations to develop mixed-integer programming (MIP)
relaxations. Our relaxations rely on ideal formulations of convex hulls of
outer-functions over a combinatorial structure that captures local
inner-function structure. The resulting relaxations often require fewer
variables and are tighter than currently prevalent ones. Finally, we provide
computational evidence to demonstrate that our relaxations close approximately
60-70% of the gap relative to McCormick relaxations and significantly improves
the relaxations used in a state-of-the-art solver on various instances
involving polynomial functions.
