Abstract
A data-driven inverse optimization problem (DDIOP) seeks to estimate an objective function (i.e., weights) that is consistent with observed optimal-solution data, and is important in many applications, including those involving mixed integer linear programs (MILPs). In the DDIOP for MILPs, the prediction loss on features (PLF), defined as the discrepancy between observed and predicted feature values, becomes discontinuous with respect to the weights, which makes it difficult to apply gradient-based optimization. To address this issue, we focus on a Lipschitz continuous and convex suboptimality loss. By exploiting its convex and piecewise-linear structure and the interiority of the minimum set, we show that a broad class of gradient-based optimization methods, including projected subgradient descent (PSGD), reaches the minimum suboptimality loss value in a finite number of iterations, thereby exactly solving the DDIOP for MILPs. Furthermore, as a corollary, we show that PSGD attains the minimum PLF in finitely many iterations. We also derive an upper bound on the number of iterations required for PSGD to reach finite convergence, and confirm the finite-step behavior through numerical experiments.