• Proposes DTE, a new method to improve pre-trained decision trees through post-training optimization. • DTE applies to data sets with continuous or continuous and discrete features. • The proposed formulation allows the decision maker to optimize the accuracy or recall of the decision tree. • DTE is feasible in practice, as it delivers improvements even when computation time is limited. Decision trees are off-the-shelf machine learning models widely used for classification and regression tasks in medical, logistics, financial, and other critical areas where interpretability is a key factor. They can efficiently handle numerical and categorical variables, making them a versatile choice for various applications. However, traditional decision-tree training methods are based on greedy heuristics, which cannot provide guarantees regarding whether further improvements could be achieved. We propose Decision Tree Enhancer (DTE), which employs optimization as a post-training step to improve previously trained decision trees. Moreover, the proposed method precludes the need for a pre-processing step for continuous features such as discretization or bucketization , and can be applied regardless of the model used to first train the decision tree. Lastly, DTE’s mathematical programming formulation enables, for example, the consideration of recall thresholds and class prioritization. Tested on 63 classification datasets from the UCI Machine Learning Repository, using tree depths from 1 to 5, four time limits (1, 5, 10, and 30 seconds), and 5 randomized train-test splits cross-validation, the proposed post-training step demonstrated superior performance over CART (Classification And Regression Tree), for both in- and out-of-sample data. With a 30-second time limit, DTE was able to improve the weighted recall in 83.2% of the datasets with an average improvement of 9.0% in training and 5.0% in testing.

Abstract This paper presents a novel technique to compute Lagrangian bounds for nonconvex mixed-integer quadratically constrained quadratic programming problems presenting a separable structure (i.e., a separable problems) such as those arising in deterministic equivalent representations of two-stage stochastic programming problems. In general, the nonconvex nature of these models still poses a challenge to the available solvers, which do not consistently perform well for larger-scale instances. Therefore, we propose an appealing alternative algorithm that allows for overcoming computational performance issues. Our novel technique, named the p-Lagrangian decomposition, is a decomposition method that combines Lagrangian decomposition with mixed-integer programming-based relaxations. These relaxations are obtained using the reformulated normalised multiparametric disaggregation technique and can be made arbitrarily precise by means of a precision parameter p. We provide a technical analysis showing the convergent behaviour of the approach as the approximation is made increasingly precise. We observe that the proposed method presents significant reductions in computational time when compared with a previously proposed techniques in the literature and the direct employment of a commercial solver. Moreover, our computational experiments show that the employment of a simple heuristic can recover solutions with small duality gaps.

We propose methods for improving the relaxations obtained by the normalized multiparametric disaggregation technique (NMDT). These relaxations constitute a key component for some methods for solving nonconvex mixed-integer quadratically constrained quadratic programming (MIQCQP) problems. It is shown that these relaxations can be more efficiently formulated by significantly reducing the number of auxiliary variables (in particular, binary variables) and constraints. Moreover, a novel algorithm for solving MIQCQP problems is proposed. It can be applied using either its original NMDT or the proposed reformulation. Computational experiments are performed using both benchmark instances from the literature and randomly generated instances. The numerical results suggest that the proposed techniques can improve the quality of the relaxations.