In the pursuit of employing interpretable and performant Machine Learning models, Decision Trees has become a staple in many industries while being able to produce near-optimal results. With computational power becoming more accessible, there has been increasing progress in constructing Optimal Decision Trees. It guarantees optimal solutions with respect to different metrics within a given size limit on training data while requiring a smaller number of nodes and becoming more viable to compute on real-world data. However, non-linear metrics, which are very effective when evaluating trees on imbalanced datasets, still represent a challenge regarding runtime performance and scalability. Previous approaches generate the Pareto Front of the set of possible solutions, an expensive operation in computing the optimal tree. To address this gap, we introduce a novel merging algorithm of two Pareto Fronts using convex hulls, offering better pruning and leading to an increase in scalability. The experiments show a significant improvement in runtime of almost 10\% on bigger datasets and higher-depth trees using the F1-score metric, with the potential to be applied to other convex metrics.

This paper looks at the different parts of the Critical Path and Resource Utilization (CPRU) heuristic for use in the Resource Constraint Project Scheduling Problem, with variable resources (RCPSP-t programming problem). RCPSP-t has many real-world instances such as in hospitals or manufacturing. Optimizing the solution generation for these instances may improve the efficiency of these industries. CPRU was split into parts and different versions were compared against VSIDS a more modern heuristic to determine if problem-specific heuristics perform better than generally good ones. A new adaptation of CPRU that adapts the research utilisation score by calculating the fraction used based on the amount of resources available given scheduled activities instead of looking at the resources of the problem instance. From the results, we concluded that CPRU may perform better for large instances of RCPSP- t compared to VSIDS in terms of generating good schedules within a few iterations. We also found that CPRU generates better schedules given a small time limit. We did not find evidence that the CPRU adaptation improved performance compared to CPRU in terms of schedule and time limits.

This paper introduces a new approach to the Preemptive Resource Constrained Project Scheduling Problem with setup times. The method makes use of a Constraint Optimization Problem solver, which has been modified to use priority-rule-based heuristics in its variable and value selection procedures. An alternative implementation which uses a combination of a priority-rule heuristic and a domain-independent solver heuristic has also been investigated. Both methods were tested on four well-known problem sets against a problem-independent solver configuration. Experimental results show a significant reduction in the time needed to find optimal solutions for the new methods.

Decision trees are valued for their ability to logically and transparently classify data. While heuristic methods to compute such trees are efficient, they often compromise on accuracy, prompting interest in Optimal Decision Trees (ODTs), which have the best misclassification score for a given tree size limit and training dataset. The dynamic programming (DP) approach for ODTs has shown improvements over alternatives such as mixed-integer or constraint programming. That being said, it requires further improvements to handle exponential runtime scaling with the depth of the tree and the number of features of the dataset. Leveraging modern hardware, such as multiple CPU cores, offers a promising solution to improve efficiency. This paper proposes a multithreading method for DP ODTs which we apply to STreeD specifically. We introduce a shared memory model and determine which components of the original program can be made local to the threads. We investigate whether it is more efficient to start multithreading at the root of the search tree than near its leaf nodes. We find the former to be superior, resulting in faster runtimes and less shared resource access. Empirical evaluations against the state of the art demonstrate better runtimes, particularly beneficial for large datasets. Finally, thread scaling analyses reveal substantial speed-ups, exceeding 2.5 times with four threads, highlighting our approach's effectiveness for computationally-intensive tasks.

Survival analysis is a branch of statistics concerned with studying and estimating the expected time duration until some event, such as biological death, occurs. Survival distributions are fitted based on historical data, where some instances are censored, meaning that the actual time of the event is not known precisely. Survival trees extend on the classical statistical methods developed and can capture complex non-linear relations between the variables by recursively splitting the instances by generated rules and fitting a different survival distribution in each leaf. Moreover, decision trees are desirable models due to their interpretable nature. We extend existing optimal survival tree methods by considering Cox Proportional Hazard models in each leaf node, which allows us to find more complex yet interpretable relationships than existing methods. The experiments show that our model outperforms state-of-the-art methods for creating survival trees, SurTree, OST, and CTree, especially in determining the relative risks between out-of-sample observations while generating significantly smaller trees.

