# Exact Solution to Data-Driven Inverse Optimization of MILPs in Finite Time via Gradient-Based Methods

arXiv: https://arxiv.org/abs/2405.14273 · HTML: https://mlsanity.com/paper/2405.14273/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 57 references that are in the map.
- First posted on arXiv 23 May 2024.

## Builds on (most cited first, 23 of 23)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Learning with Differentiable Perturbed Optimizers](https://mlsanity.com/paper/2002.08676/) (2020)
- [Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application](https://mlsanity.com/paper/1309.1541/) (2013)
- [Inverse Optimization: Theory and Applications](https://mlsanity.com/paper/2109.03920/) (2021)
- [MetaGrad: Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1604.08740/) (2016)
- [Inverse Optimization with Noisy Data](https://mlsanity.com/paper/1507.03266/) (2015)
- [Data-driven Inverse Optimization with Imperfect Information](https://mlsanity.com/paper/1512.05489/) (2015)
- [Data-Driven Estimation in Equilibrium Using Inverse Optimization](https://mlsanity.com/paper/1308.3397/) (2013)
- [MetaGrad: Adaptation using Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/2102.06622/) (2021)
- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [Contextual Inverse Optimization: Offline and Online Learning](https://mlsanity.com/paper/2106.14015/) (2021)
- [An Online-Learning Approach to Inverse Optimization](https://mlsanity.com/paper/1810.12997/) (2018)
- [Contextual Recommendations and Low-Regret Cutting-Plane Algorithms](https://mlsanity.com/paper/2106.04819/) (2021)
- [Inverse Optimization: Closed-form Solutions, Geometry and Goodness of fit](https://mlsanity.com/paper/1511.04650/) (2015)
- [Maximum Optimality Margin: A Unified Approach for Contextual Linear Programming and Inverse Linear Programming](https://mlsanity.com/paper/2301.11260/) (2023)
- [An Inverse Optimization Approach to Measuring Clinical Pathway Concordance](https://mlsanity.com/paper/1906.02636/) (2019)
- [Online Convex Optimization Perspective for Learning from Dynamically Revealed Preferences](https://mlsanity.com/paper/2008.10460/) (2020)
- [A proof of convergence of inverse reinforcement learning for multi-objective optimization](https://mlsanity.com/paper/2305.06137/) (2023)
- [A proof of imitation of Wasserstein inverse reinforcement learning for multi-objective optimization](https://mlsanity.com/paper/2305.10089/) (2023)
- [Data-Driven Inverse Optimization for Marginal Offer Price Recovery in Electricity Markets](https://mlsanity.com/paper/2302.05498/) (2023)

## Built on by (most cited first, 4 of 4)

- [Inverse Mixed-Integer Programming: Learning Constraints then Objective Functions](https://mlsanity.com/paper/2510.04455/) (2025)
- [Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs](https://mlsanity.com/paper/2607.22263/) (2026)
- [Online Inverse Integer Linear Optimization via Small-Gradient Skipping: Constant Regret and Finite Mistakes](https://mlsanity.com/paper/2609.09809/) (2026)
- [Outperformance Inverse Optimization: Learning Objective Functions that Outperform Agent Decisions](https://mlsanity.com/paper/2610.09890/) (2026)

## Abstract (arXiv)

A data-driven inverse optimization problem (DDIOP) is the problem of estimating the objective-function parameters (weights) that explain observed optimal-solution data, and it arises in many applications, including mixed integer linear programming (MILP). In inverse optimization for MILPs, the prediction error of the features is discontinuous with respect to the weights, so applying gradient-based optimization directly is difficult. In this paper we focus on the suboptimality loss. This loss attains its minimum value, zero, if and only if the weights are exactly consistent with the observed data. Using the fact that this loss is convex and piecewise linear and that its set of minimizers has a relative interior point, we show that a broad class of gradient-based optimization methods, including projected subgradient descent, reaches exact consistency with the observed data in finitely many iterations (an exact solution is obtained in finite time). This guarantee holds for plain projected subgradient descent with standard diminishing step sizes, requiring neither prior knowledge of the optimal value nor smoothness of the objective. Through numerical experiments, we confirm this finite-step attainment behavior.