A Reciprocity Between Tree Ensemble Optimization and Multilinear Optimization

• 成果类型: Article
• 署名作者: Kim, Jongeun; Richard, Jean-Philippe P.; Tawarmalani, Mohit
• 署名单位: University of Minnesota System; University of Minnesota Twin Cities; Purdue University System; Purdue University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0150
• 发表日期: 2025
• 关键词: programming formulation; CLASSIFICATION; relaxations; EXTENSIONS; polytope; strength

摘要

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.