The Algorithm Selection Problem (ASP) presents a significant challenge in numerous industries, requiring optimal solutions for complex computational problems. Traditional approaches to solving ASP often rely on complex, black-box models like random forests, which are effective but lack transparency, and they often fail to balance performance with interpretability. This paper investigates the performance-interpretability trade-off for the ASP, specifically focused on Optimal Decision Trees (ODTs) as recent innovations have made the use of ODTs more viable. We compare ODTs against 4 other tree-based models, using 11 different datasets. We show there is no apparent tradeoff between performance and interpretability for ODTs which have been trained using an instance cost-sensitive approach, as they achieve comparable performance to a Random Forest Regressor while maintaining interpretability through multiple orders of magnitude fewer leaf nodes.

The Multi-Mode Resource Constraint Scheduling Problem is an NP-hard optimization problem. It arises in various industries such as construction engineering, transportation, and software development. This paper explores the integration of an adaptation of the Longest Processing Time heuristic to initialize the Variable State Independent Decaying Sum for the MRCPSP. This adaptation prioritizes tasks with a longer duration in all possible modes. Experimental evaluation demonstrates a 10% faster average computation time compared to default VSIDS, and the average deviation to the optimal solution is improved from 0.080% to 0.050%. These two findings combined show a minor improvement in using the LPT to initialize VSIDS values for the MRCPSP. Using the LPT also to initialize the default increment parameter, did not seem to yield any positive results.

This paper investigates the inclusion of domain-specific variable selection heuristics
in Constraint Programming (CP) solvers for the Prize-Collecting Job Sequencing
with One Common and Multiple Secondary Resources (PC-JSOCMSR) problem. We
propose two variable selection heuristics: a greedy variable selection method based on
densities, Highest Density First (HDF), and a modified Variable State Independent
Decaying Sum (VSIDS) initialized with job densities, referred to as VSIDS + Density.
Experimental results on benchmark instance sets reveal that the proposed heuristics
do not outperform the baseline VSIDS heuristic. Overall, they lead to higher conflict
counts and slower convergence. These findings highlight the robustness of generalpurpose
heuristics like VSIDS in diverse problem instances. Future research should
explore other domain-specific heuristics, as the current experiment demonstrates that
the proposed heuristics do not improve performance.

Constraint programming solvers provide a generalizable approach to finding solutions for optimization problems. However, when comparing the performance of constraint programming solvers to the performance of a heuristic solver for an optimization problem such as cluster editing, the heuristic solver is able to find near-optimal and optimal solutions much faster. The goal of this research is to understand how the behaviour of such a heuristic solver can assist the performance of constraint programming solvers in optimization problems. In order to achieve this, first Chuffed, a state-of-the-art constraint programming solver was combined with a heuristic approach to cluster editing, with the goal of emulating the performance of the heuristic algorithm, in particular, being able to find near-optimal solutions faster. Continuing, the goal was to generalize the behaviour observed by the modified solver, by emulating the performance observed without the need for the specialized heuristic solver. The generalized approach is tested on a wide variety of different tests. An approach to value selection was developed that performs lookahead propagations for the two values of a boolean variable and selects the value that has the most optimal solution within the domain after performing the lookahead propagation. This approach added a significant time overhead that increased the overall solving time for many problems, with the lookahead configuration having a median increase of 8.7% over the default configuration for the optimization problems of the MiniZinc Challenge 2022. However, it was able to successfully emulate the performance of the heuristic solver, finding near-optimal solutions significantly faster than the default value selection. In particular, for the optimization problems of the MiniZinc Challenge 2022, on average, the lookahead configuration had a definite integral for the time vs objective graph 54.7% lower than the default Chuffed configuration.

