PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimization of Tree Ensembles

Velibor V. Mišić

arXiv:1705.10883v2math.OCcs.LGstat.ML

TL;DR

When tree-ensemble inputs are controllable, the decision problem is how to set them to maximize predicted outcomes. The paper formulates this as mixed-integer optimization and develops theory and scalable solution methods; real-data applications demonstrate near- or full-optimal solutions, including drug-design trade-offs and store-level pricing.

  • Problem

    Tree ensembles are often used with uncontrollable inputs, but the paper studies how to maximize predicted outcomes when inputs are decision variables.

    Source: §1 · pp. 1, 3

  • Method

    The paper formulates tree-ensemble prediction optimization as mixed-integer optimization, develops approximation bounds, and exploits structure through Benders decomposition and split-constraint generation.

    Source: §1 · p. 3, §8 · p. 25

  • Results

    The approach solves large-scale instances to near or full optimality and outperforms heuristic approaches, with drug-design and customized-pricing case studies.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The approach constructs drug-compound trade-offs between predicted performance and similarity to known compounds, and finds provably optimal store-level prices within seconds.

    Source: §1 · p. 3

    The approach assumes a fixed model for a one-time decision and assumes its predictions accurately represent outcomes, although predictions may not estimate causal effects.

    Source: §3.1 · p. 6

Abstract

from arXiv · show

Tree ensemble models such as random forests and boosted trees are among the most widely used and practically successful predictive models in applied machine learning and business analytics. Although such models have been used to make predictions based on exogenous, uncontrollable independent variables, they are increasingly being used to make predictions where the independent variables are controllable and are also decision variables. In this paper, we study the problem of tree ensemble optimization: given a tree ensemble that predicts some dependent variable using controllable independent variables, how should we set these variables so as to maximize the predicted value? We formulate the problem as a mixed-integer optimization problem. We theoretically examine the strength of our formulation, provide a hierarchy of approximate formulations with bounds on approximation quality and exploit the structure of the problem to develop two large-scale solution methods, one based on Benders decomposition and one based on iteratively generating tree split constraints. We test our methodology on real data sets, including two case studies in drug design and customized pricing, and show that our methodology can efficiently solve large-scale instances to near or full optimality, and outperforms solutions obtained by heuristic approaches. In our drug design case, we show how our approach can identify compounds that efficiently trade-off predicted performance and novelty with respect to existing, known compounds. In our customized pricing case, we show how our approach can efficiently determine optimal store-level prices under a random forest model that delivers excellent predictive accuracy.

1. Introduction

The paper asks how to maximize a tree ensemble’s prediction when its input variables are controllable decisions. It formulates this problem as mixed-integer optimization and develops theory, scalable methods, and applications in drug design and pricing.

1. Introduction

  • Tree ensemble optimization chooses controllable input variables to maximize the dependent variable predicted by a tree ensemble.The problem is practically relevant but challenging because tree ensembles are highly nonlinear and large-scale.Source: §1 · p. 2
  • The proposed mixed-integer optimization formulation handles discrete, categorical, and continuous numeric variables.The paper presents this as a new problem in machine learning and operations research.Source: §1 · p. 3
  • Theoretical results establish NP-hardness, a stronger relaxation than an alternate MIO, and depth-truncated approximations with upper and lower bounds.The upper bound improves with truncation depth; the lower bound depends on variability in predictions below the truncation depth.Source: §1 · p. 3
  • Two large-scale strategies exploit problem structure: Benders reformulation with constraint generation and lazy constraint generation with tree traversal to find violated constraints.The Benders subproblem can be solved efficiently.Source: §1 · p. 3
  • The methods solve small-to-medium instances to full optimality within minutes, outperform a simple local-search heuristic, and can drastically reduce solution time.The full formulation is reported to have stronger relaxation bounds and shorter solution times than the alternate formulation.Source: §1 · p. 3
  • In drug design, the approach finds large-scale solutions to full or near optimality within two hours and constructs performance–similarity trade-off frontiers; in pricing, it finds provably optimal store-level prices within seconds.The pricing random forest also improves out-of-sample prediction accuracy over two state-of-the-art hierarchical Bayesian models.Source: §1 · p. 3

2. Literature review

