mlsanityData to 7 Oct 2026

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

arXiv 2405.14273 ↗First posted 23 May 2024cs.LG cs.AI math.OCcited by 3

Not on the map. Why?

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.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 23 of its 57 references that are in the map. First posted on arXiv 23 May 2024.

Builds on

23 of 57 references.

References · 23

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2017Smart "Predict, then Optimize"cited by 332
  3. 2018Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimizationcited by 220
  4. 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 158
  5. 2020Learning with Differentiable Perturbed Optimizerscited by 81
  6. 2013Projection onto the probability simplex: An efficient algorithm with a simple proof, and an applicationcited by 65
  7. 2021Inverse Optimization: Theory and Applicationscited by 48
  8. 2016MetaGrad: Multiple Learning Rates in Online Learningcited by 46
  9. 2015Inverse Optimization with Noisy Datacited by 34
  10. 2015Data-driven Inverse Optimization with Imperfect Informationcited by 33
  11. 2013Data-Driven Estimation in Equilibrium Using Inverse Optimizationcited by 32
  12. 2021MetaGrad: Adaptation using Multiple Learning Rates in Online Learningcited by 26
11 more
  1. 2022SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problemscited by 21
  2. 2021Contextual Inverse Optimization: Offline and Online Learningcited by 20
  3. 2018An Online-Learning Approach to Inverse Optimizationcited by 16
  4. 2021Contextual Recommendations and Low-Regret Cutting-Plane Algorithmscited by 14
  5. 2015Inverse Optimization: Closed-form Solutions, Geometry and Goodness of fitcited by 13
  6. 2023Maximum Optimality Margin: A Unified Approach for Contextual Linear Programming and Inverse Linear Programmingcited by 13
  7. 2019An Inverse Optimization Approach to Measuring Clinical Pathway Concordancecited by 9
  8. 2020Online Convex Optimization Perspective for Learning from Dynamically Revealed Preferencescited by 7
  9. 2023A proof of convergence of inverse reinforcement learning for multi-objective optimizationcited by 3
  10. 2023A proof of imitation of Wasserstein inverse reinforcement learning for multi-objective optimizationcited by 3
  11. 2023Data-Driven Inverse Optimization for Marginal Offer Price Recovery in Electricity Marketscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2025Inverse Mixed-Integer Programming: Learning Constraints then Objective Functionscited by 2
  2. 2026Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programscited by 1
  3. 2026Outperformance Inverse Optimization: Learning Objective Functions that Outperform Agent Decisionscited by 0