Core-guided solvers and Implicit Hitting Set (IHS) solvers have become ubiquitous within the field of Maximum Satisfiability (MaxSAT). While both types of solvers iteratively increase the solution cost until a satisfiable solution is found, the manner in which this relaxation is performed leads to the belief that these techniques are wholly separate from one another. This work exhibits the difficulty of directly translating the cores found by an IHS-solver to cores utilizable by an OLL-solver due to an inherent disconnect between the manner in which both approaches explore the solution space. It will then be shown how this translation can be performed more easily given certain assumptions. Finally, several techniques are introduced for performing a translation from cores of the original formula to OLL-cores which avoids the aforementioned issue, resulting in a hybrid IHS-OLL algorithm. The comparison between the performance of the hybrid algorithm and RC2 shows that the hybrid algorithm achieves analogous performance in terms of the number of instances solved while indicating that utilising cores of the original formula as a starting point for an OLL solver can be beneficial for the performance of the solver in certain cases.

The multi-mode resource-constrained project scheduling problem (MRCPSP) is an extension of the resource-constrained project scheduling problem (RCPSP), which allows activities to be executed in multiple modes. The state-of-the-art solutions for solving this NP-Hard problem are dedicated algorithms and (meta-)heuristics. However, this paper considers a more flexible approach using a MaxSAT solver. The idea is to replace the existing variable selection strategy of the solver, Variable State Independent Decaying Sum (VSIDS), with two scheduling heuristics, Earliest Starting Time (EST) and Shortest Feasible Mode (SFM). We examine that combining the three heuristics results in a more efficient solver. In contrast, scheduling rules alone lead to a solver that performs significantly worse on any of the chosen metrics and benchmarks.

This paper provides a novel method of solving the resource-constrained project scheduling problem (RCPSP) with logical constraints (RCPSP-log) using satisfiability (SAT) solving and integrating variable selection heuristics. The extension provides two additional precedences: OR constraints and bidirectional (BI) relations, making it possible to express more complex dependencies between tasks. OR constraints enable a task to be dependent on multiple preceding tasks, while BI relations do not allow tasks to be executed at the same time. Both problems are known to be NP-hard.

The solution method consists of using a max satisfiability (MaxSAT) solver combined with variable selection heuristics. The paper investigates two heuristics, based on the greedy approach of scheduling each activity as early as possible and variable conflict analysis.

The results on well-known datasets from the literature show that most of the instances can be solved within the designated time limit. The proposed approaches contribute to reducing the makespan, especially when dealing with no logical constraints or only OR relations. For BI constraints, the algorithm is having difficulties in finding solutions, especially when increasing the number of activities, reporting fewer solutions than the baselines. Overall, the results provide insight into the integration of variable selection heuristics for SAT solving, with the potential for more investigation into problem-specific ideas.

This paper presents a new greedy heuristic to extend SAT Solvers when solving the Preemptive resource-constrained project scheduling problem (PRCPSP-ST). The heuristic uses domain-specific knowledge to generate a fixed order of variable selection. We also extend previous work into encoding PRCPSP-ST by providing an alternative upper bound. The heuristic was tested against VSDIS on the J12 dataset. These experiments show that it performed, on average, six times slower than VSDIS.

This paper solves job sequencing with one common and multiple secondary resources (JSOCMSR) problem by encoding it as a Boolean satisfiability (SAT) problem and applying domain-specific heuristics to improve the SAT solver’s performance. JSOCMSR problem is an NP-hard scheduling problem where each job utilizes two resources: a shared resource and a secondary job-dependent resource. First, the problem was modeled as an instance of SAT and then the SAT solver was augmented with a static greedy variable-ordering heuristic. This heuristic has led to significant improvement in the solver’s speed compared to a generic SAT heuristic for problem instances of larger size.

The Variable State Independent Decaying Sum (VSIDS) heuristic is one of the most effective variable selection heuristics for Conflict-Driven Clause-Learning (CDCL) SAT solvers. It works by keeping track of the activity values for each variable, which get bumped and decayed based on conflict analysis. These activity values usually start out arbitrarily at zero, which prompts the question if initializing these values can result in better performance.
This paper presents several adaptations of the VSIDS heuristic specialized for solving the Resource-Constraint Project Scheduling Problem with time varying resource availabilities and demands (RCPSP/t). The approach uses domain-specific knowledge to initialize the activity values of VSIDS with more relevant values. The experiments presented in this paper show that this domain-specific knowledge can indeed benefit the heuristic and can lead to better solve times, allowing the solver to find solutions for 17% more of the instances and find proven optimal solutions for 5% more instances of the PSPLIB data set.