The review situates tree ensembles among successful predictive models and distinguishes optimizing a fixed ensemble from prior work on estimating predictive models or optimizing decisions through other model formulations.

2. Literature review

  • Random forests and boosted trees are prominent ensembles, motivated by improved accuracy over individual trees and supported by strong practical performance.Random forests achieved best or near-best results across benchmark data sets in one systematic comparison.Source: §2 · p. 4
  • Prior operations-research work uses predictive models to optimize decisions, including pricing and assortment optimization.Examples include demand-based price selection and revenue optimization under a ranking-based choice model.Source: §2 · p. 4
  • Ferreira et al. (2015) combine random-forest demand predictions with an MIO for fashion-sale pricing, but use precomputed predictions as objective coefficients rather than modeling tree predictions explicitly.That approach requires enumerating possible feature combinations, making extension difficult when there are many independent variables.Source: §2 · p. 4
  • The paper’s MIO explicitly models each tree’s structure, distinguishing its approach from Ferreira et al. (2015) and introducing tree-ensemble prediction optimization as a problem.The authors state that the approach is difficult to extend to many variables when all value combinations must be enumerated.Source: §2 · p. 5
  • Bertsimas and Mišić (2019) provide a related special case and Benders-cut results generalized here, while their focus is product-line decisions and this paper targets tree ensembles broadly.Other MIO work focuses on estimating trees or statistical models; this paper instead optimizes decisions under a fixed tree ensemble.Source: §2 · p. 5

3. Model

The model maximizes a fixed tree ensemble’s prediction over controllable inputs by encoding input values and leaf assignments in an MIO. The paper establishes theoretical limits and formulation strength, then develops depth-truncated approximations with quality bounds.

3.1. Background

  • The tree-ensemble optimization problem maximizes the ensemble prediction over input variables, and is NP-hard; the analysis assumes a fixed model and a one-time decision.The paper also assumes the prediction model accurately represents outcomes under the chosen decision, while noting that predictions need not estimate causal effects.Source: §3.1 · p. 6

3.2. Optimization model

  • The MIO encodes categorical choices and numeric positions relative to unique split points, alongside variables assigning the observation to each tree’s leaf.Numeric values themselves are not represented because tree-ensemble predictions are piecewise constant; the model needs only the relation to split points.Source: §3.2 · pp. 6–8

3.3. Theoretical properties

  • The proposed formulation is stronger than an alternate MIO obtained by standard linearization of a binary polynomial formulation.The paper states that stronger formulations are generally faster to solve and reports a substantial relaxation-bound difference in computational experiments.Source: §3.3 · p. 9

3.4. Depth d approximation

  • Depth truncation reduces the number of split constraints by representing each tree only through a selected depth, and its relaxed objective is an upper bound that tightens as depth increases.The hierarchy removes constraints while retaining decision variables; the motivation is the large constraint count in deep ensembles.Source: §3.4 · pp. 9–10
  • For nonnegative tree weights, a depth-truncated solution has a computable lower bound on its full-depth objective, with a gap bounded by the weighted sum of tree-specific prediction-error bounds.The bounds let decision makers trade problem complexity against guaranteed approximation quality; the lower bound can be conservative at small depths.Source: §3.4 · pp. 10–11

4. Solution methods

For large instances, the paper presents Benders decomposition and iterative split-constraint generation as alternatives to solving the full MIO directly. Both exploit tree structure to check or add constraints efficiently.

4.1. Benders decomposition

  • Benders decomposition separates each tree’s variables from the others, linking their subproblems only through the shared decision variables x.The paper derives an efficient structure for checking violated Benders constraints without invoking a linear optimization solver.Source: §4.1 · pp. 11, 13

4. Solution methods

  • Both constraint-generation approaches are limited to candidate integer solutions and cannot generate cuts or separate constraints for fractional solutions.Extending the split-constraint procedure to fractional solutions is identified as future research.Source: §4.1 · p. 13, §4.2 · pp. 14–15

4.2. Split constraint generation

  • The split-constraint method starts with a subset of split constraints, adds violated constraints, and repeats until the current solution is optimal.For each tree, checking only the splits traversed by the observation encoded by x suffices; violations can therefore be found by traversing the tree.Source: §4.2 · p. 14
  • O(dmax) checks per tree replace a potentially O(2^dmax) set of split constraints in the constraint-generation procedure.The procedure checks at most dmax left/right split constraints for a tree, even when a complete tree has exponentially many split constraints.Source: §4.2 · p. 14

