The knowledge gap between an expert and a non-expert often materializes in two ways: (i) Different preferences (or perceived costs) that may encode information about hidden costs and intuitive anticipation of future events or uncertainty [1]. (ii) Specific rules applied to make decisions, which may again reflect knowledge about hidden costs and uncertainty but also additional constraints. These decision rules often follow a given logic (e.g. “if condition A met, then perform operation B”) and can also serve as heuristics for the expert to arrive at their decisions quickly [2].
In this work, we apply an inverse optimization (IO) approach [3] to jointly learn an expert decision maker’s perceived costs and decision rules. The key idea of IO is to model the decision-making process as an optimization problem and estimate the unknown model parameters (in this case cost parameters) using the given decision data. The postulated decision rules can generally be stated as logical propositions, which in turn can be formulated as mixed-integer linear constraints, resulting in a mixed-integer linear program. The resulting IO problem is solved using a cutting-plane algorithm [4, 5]. The results are inherently interpretable as they directly indicate the perceived costs as well as which decision rules apply. Another major advantage of the IO approach is its ability to explicitly incorporate all physical constraints, which improves data efficiency [6, 7] and ensures that the predicted decisions are feasible.
We apply the proposed approach to the Amazon Challenge dataset [8, 9], where we predict the routes chosen by expert human drivers to deliver packages to a pre-defined set of stops, based on their past routing decisions. The given stops are grouped into zones, and the drivers tend to visit all the stops in one zone before moving on to the next. The results from solving the corresponding IO problem also indicate that these zones themselves are arranged into larger clusters and that the zones within a cluster are visited before moving on to another cluster. Applying this additional decision rule ultimately led to better predictions, which showcases the ability of the IO approach, with its greater modeling flexibility, to accurately capture and replicate human experts’ decision-making processes in a real-world setting.
References:
[1] Mikael Rönnqvist, Gunnar Svenson, Patrik Flisberg, and Lars-Erik Jönsson. Calibrated route finder: Improving the safety, environmental consciousness, and cost effectiveness of truck routing in Sweden. Interfaces, 47(5):372–395, 2017.
[2] Robert JB Hutton and Gary Klein. Expert decision making. Systems Engineering: The Journal of The International Council on Systems Engineering, 2(1):32–45, 1999.
[3] Ravindra K Ahuja and James B Orlin. Inverse optimization. Operations Research, 49(5):771–783, 2001.
[4] Lizhi Wang. Cutting plane algorithms for the inverse mixed integer linear programming problem. Operations Research Letters, 37(2):114–116, 2009.
[5] Mahsa Moghaddass and Daria Terekhov. Inverse integer optimization with multiple observations. Optimization Letters, 15(4):1061–1079, 2021.
[6] Rishabh Gupta and Qi Zhang. Decomposition and adaptive sampling for data-driven inverse linear optimization. INFORMS Journal on Computing, 34(5):2720–2735, 2022.
[7] Rishabh Gupta and Qi Zhang. Efficient learning of decision-making models: A penalty block coordinate descent algorithm for data-driven inverse optimization. Computers & Chemical Engineering, 170:108123, 2023.
[8] Amazon Last-Mile Routing Research Challenge | supported by the MIT Center for Transportation & Logistics. https://routingchallenge.mit.edu/.
[9] Daniel Merchán, Jatin Arora, Julian Pachon, Karthik Konduri, Matthias Winkenbach, Steven Parks, and Joseph Noszek. 2021 Amazon Last Mile Routing Research Challenge: Data Set. Transportation Science, 58(1):8–11, 2022.