A Reciprocity Between Tree Ensemble Optimization and Multilinear Optimization

In this paper, we establish a low-degree polynomially-sized reduction between tree ensemble optimization and optimization of multilinear functions over a Cartesian product of simplices. We use this insight to derive new formulations for tree ensemble optimization problems and to obtain new convex hull results for multilinear polytopes. A computational experiment on multicommodity transportation problems with costs modeled using tree ensembles shows the practical advantage of our formulation relative to existing formulations of tree ensembles and other piecewise-linear modeling techniques.