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.

Funding: This work was supported by Division of Civil, Mechanical and Manufacturing Innovation [Grants 1727989, 1917323].

Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.0150.