Fast Continuous and Integer L-Shaped Heuristics Through Supervised Learning
From MaRDI portal
Publication:6202344
DOI10.1287/IJOC.2022.0175arXiv2205.00897MaRDI QIDQ6202344FDOQ6202344
Authors: E. P. Larsen, Emma Frejinger, Bernard Gendron, Andrea Lodi 
Publication date: 26 March 2024
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Abstract: We propose a methodology at the nexus of operations research and machine learning (ML) leveraging generic approximators available from ML to accelerate the solution of mixed-integer linear two-stage stochastic programs. We aim at solving problems where the second stage is highly demanding. Our core idea is to gain large reductions in online solution time while incurring small reductions in first-stage solution accuracy by substituting the exact second-stage solutions with fast, yet accurate supervised ML predictions. This upfront investment in ML would be justified when similar problems are solved repeatedly over time, for example, in transport planning related to fleet management, routing and container yard management. Our numerical results focus on the problem class seminally addressed with the integer and continuous L-shaped cuts. Our extensive empirical analysis is grounded in standardized families of problems derived from stochastic server location (SSLP) and stochastic multi knapsack (SMKP) problems available in the literature. The proposed method can solve the hardest instances of SSLP in less than 9% of the time it takes the state-of-the-art exact method, and in the case of SMKP the same figure is 20%. Average optimality gaps are in most cases less than 0.1%.
Full work available at URL: https://arxiv.org/abs/2205.00897
This page was built for publication: Fast Continuous and Integer L-Shaped Heuristics Through Supervised Learning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202344)