The Algorithm Selection Problem is a relevant question in computer science that would enable us to predict which algorithm would perform better on a given instance of a problem.
Different solutions have been proposed, either using Mixed Integer Programming or machine learning models, but both suffer from either poor scalability, no guarantees of optimality, or not interpretable models that could be used to gain insights into the nature of the problem.
In this work we propose a dynamic programming method to build Optimal Decision Trees to solve the Algorithm Selection Problem, giving us an interpretable model that is globally optimal over the training dataset. We also show that this method is orders of magnitude faster in training trees that are identical to the current state-of-the-art and propose possible improvements for future work.

In this paper, we tackle the problem of creating decision trees that are both optimal and individually fair. While decision trees are popular due to their interpretability, achieving optimality can be difficult. Existing approaches either lack scalability or fail to consider individual fairness. To address this, we define individual fairness as a separable optimization task by analyzing the fairness gained and lost within a sub-tree. Using the Streed framework, we implement an algorithm that constructs optimal decision trees with the lowest misclassification score and individual fairness value above a certain threshold. Our algorithm has been tested on various datasets, demonstrating its effectiveness and scalability. This research is a significant step towards creating fair decision trees that are optimal, fair, and scalable.

Survival analysis revolves around studying and predicting the time it takes for a particular event to occur. In clinical trials on terminal illnesses, this is usually the time from the diagnosis of a patient until their death. Estimating the odds of survival of a new patient can be done by analyzing survival data from past patients in similar conditions. To cluster similar patients based on a set of features, survival trees may be employed, which act as decision trees that assign a survival distribution to each cluster. Many algorithms exist for creating useful survival trees, but not for creating optimal survival trees. In this paper, research on finding optimal classification trees is applied to survival analysis, by adapting the MurTree algorithm to construct survival trees. We present SurTree, an algorithm that applies many of MurTree’s techniques to create globally optimal survival trees. Furthermore, we compare the output quality and runtime performance of SurTree to a state-of-the-art method for constructing survival trees, showing its optimality and its fast computation times on smaller datasets.

Decision trees make decisions in a way interpretable to humans, this is important when machines are increasingly used to aid in making high-stakes and socially sensitive decisions. While heuristics have been used for a long time to find decision trees with reasonable accuracy, recent approaches find fully optimal trees. Due to the computational hardness of finding fully optimal decision trees, it is only practically possible to find shallow trees for a limited dataset size. However, continuous algorithmic improvements keep pushing the scale of feasible solutions. Dynamic Programming approaches promise to find scalable optimal decision trees but need to be adapted for different objectives, such as regression. We combine and adapt the algorithmic techniques of two Dynamic Programming methods, creating a new method that improves the scalability of optimal regression trees. This new method often achieves an order of magnitude speed improvement over a previous state-of-the-art method.

Machine learning can be used to classify patients in a hospital. Here, the classifier has to minimize the cost of misclassifying the patient and minimize the costs of the tests. Unfortunately, obtaining features may be costly, e.g., taking blood tests or doing an x-ray scan. Furthermore, it is possible that acquiring those test results may take a few days. To train such a classifier, several machine learning algorithms exist. Decision trees appear as favourites since, unlike other classifiers, decision trees do not need all feature values to classify an instance. Current approaches, however, only use heuristics to find a local optimum. Although heuristics are relatively fast, they are not optimal and therefore may not capture well the underlying characteristics of the given dataset. We propose an optimal approach to train cost-sensitive decision trees while also considering these delayed tests. Here we show, smaller trees with higher accuracy and a lower cost can be constructed, compared to a heuristic approach. We use dynamic programming to allow us to skip many calculations, which speeds up the programming time to seconds.