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. ... Read more

In inverse optimization (IO), an expert agent solves an optimization problem parametric in an exogenous signal. From a learning perspective, the goal is to learn the expert’s cost function given a data set of signals and corresponding optimal actions. Motivated by the geometry of the IO set of consistent cost vectors, we introduce the “incenter” concept, a new notion akin to the recently proposed circumcenter concept. Discussing the geometric and robustness interpretation of the incenter cost vector, we develop corresponding tractable convex reformulations that are in contrast with the circumcenter, which we show is equivalent to an intractable optimization program. We further propose a novel loss function called augmented suboptimality loss (ASL), a relaxation of the incenter concept for problems with inconsistent data. Exploiting the structure of the ASL, we propose a novel first-order algorithm, which we name stochastic approximate mirror descent. This algorithm combines stochastic and approximate subgradient evaluations, together with mirror descent update steps, which are provably efficient for the IO problems with discrete feasible sets with high cardinality. We implement the IO approaches developed in this paper as a Python package called InvOpt. Our numerical experiments are reproducible, and the underlying source code is available as examples in the InvOpt package. ... Read more

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. ... Read more

In the past few years, online convex optimization (OCO) has received notable attention in the control literature thanks to its flexible real-time nature and powerful performance guarantees. In this article, we propose new step-size rules and OCO algorithms that simultaneously exploit gradient predictions, function predictions and dynamics, features particularly pertinent to control applications. The proposed algorithms enjoy static and dynamic regret bounds in terms of the dynamics of the reference action sequence, gradient prediction error, and function prediction error, which are generalizations of known regularity measures from the literature. We present results for both convex and strongly convex costs. We validate the performance of the proposed algorithms in a trajectory tracking case study, as well as portfolio optimization using real-world datasets. ... Read more