Inverse Optimization

Session date: 4 November 2024

Summary:

In Inverse Optimization problems, a learning agent aims to learn how to mimic the behavior of an expert agent, which given an exogenous signal, returns an action. The underlying assumption is that in order to compute its action, the expert agent solves an optimization problem parametric in the exogenous signal. Therefore, given examples of exogenous signals and corresponding expert actions, the goal of the learner is to learn the cost function being optimized by the expert. In this presentation, we will talk about fundamental concepts of Inverse Optimization and novel results, as well as applications to static and dynamic routing problems.

Relevant papers

Learning in Inverse Optimization: Incenter Cost, Augmented Suboptimality Loss, and Algorithms

Pedro Zattoni Scroccaro, Bilge Atasoy, and Peyman Mohajerin Esfahani

Operations research, "7 " # "jul" 2024

Abs HTML

Enhancing the Efficiency and Accuracy of Inverse Optimization Inverse optimization (IO) is used to model the behavior of decision-making agents who solve optimization problems in response to external signals. Inspired by the geometry of IO problems, in “Learning in Inverse Optimization: Incenter Cost, Augmented Suboptimality Loss, and Algorithms,” Zattoni Scroccaro, Atasoy, and Mohajerin Esfahani propose the “incenter” concept to solve IO problems, which unlike previously proposed approaches, can be used to derive computationally tractable solutions to this modeling problem. Moreover, they also propose a novel loss function for IO problems and a tailored optimization algorithm to optimize it. Extensive numerical experiments showcase the improved efficiency and accuracy of the proposed IO formulations and algorithm.
Inverse optimization for routing problems

Pedro Zattoni Scroccaro, Piet Beek, Peyman Mohajerin Esfahani, and 1 more author

Transportation science, "7 " # "jul" 2024

Abs HTML

We propose a method for learning decision makers’ behavior in routing problems using inverse optimization (IO). The IO framework falls into the supervised learning category and builds on the premise that the target behavior is an optimizer of an unknown cost function. This cost function is to be learned through historical data, and in the context of routing problems, can be interpreted as the routing preferences of the decision makers. In this view, the main contributions of this study are to propose an IO methodology with a hypothesis function, loss function, and stochastic first-order algorithm tailored to routing problems. We further test our IO approach in the Amazon Last Mile Routing Research Challenge, where the goal is to learn models that replicate the routing preferences of human drivers, using thousands of real-world routing examples. Our final IO-learned routing model achieves a score that ranks second compared with the 48 models that qualified for the final round of the challenge. Our examples and results showcase the flexibility and real-world potential of the proposed IO methodology to learn from decision-makers’ decisions in routing problems. History: This paper has been accepted for the Transportation Science Special Issue on TSL Conference 2023. Funding: This work was supported by the European Research Council [TRUST-949796].