5. Computational experiments

The experiments evaluate the MIO formulation and solution methods on real-data tree ensembles, including cases where the variables may not actually be controllable. Depth approximations and tailored solution methods can yield near-optimal solutions more quickly, while the full formulation outperforms the standard linearization and local-search approaches on reported measures.

5.1. Background

  • The experiments use random forests estimated from real datasets, although some datasets’ independent variables may not be controllable in practice.The authors retain these datasets because they provide real tree-ensemble models for evaluating the optimization methodology.Source: §5.1 · p. 15, Table 1 · p. 16

5.2. Full MIO formulation experiments

  • In 2 of 20 cases, the standard-linearization MIO reached full optimality within 30 minutes; its timed-out gaps ranged from 50% to over 100%, while the proposed formulation solved the largest case to optimality in about 20 minutes.The proposed formulation also had a tighter relaxation bound; its integrality gap was a few percent in most cases.Source: §5.2 · p. 17, Table 2 · p. 18, Table 3 · p. 18
  • Local search was often suboptimal even from ten starting points, whereas the MIO formulation guarantees a globally optimal solution, sometimes justifying its additional runtime.Local-search time was generally lower, but not substantially so in every case.Source: §5.2 · pp. 16–17

5.3. Depth d approximation experiments

  • For T=100, the depth approximation produced essentially optimal solutions at depth 15 for winequalityred (maximum depth 26) and depth 9 for concrete (maximum depth 24).As depth increased, the upper bound decreased while the lower bound and actual objective increased; solution time seemed to plateau after a certain depth.Source: §5.3 · pp. 17, 19

5.4. Solution method experiments

  • Over 95% less solution time in the concrete case: split generation took about 32 seconds and Benders about 37 seconds, versus about 800 seconds for direct solution, all to full optimality.Across instances, both tailored methods dramatically reduced solution time; Benders was faster in some cases and split generation in others.Source: Table 4 · p. 20, §5.4 · p. 20

6. Case study 1: drug design

The drug-design case optimizes random-forest-predicted molecular activity across large molecular datasets, then examines how predicted performance trades off against similarity to existing compounds. Split generation solves more unconstrained instances to optimality than direct optimization, while proximity constraints yield high-performing, less-similar solutions.

6.1. Background

  • The experiments seek molecules maximizing random-forest-predicted activity across 15 datasets, with roughly 4,000 to just under 10,000 independent variables per dataset.The datasets contain about 1,500 to just over 37,000 observations; the study uses ranger and limits each forest to 100 trees.Source: §6.1 · pp. 20–21, §6.2 · p. 21

6.2. Unconstrained optimization results

  • Split generation solves 10 of 15 data sets to full optimality within one hour and another three within the next hour, improving on direct optimization.Direct optimization solves nine within one hour and one more within the next hour; the largest reported improvement is data set 10, from over an hour to just over 20 minutes.Source: §6.2 · p. 22, Table 6 · p. 23
  • Benders has substantially higher optimality gaps after two hours than direct optimization and split generation, and solves only two instances to full optimality.Split generation solves both of those instances to full optimality more quickly.Source: §6.2 · p. 22
  • Local search is highly suboptimal against the best split-generation solution, with optimality gaps from about 5% on data set 8 to 26% on data set 13.The ten repetitions can also take longer than split generation in some cases.Source: §6.2 · p. 22

6.3. Controlling proximity

  • At maximum proximity 0.01, data set 4’s relative objective value falls by only about 7%, while MIO solutions dominate local search in both proximity and objective value.For data sets 4 and 7, local search’s best relative objectives are roughly 94% and 90%, respectively; six of 112 frontier points did not solve to full optimality, with a maximum gap of about 0.12%.Source: §6.3 · p. 24, Figure 6 · p. 25

7. Case study 2: customized pricing

The customized-pricing case estimates random-forest profit models for 11 orange-juice products and optimizes prices for each store. The resulting prices perform well under hierarchical Bayesian models and are less extreme, while the random-forest models achieve higher out-of-sample R2.

