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.