PIECEWISE POLYHEDRAL RELAXATIONS OF MULTILINEAR OPTIMIZATION

In this paper, we consider piecewise polyhedral relaxations (PPRs) of multilinear optimization problems over axis-parallel hyperrectangular 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 (nonregular) hyperrectangular partitions. We also perform experiments that show that, for a variant of tree ensemble optimization, our formulations based on nonregular partitions outperform an existing formulation for piecewise linear functions commonly used in the literature and also outperform by an order of magnitude formulations over regular partitions.