  We study mixed-integer programming formulations for the piecewise linear
lower and upper bounds (in other words, piecewise linear relaxations) of
nonlinear functions that can be modeled by a new class of combinatorial
disjunctive constraints (CDCs), generalized $n$D-ordered CDCs. We first
introduce a general formulation technique to model piecewise linear lower and
upper bounds of univariate nonlinear functions concurrently so that it uses
fewer binary variables than modeling bounds separately. Next, we propose
logarithmically sized ideal non-extended formulations to model the piecewise
linear relaxations of univariate and higher-dimensional nonlinear functions
under the CDC and independent branching frameworks. We also perform
computational experiments for the approaches modeling the piecewise linear
relaxations of univariate nonlinear functions and show significant speed-ups of
our proposed formulations. Furthermore, we demonstrate that piecewise linear
relaxations can provide strong dual bounds of the original problems with less
computational time in order of magnitude.
