A Sampling-Based Relaxation Approach to Contextual Inverse Optimization

Abstract

Decision-making pipelines increasingly rely on prediction models whose outputs serve as inputs to downstream optimization problems. Decision-Focused Learning (DFL) has emerged as a promising approach to training such models by directly optimizing decision quality rather than predictive accuracy alone. While most existing DFL methods assume a complete-information setting in which the ground-truth optimization parameters are observed, this paper studies Contextual Inverse Optimization (CIO), an incomplete-information setting in which only the resulting solutions are observed. Prior work on CIO has proposed learning algorithms based on optimality conditions for linear programs, as well as methods that repeatedly solve inverse optimization problems to handle integer programs, often incurring a substantial computational burden. In this paper, we propose a learning algorithm for general optimization problems with linear objective functions that eliminates the need to solve inverse optimization problems. The proposed method learns prediction models by solving a Relaxed Inverse Optimization Problem (RIOP), constructed based on feasible solutions randomly sampled from the feasible region, thereby reducing the computational overhead associated with existing CIO methods. Numerical experiments demonstrate that our method achieves competitive performance in terms of regret compared with existing methods, while offering improved computational efficiency for certain classes of downstream optimization problems.