Inverse Optimization Theory and Applications to Routing Problems

Abstract

This thesis concerns the fundamental problem of learning the behavior of decisionmaking agents using only observations of how they act in different situations. As humans, we do it all the time, and have been doing it since birth: think about how a child learns to speak and walk. However, this thesis does not only focus on imitating. We go a step further and try to learn why an agent does what it does. In other words, what is the agent’s objective, which led them to act in a certain way? This is a much harder question, but also much more rewarding when answered correctly: knowing the agent’s motivation allows us not only to imitate but also to understand or even influence the agent’s behavior. For this purpose, we ask the question: what is the agent optimizing for when making decisions? For instance, imagine a consumer agent that buys a certain set of products given their budget. To model the consumer’s behavior, we interpret their action as buying the products with maximum utility, given a limited budget. Thus, learning how the consumer evaluates each product (that is, the utility of each product for the consumer) would allow us to understand, replicate, and possibly influence their behavior. Mathematically, we model the decision process of the agent as an optimization program, and we use Inverse Optimization (IO) as a tool to “reverse engineer” the agent’s optimization program from observed behavior. This thesis can be divided into two parts. First, we dive into the mathematical formalization of the IO problem. We look at the geometry of thema thematical objects emerging from IO problems, and we discuss what it means to solve the IO problem and different ways to do it, proposing tractable reformulations and efficient algorithms. In the second part of this thesis, we develop a tailored IO methodology to solve IO problems emerging from routing problems. We test the potential of our methodology for modeling human driving behavior on real-world problems using data from the Amazon Last Mile Routing Research Challenge. We achieve excellent results, showcasing the potential of IO to solve real-world problems. Additionally, we also developed Inv Opt, an open-source Python package to solve general IO problems.