In this paper, we consider piecewise polyhedral relaxations (PPRs) of multilinear optimization problems over axis-parallel hyper-rectangular partitions of their domain. We improve formulations for PPRs by linking components that are commonly modeled independently in the literature. Numerical experiments with ALPINE, an open-source software for global optimization that relies on piecewise approximations of functions, show that the resulting formulations speed-up the solver by an order of magnitude when compared to its default settings. If given the same time, the new formulation can solve more than twice as many instances from our test-set. Most results on piecewise functions in the literature assume that the partition is regular. Regular partitions arise when the domain of each individual input variable is divided into nonoverlapping intervals and when the partition of the overall domain is composed of all Cartesian products of these intervals. We provide the first locally ideal formulation for general (non-regular) hyper-rectangular partitions. We also perform experiments that show that, for a variant of tree ensemble optimization problems, a formulation based on non-regular partitions outperforms that over regular ones by an order of magnitude.
Article
View Piecewise Polyhedral Relaxations of Multilinear Optimization