7. Case study 2: customized pricing

  • Random-forest-optimal prices perform well under hierarchical Bayesian models and set fewer products to their highest or lowest allowable prices across the store chain.The random-forest profit models for 11 orange-juice products are optimized in seconds and achieve significantly higher out-of-sample R2 than the hierarchical Bayesian models.Source: §7 · p. 25

8. Conclusion

The paper formulates tree-ensemble optimization as mixed-integer optimization and develops theory and solution methods for it. Real-data case studies demonstrate its use in drug design and customized pricing.

8. Conclusion

  • The mixed-integer formulation models each tree’s action and supports Benders decomposition and split-constraint generation, alongside bounded-quality approximations based on depth truncation.The authors report that the formulation is stronger than a general alternative formulation and demonstrate the approach in drug-design and customized-pricing case studies.Source: §8 · p. 25

EC.1. Proofs

The auxiliary proofs characterize sets of leaves associated with a chosen leaf and establish disjointness properties for sets formed from tree splits.

EC.1. Proofs

  • For a chosen leaf, the leaves on the wrong side of its path splits cover every other leaf in the tree.The wrong-side sets are formed from right(s) for left-path splits and left(s) for right-path splits.Source: EC.1.1. Auxiliary results · p. 29
  • The constructed collection of B sets is pairwise disjoint, as established in the auxiliary proof.The proof orders splits by depth and uses the nested sequence of A sets to establish disjointness.Source: EC.1.1. Auxiliary results · p. 30
  • A corresponding lemma for splits is stated for a given tree and split, with its proof omitted as following similar lines to the earlier lemma.The sets formed from wrong-side leaves for the split’s left and right ancestor sets are also pairwise disjoint.Source: EC.1.1. Auxiliary results · pp. 29–30

EC.1.2. Proof of Proposition 1

The proof reduces minimum vertex cover to tree ensemble optimization, establishing NP-hardness. It also compares relaxations of the formulations and shows how depth-restricted feasible regions relate to the full-depth model.

EC.1.2. Proof of Proposition 1

  • The tree ensemble optimization problem is NP-hard by reduction from minimum vertex cover.The constructed objective is equivalent to minimizing the size of a feasible vertex cover.Source: EC.1.2. Proof of Proposition 1 · p. 32

EC.1.3. Proof of Proposition 2

  • The proof shows that an optimal solution to the relaxation of (2) is feasible for the relaxation of (4), yielding an objective bound between their relaxed optima.It verifies the additional constraints of (4) using constraints in (2).Source: EC.1.3. Proof of Proposition 2 · p. 32

EC.1.4. Proof of Proposition 3

  • At depth d, formulation (5) has a feasible region containing the depth-(d + 1) region; at maximum tree depth, it coincides with the MIO formulation.The nested regions establish the stated sequence of objective inequalities.Source: EC.1.4. Proof of Proposition 3 · p. 33

EC.1.5. Proof of Theorem 1

The proof bounds the objective gap between a depth-restricted solution and its full-depth counterpart. It does so by tracing the node reached under the restricted solution and bounding prediction differences using ranges of leaf predictions.

EC.1.5. Proof of Theorem 1

  • A depth-d solution is mapped down each tree to a leaf or depth-d split node by following the branches selected by the controllable variables.The stopping node is used to compare the depth-restricted tree prediction with its full-depth counterpart.Source: EC.1.5. Proof of Theorem 1 · p. 33
  • The proof bounds the objective gap by summing tree-level prediction-difference bounds, then combines that bound with feasibility and the depth-relaxation result.For a split node, the bound uses the range of predictions within its left and right subtrees; the proof also handles leaf and unknown-node cases.Source: EC.1.5. Proof of Theorem 1 · p. 35

EC.1.6. Proof of Proposition 4

For fixed controllable variables, the proof constructs a feasible tree-leaf assignment by selecting the leaf reached by those variables. It establishes that this assignment is the only feasible solution and therefore is optimal.

