Survival analysis studies and predicts the time of death, or other singular unrepeated events, based on historical data, while the true time of death for some instances is unknown. Survival trees enable the discovery of complex nonlinear relations in a compact human comprehensible model, by recursively splitting the population and predicting a distinct survival distribution in each leaf node. We use dynamic programming to provide the first survival tree method with optimality guarantees, enabling the assessment of the optimality gap of heuristics. We improve the scalability of our method through a special algorithm for computing trees up to depth two. The experiments show that our method’s run time even outperforms some heuristics for realistic cases while obtaining similar out-of-sample performance with the state-of-the-art.

@en

Global optimization of decision trees has shown to be promising in terms of accuracy, size, and consequently human comprehensibility. However, many of the methods used rely on general-purpose solvers for which scalability remains an issue. Dynamic programming methods have been shown to scale much better because they exploit the tree structure by solving subtrees as independent subproblems. However, this only works when an objective can be optimized separately for subtrees. We explore this relationship in detail and show necessary and sufficient conditions for such separability and generalize previous dynamic programming approaches into a framework that can optimize any combination of separable objectives and constraints. Experiments on five application domains show the general applicability of this framework, while outperforming the scalability of general-purpose solvers by a large margin.@en

Interpretable and fair machine learning models are required for many applications, such as credit assessment and in criminal justice. Decision trees offer this interpretability, especially when they are small. Optimal decision trees are of particular interest because they offer the best performance possible for a given size. However, state-of-the-art algorithms for fair and optimal decision trees have scalability issues, often requiring several hours to find such trees even for small datasets. Previous research has shown that dynamic programming (DP) performs well for optimizing decision trees because it can exploit the tree structure. However, adding a global fairness constraint to a DP approach is not straightforward, because the global constraint violates the condition that subproblems should be independent. We show how such a constraint can be incorporated by introducing upper and lower bounds on final fairness values for partial solutions of subproblems, which enables early comparison and pruning. Our results show that our model can find fair and optimal trees several orders of magnitude faster than previous methods, and now also for larger datasets that were previously beyond reach. Moreover, we show that with this substantial improvement our method can find the full Pareto front in the trade-off between accuracy and fairness.@en

The power system is undergoing a significant change as it adapts to the intermittency and uncertainty from renewable generation. Flexibility from loads such as electric vehicles (EVs) can serve as reserves to sustain the supply-demand balance in the grid. Some reserve markets have rules for participation that are computationally challenging for aggregators of such flexible loads: they are asked to bid both volume and price, and on top of this there is a minimum-volume requirement, a constraint currently under discussion both in the US and European markets. Several state-of-the-art methods to find a bidding strategy for the demand scheduling of large fleets of flexible loads in the day-ahead and reserve market are adapted to deal with such a shared constraint, and are compared based on costs, unscheduled demand, and running time. The experimental analysis shows that although such a shared constraint significantly affects scalability, some of the proposed adaptations can deal with this without much loss in quality. This comparison also shows the importance of including good uncertainty models for dealing with the risk of not meeting the users’ demands, and that it is possible to find an optimal single price per time unit for scheduling a fleet of EVs.

@en

Due to increasing numbers of intermittent and distributed generators in power systems, there is an increasing need for demand responses to maintain the balance between electricity generation and use at all times. For example, the electrification of transportation significantly adds to the amount of flexible electricity demand. Several methods have been developed to schedule such flexible energy consumption. However, an objective way of comparing these methods is lacking, especially when decisions are made based on incomplete information which is repeatedly updated. This paper presents a new benchmarking framework designed to bridge this gap. Surveys that classify flexibility planning algorithms were an input to define this benchmarking standard. The benchmarking framework can be used for different objectives and under diverse conditions faced by electricity production stakeholders interested in flexibility scheduling algorithms. Our contribution was implemented in a software toolbox providing a simulation environment that captures the evolution of look-ahead information, which enables comparing online planning and scheduling algorithms. This toolbox includes seven planning algorithms. This paper includes two case studies measuring the performances of these algorithms under uncertain market conditions. These case studies illustrate the importance of online decision making, the influence of data quality on the performance of the algorithms, the benefit of using robust and stochastic programming approaches, and the necessity of trustworthy benchmarking.@en

The problem of optimally scheduling the charging demand of electric vehicles within the constraints of the electricity infrastructure is called the charge scheduling problem. The models of the charging speed, horizon, and charging demand determine the computational complexity of the charge scheduling problem. We show that for about 20 variants the problem is either in P or weakly NP-hard and dynamic programs exist to compute optimal solutions. About 10 other variants of the problem are strongly NP-hard, presenting a potentially significant obstacle to their use in practical situations of scale. An experimental study establishes up to what parameter values the dynamic programs can determine optimal solutions in a couple of minutes.
@en

The problem of optimally scheduling the charging demand of electric vehicles within the constraints of the electricity infrastructure is called the charge scheduling problem. The models of the charging speed, horizon, and charging demand determine the computational complexity of the charge scheduling problem. For about 20 variants the problem is either in P or weakly NP-hard and dynamic programs exist to compute optimal solutions. About 10 other variants of the problem are strongly NP-hard, presenting a potentially significant obstacle to their use in practical situations of scale.@en

In power systems, demand and supply always have to be balanced. This is becoming more challenging due to the sustained penetration of renewable energy sources. Because of the increasing amount of electrical vehicles (EVs), and the high capacity and flexibility of their charging process, EVs are a good candidate for providing balancing services to electric systems. We propose a stochastic optimization method for an EV aggregator that models the uncertainty of the imbalance price, the reserve prices and the probability of acceptance and deployment of reserves. The model results in an optimal charging and discharging strategy considering day-ahead purchase, imbalance trading and reserve bids. Unlike previous studies, the reserve bids consists of both a quantity and an optimal price. Experimental evaluation shows that the proposed stochastic optimization method results in lower costs than deterministic and quantity-only bid solutions.@en