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

作     者：Dunke, Fabian Nickel, Stefan 

作者机构：Karlsruhe Inst Technol Inst Operat Res Discrete Optimizat & Logist Kaiserstr 12 D-76131 Karlsruhe Germany 

出 版 物：《DECISION SUPPORT SYSTEMS》 (决策支持系统)

年 卷 期：2020年第137卷

页      面：113343-113343页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Automated decision making Data-driven optimization Automated algorithm configuration Online optimization Simulated annealing Lean decision making 

摘      要：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.