EC.1.6. Proof of Proposition 4

  • The proof verifies feasibility by showing the selected leaf assignment satisfies the left and right split constraints.The construction uses the branches selected by the variables to show incompatible leaves receive zero.Source: EC.1.6. Proof of Proposition 4 · p. 36
  • The constructed assignment puts value 1 on the selected leaf and 0 on every other leaf, and is the unique feasible solution of (8).The split constraints force all other leaves to zero, while the leaf-sum constraint fixes the selected leaf at one.Source: EC.1.6. Proof of Proposition 4 · p. 37

EC.1.7. Proof of Proposition 5

The proof establishes optimality of a constructed dual solution for the tree-level linear optimization problem. It also shows that enforcing split constraints on the relevant subsets suffices to recover the full formulation’s leaf assignment.

EC.1.7. Proof of Proposition 5

  • The constructed dual solution is feasible and matches the primal optimum, so weak linear-optimization duality establishes its optimality.The proof checks dual feasibility leaf by leaf and verifies equality of the primal and dual objectives.Source: EC.1.7. Proof of Proposition 5 · p. 38

EC.1.8. Proof of Proposition 6

  • Constraints on the relevant subsets of splits force all nonselected leaf variables to zero and the selected leaf variable to one, recovering Proposition 4’s assignment.The proof uses nonnegativity, the split-constraint hypothesis, and the leaf-sum constraint.Source: EC.1.8. Proof of Proposition 6 · pp. 38–39

EC.2. Local search procedure

The local search works over finite domains built from the ensemble’s split points. It starts from a random solution and returns a locally optimal solution.

EC.2. Local search procedure

EC.3. Case study 2: customized pricing

The customized-pricing case compares random forests with hierarchical Bayesian demand models on orange-juice sales data, then optimizes store-level prices. Random forests improve out-of-sample profit prediction and yield quickly computed, provably optimal prices that are not extreme and perform robustly under the alternative models.

EC.3.1. Background

  • For the orange-juice data, each observation is a store-week; the dataset covers 83 stores, 121 weeks, 11 brands, and store-neighborhood covariates.Source: EC.3.1. Background · p. 41

EC.3.2. Models

  • The RF model directly predicts brand-level profit, while the two HB specifications model log sales as linear in log prices or actual prices.Predicting profit keeps the objective directly usable in the tree-ensemble formulation; optimizing price times predicted sales would require a harder modified model.Source: EC.3.2. Models · pp. 41–42

EC.3.3. Predictive accuracy results

  • Removing cross-brand promotions improves HB-LogLog R2 by 0.04–0.68 (average 0.15) and HB-SemiLog R2 by 0.03–0.85 (average 0.17).In contrast, RF-Own has slightly lower R2 than RF; Table EC.2 covers the second profit-prediction task.Source: EC.3.3. Predictive accuracy results · p. 44, Table EC.2 · p. 45
  • RF with 500 trees raises brand 8’s R2 from the HB models’ best 0.45 to 0.67, an absolute improvement of 0.25.Across brands, RF improves over each brand’s best HB model by 0.05 to 0.48; Table EC.1 reports first-task results averaged over ten random splits.Source: EC.3.3. Predictive accuracy results · p. 44, Table EC.1 · p. 44

EC.3.4. Optimization results

  • The pricing experiment optimizes prices in $0.05, $0.10, or $0.20 increments between each brand’s observed 25th and 75th price percentiles, with promotions fixed at zero.Source: EC.3.4. Optimization results · p. 45
  • RF pricing takes about 11.4 seconds per store at δ = 0.05 and finishes every instance within 30 seconds; its solutions are provably optimal.The HB optimization problems take no more than five seconds, but use local search without a general optimality guarantee; Table EC.4 reports computation times.Source: EC.3.4. Optimization results · pp. 46–47, Table EC.4 · p. 47
  • Across the model comparisons, RF prices are about as robust as HB prices; at δ = 0.20, cross-model profit retention is 88.1% and 87.6% in the reported directions.Table EC.5 presents the multi-model comparison; HB-LogLog-Own and HB-SemiLog-Own prices are mostly at allowable extremes, while RF prices span more interior values (Figure EC.2).Source: EC.3.4. Optimization results · pp. 47–48, Table EC.5 · p. 48, Figure EC.2 · p. 49
  • The case study concludes that RF can produce non-extreme prices quickly to provable optimality while retaining high predicted profits under HB models.Source: EC.3.4. Optimization results · p. 48

Related papers

Loading 1705.10883v2…