(402f) Inverse Linear Optimization: Conceptual Framework, Two-Phase Algorithm, and Adaptive Sampling

Real-world decision making generally involves selecting the best among multiple possible options. It can be conjectured that these decisions are solutions to an underlying optimization problem which, in many cases, is unknown even to the decision maker. Uncovering these hidden optimization problems can act as a medium to generate insights into the decision-making process and predict future decisions. Examples where this can be useful are as diverse as learning the strategy of an expert decision maker operating a complex process, understanding the preferences of customers, or analyzing decision-making strategies in biological systems known to have evolved to behave optimally for their survival. Several of such decision-making problems can be formulated or approximated as linear programs (Burgard & Maranas, 2003; Saez-Gallego et al., 2016).

In this work, we develop a data-driven framework for uncovering the unknown cost vector when the decision-making process can be represented as a linear optimization problem. This is referred to as inverse optimization (Ahuja & Orlin, 2001). Research on inverse optimization started with a single, deterministic observation and has more recently progressed to the more realistic setting of multiple noisy observations coming from different sets of input parameters (Aswani et al., 2018). The latter is often referred to as data-driven inverse optimization and is the focus of this work.

The two main theoretical contributions of this work are as follows: (1) We propose a novel two-phase algorithm that performs denoising of observations and cost vector estimation separately. Our approach derives from a polyhedral understanding of the problem and is shown to be effective in alleviating the limitations of existing methods found to lead to severely restricted feasible sets of cost vector estimates. (2) We develop a rigorous adaptive sampling strategy that systematically reduces the set of feasible estimates and therefore increases the confidence in the resulting point estimate. Our extensive computational experiments show that the proposed approach can find the true cost vector (or the best possible estimate) with significantly less samples compared to naïve random sampling.

References

Ahuja, R. K., & Orlin, J. B. (2001). Inverse optimization. Operations Research, 49(5), 771–783.

Aswani, A., Shen, Z. J. M., & Siddiq, A. (2018). Inverse optimization with noisy data. Operations Research, 66(3), 870–892.

Burgard, A. P., & Maranas, C. D. (2003). Optimization-based framework for inferring and testing hypothesized metabolic objective functions. Biotechnology and Bioengineering, 82(6), 670–677.

Saez-Gallego, J., Morales, J. M., Zugno, M., & Madsen, H. (2016). A Data-Driven Bidding Model for a Cluster of Price-Responsive Consumers of Electricity. IEEE Transactions on Power Systems, 31(6), 5001–5011.