Linear Model Decision Trees

There are multiple formulations for representing linear model decision trees.

Please see the following reference:

Ammari et al. (2023) Linear Model Decision Trees as Surrogates in Optimization of Engineering Applications. Computers & Chemical Engineering

We utilize the following common nomenclature in the formulations:

\[\begin{split}\begin{align*} L &:= \text{Set of leaves} \\ z_{\ell} &:= \text{Binary variable indicating which leaf is selected} \\ x &:= \text{Vector of input variables to the decision tree} \\ d &:= \text{Output variable from the decision tree} \\ a_{\ell} &:= \text{Vector of slopes learned by the tree for leaf } \ell \in L\\ b_{\ell} &:= \text{Bias term learned by the tree for leaf } \ell \in L\\ \end{align*}\end{split}\]

Linear Tree Definition

class omlt.linear_tree.lt_definition.LinearTreeDefinition(lt_regressor, scaling_object=None, scaled_input_bounds=None, unscaled_input_bounds=None)[source]

Bases: object

Class to represent a linear tree model trained in the linear-tree package

__model

Linear Tree Model trained in linear-tree

Type:: linear-tree model

__splits

Dict containing split node information

Type:: dict

__leaves

Dict containing leaf node information

Type:: dict

__thresholds

Dict containing splitting threshold information

Type:: dict

__scaling_object

Scaling object to ensure scaled data match units of broader optimization problem

Type:: scaling object

__scaled_input_bounds

Dict containing scaled input bounds

Type:: dict

__unscaled_input_bounds

Dict containing unscaled input bounds

Type:: dict

References

linear-tree : https://github.com/cerlymarco/linear-tree

property leaves: Returns dict containing leaf information

property n_inputs: Returns number of inputs to the linear tree

property n_outputs: Returns number of outputs to the linear tree

property scaled_input_bounds: Returns dict containing scaled input bounds

property scaling_object: Returns scaling object

property splits: Returns dict containing split information

property thresholds: Returns dict containing threshold information

Linear Tree Formulations

class omlt.linear_tree.lt_formulation.LinearTreeGDPFormulation(lt_definition, transformation='bigm')[source]

Bases: _PyomoFormulation

Class to add a Linear Tree GDP formulation to OmltBlock. We use Pyomo.GDP to create the disjuncts and disjunctions and then apply a transformation to convert to a mixed-integer programming representation.

\[\begin{split}\begin{align*} & \underset{\ell \in L}{\bigvee} \left[ \begin{gathered} Z_{\ell} \\ \underline{x}_{\ell} \leq x \leq \overline{x}_{\ell} \\ d = a_{\ell}^T x + b_{\ell} \end{gathered} \right] \\ & \texttt{exactly_one} \{ Z_{\ell} : \ell \in L \} \\ & x^L \leq x \leq x^U \\ & x \in \mathbb{R}^n \\ & Z_{\ell} \in \{ \texttt{True, False} \} \quad \forall \ \ell \in L \end{align*}\end{split}\]

Additional nomenclature for this formulation is as follows:

\[\begin{split}\begin{align*} Z_{\ell} &:= \text{Boolean variable indicating which leaf is selected} \\ \overline{x}_{\ell} &:= \text{Vector of upper bounds for leaf } \ell \in L \\ \underline{x}_{\ell} &:= \text{Vector of lower bounds for leaf } \ell \in L \\ x^U &:= \text{Vector of global upper bounds} \\ x^L &:= \text{Vector of global lower bounds} \\ \end{align*}\end{split}\]

Inherited from _PyomoFormulation Class

model_definition: LinearTreeDefinition object

transformation: choose which transformation to apply. The supported transformations are bigm, mbigm, hull, and custom.

References

Ammari et al. (2023) Linear Model Decision Trees as Surrogates in Optimization of Engineering Applications. Computers & Chemical Engineering
Chen et al. (2022) Pyomo.GDP: An ecosystem for logic based modeling and optimization development. Optimization and Engineering, 23:607–642

property input_indexes: The indexes of the formulation inputs.

property output_indexes: The indexes of the formulation output.

class omlt.linear_tree.lt_formulation.LinearTreeHybridBigMFormulation(lt_definition)[source]

Bases: _PyomoFormulation

Class to add a Linear Tree Hybrid Big-M formulation to OmltBlock.

\[\begin{split}\begin{align*} & d = \sum_{\ell \in L} (a_{\ell}^T x + b_{\ell})z_{\ell} \\ & x_i \leq \sum_{\ell \in L} \overline{x}_{i,\ell} z_{\ell} && \forall i \in [n] \\ & x_i \geq \sum_{\ell \in L} \underline{x}_{i,\ell} z_{\ell} && \forall i \in [n] \\ & \sum_{\ell \in L} z_{\ell} = 1 \end{align*}\end{split}\]

Where the following additional nomenclature is defined:

\[\begin{split}\begin{align*} [n] &:= \text{the integer set of variables that the tree splits on (e.g. [n] = {1, 2, ... , n})} \\ \overline{x}_{\ell} &:= \text{Vector of upper bounds for leaf } \ell \in L \\ \underline{x}_{\ell} &:= \text{Vector of lower bounds for leaf } \ell \in L \\ \end{align*}\end{split}\]

Inherited from _PyomoFormulation Class

model_definition: LinearTreeDefinition object

property input_indexes: The indexes of the formulation inputs.

property output_indexes: The indexes of the formulation output.