A data-driven methodology for the automated configuration of online algorithms

摘要

With the goal of devising algorithms for decision support in operational tasks, we introduce a new methodology for the automated configuration of algorithms for combinatorial online optimization problems. The procedure draws upon available instance data and is capable of recognizing data patterns which prove beneficial to the overall outcome. Since online optimization requires repetitive decision making without complete future information, no online algorithm can be optimal for every instance and it is reasonable to restrict attention to rule-based algorithms. We consider such algorithms in the form of procedures which derive their decisions using a threshold value. Threshold values are computed by evaluating a mathematical term (threshold value expression) composed of the available instance data elements. The goal then consists of determining the structure of the threshold value expression leading to the best algorithm performance. To this end, we employ a simulated annealing scheme returning the most favorable term composition given the available instance data. The resulting methodology can be implemented as part of data-driven decision support systems in order to facilitate knowledge-based decision making. Decision rules are generated in an automated fashion once historical input data is provided. The methodology is successfully instantiated in a series of computational experiments for three classes of combinatorial online optimization problems (scheduling, packing, lot sizing). Results show that automatically configured online algorithms are even capable of substantially outperforming well-known online algorithms in respective problem settings. We attribute this effect to the methodology's capability of integrating instance data into the process of algorithm configuration.