Predicting Tactical Solutions to Operational Planning Problems Under Imperfect Information

作     者：Larsen, Eric Lachapelle, Sebastien Bengio, Yoshua Frejinger, Emma Lacoste-Julien, Simon Lodi, Andrea 

作者机构：Univ Montreal Dept Comp Sci & Operat Res Montreal PQ H3T 1J4 Canada Univ Montreal CIRRELT Montreal PQ H3C 3J7 Canada Univ Montreal Mila Montreal PQ H2S 3H1 Canada Polytech Montreal CERC Montreal PQ H3T 1J4 Canada 

出 版 物：《INFORMS JOURNAL ON COMPUTING》 (美国运筹学与管理学会计算杂志)

年 卷 期：2022年第34卷第1期

页      面：227-242页

核心收录：

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

基　　金：Canadian National Railway Company Chair in Optimization of Railway Operations at the Universite de Montreal Natural Sciences and Engineering Research Council of Canada [CRD477938-14] Canada Foundation for Innovation Ministere de l' Economie, de la Science et de l'Innovation du Quebec Fonds de recherche du Quebec-Nature et technologies IVADO 

主　　题：supervised learning deep learning integer linear programming stochastic programming 

摘      要：This paper offers a methodological contribution at the intersection of machine learning and operations research. Namely, we propose a methodology to quickly predict expected tactical descriptions of operational solutions (TDOSs). The problem we address occurs in the context of two-stage stochastic programming, where the second stage is demanding computationally. We aim to predict at a high speed the expected TDOS associated with the second-stage problem, conditionally on the first-stage variables. This may be used in support of the solution to the overall two-stage problem by avoiding the online generation of multiple second-stage scenarios and solutions. We formulate the tactical prediction problem as a stochastic optimal prediction program, whose solution we approximate with supervised machine learning. The training data set consists of a large number of deterministic operational problems generated by controlled probabilistic sampling. The labels are computed based on solutions to these problems (solved independently and offline), employing appropriate aggregation and subselection methods to address uncertainty. Results on our motivating application on load planning for rail transportation show that deep learning models produce accurate predictions in very short computing time (milliseconds or less). The predictive accuracy is close to the lower bounds calculated based on sample average approximation of the stochastic prediction programs.