Mixed Integer Linear Programming-Based Methods for the Optimal Time-Constrained Cost-Sensitive Decision Tree

Cost management and completion timelines are common classification problem requirements. For instance, a blood test requires human and equipment resources, costs money, and must be done quickly. To avoid major patient risks, medical diagnosis should minimize positive-to-negative misclassification. There has been extensive research on how to build a decision tree from training data that minimizes misclassification and test costs, but not on how to design an optimal decision tree with time constraints. A mixed-integer programming is implemented to create an optimal time-constrained cost-sensitive decision tree in this study. We adapt several existing approaches in the literature with time constraints, misclassification cost, and feature selection cost, and introduce new mathematical models designed for these problems. Our experiments compare all methods and examine how time and cost constraints affect optimal solution identification and demonstration.