Analyzing Local Structure in Predict+Optimize Loss Functions

Abstract

Predict then optimize (P+O) is an emerging field that uses machine learning to predict variables for a combinatorial optimization (CO) problem. In this, it has to overcome the discontinuous nature of combinatorial problems. Many different solutions have been proposed, like SPO+, PFYL and CaVE. What they all have in common is that they give up some information about the problem to make the loss function continuous. To get a better idea of where the strengths and weaknesses lie of P+O losses, we want to find how much of this information on problem structure is retained. This brings us to the main research question: How much of the local structure of regret do P+O loss functions follow? Are there ways to improve this? We found that all P+O methods tested struggled to consistently find locally optimal solutions, often leaving room for improvement in adjacent solutions. When locally optimal solutions were found, they were mostly already globally optimal. We found that P+O methods do not really consider local regret optimality except for the global solution. Since this solution often cannot be found, we reason that regret local search could improve these cases a lot. We develop Decision Guided Learning (DGL) as a regret local search algorithm and find good improvements for smaller machine learning models and medium to no improvements for larger machine learning models. We reason that when models are large enough to approximate all the true optimal solutions, the need for regret local search becomes less.