A Reciprocity Between Tree Ensemble Optimization and Multilinear Optimization

Capitalizing on the relationships between tree ensembles and multilinear functions Tree ensembles are machine learning models used for regression and classification that combine the predictions of multiple trees. When such trained models are embedded into optimization models in the form of constraints or objectives, a key question is that of deriving best integer programming formulations for them. In “A Reciprocity Between Tree Ensemble Optimization and Multilinear Optimization,” J. Kim, J.-P. Richard, and M. Tawarmalani establish a polynomial-size reduction between the optimization of functions expressed as tree ensembles and the optimization of multilinear functions over a Cartesian product of simplices. This bidirectional reduction permits the derivation of new stronger formulations for tree ensemble optimization problems, including ideal formulations for single trees. It also provides a new framework for the construction of polynomially-sized convex hull descriptions for certain multilinear sets, which permits the generalization of many results from the literature.