Inverse Mixed-Integer Programming: Learning Constraints then Objective Functions

Akira Kitaoka

math.OCOct 6, 2025

Inverse Mixed-Integer Programming: Learning Constraints then Objective Functions

Authors: Akira Kitaoka

Abstract

Data-driven inverse optimization for mixed-integer linear programs (MILPs), which seeks to learn an objective function and constraints consistent with observed decisions, is important for building accurate mathematical models in a variety of domains, including power systems and scheduling. However, to the best of our knowledge, existing data-driven inverse optimization methods primarily focus on learning objective functions under known constraints, and learning both objective functions and constraints from data for MILPs remains largely unexplored. In this paper, we propose a two-stage approach for a class of inverse optimization problems in which the objective is a linear combination of given feature functions and the constraints are parameterized by unknown functions and thresholds. Our method first learns the constraints and then, conditioned on the learned constraints, estimates the objective-function weights. On the theoretical side, we provide finite-sample guarantees for solving the proposed inverse optimization problem. To this end, we develop statistical learning tools for pseudo-metric spaces under sub-Gaussian assumptions and use them to derive a learning-theoretic framework for inverse optimization with both unknown objectives and constraints. On the experimental side, we demonstrate that our method successfully solves inverse optimization problems on scheduling instances formulated as ILPs with up to 100 decision variables.

Figures & tables

Panel of Figure 1 — Figure 1. Inputs and outputs of the DDIOP (schematic). Unknown parameters (objective-function coefficients and constraint parameters) are estimated so that the observed schedule $\hat{x}$ becomes an optimal solution.

Forward problem	C	O	References
MILP	✓	✓	Ours
MILP	✓	$\times$	Kolb et al. (2017) , Kumar et al. (2019) , Suenaga et al. (2024)
MILP	$\times$	✓	Bärmann et al. (2017) ; Bärmann et al. (2018) , Gollapudi et al. (2021) , Besbes et al. (2021) ; Besbes et al. (2025) , Kitaoka and Eto (2023a) ; Kitaoka (2024) , Zattoni Scroccaro et al. (2025) , Sakaue et al. (2025) , Elhedhli and Okur (2025) , Bulut and Ralphs (2021) , Kitaoka and Eto (2023b)
ILP	$\times$	✓	Suzuki et al. (2019)
LP	✓	✓	Aswani et al. (2018)
LP	✓	$\times$	Chan and Kaw (2020) , Ghobadi and Mahmoudzadeh (2021) , Ren et al. (2025)

Table 1. Summary comparison of inverse optimization methods with a guarantee that the parameters can be learned (C: capable of learning constraints; O: capable of learning objectives).

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

$D$	Decision variables	Constraints	Mean (s)	Max (s)	Median (s)
4	16	40	0.125	0.391	0.089
5	25	65	0.313	0.737	0.322
6	36	96	2.245	6.492	1.627
7	49	133	3.314	11.830	2.296
8	64	176	62.761	237.787	51.446
9	81	225	194.870	1040.056	55.118

Appendix

Table 3. The time required to solve Equation 3.5 in Experiment 1.

$D$	4	5	6	7
Decision variables	16	25	36	49
Constraints	40	65	96	133
Mean (s)	1.04	6.16	9.24	63.00
Max (s)	3.79	28.44	43.05	202.19
Median (s)	0.33	3.62	6.42	44.81
Completion rate	100%	100%	100%	100%

Appendix

Table 4. The time required to solve Equation 3.5 in Experiment 2.

Table 10

Table 11

$N$	Exact attainment (train)	$\phi$ recovery	Penalty term	Max term	$\ell^{\mathrm{sub},1}$	MSEF (median)
1	$100\%$	$0\%$	$3.69$	$0.047$	$3.74\ (0.46)$	$7.53$
2	$100\%$	$8\%$	$1.87$	$0.058$	$1.92\ (0.30)$	$6.95$
4	$96\%$	$52\%$	$0.354$	$0.054$	$0.409\ (0.093)$	$4.16$
8	$100\%$	$68\%$	$0.085$	$0.028$	$0.113\ (0.029)$	$0.99$
16	$84\%$	$84\%$	$0.038$	$0.012$	$0.051\ (0.019)$	$1.29$
32	$68\%$	$92\%$	$0.0012$	$0.0030$	$0.0042\ (0.0010)$	$0.36$

Appendix

Table 9. Results of the verification of the generalization error (

D=5

25

episodes for each

N

100

held-out states,

\lambda=1

). Standard errors in parentheses.

Figure 13. Mean and median of the MSEF on held-out states (

D=5

, log-log scale).

Explore similar work

Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs
Jul 24, 2026Akira KitaokaLinear Programming Optimal Sample Complexity
Uncovering expert objectives in production planning via inverse optimization: An industrial case study
Aug 7, 2026Shivi Dixit, Rishabh Gupta, Adam Kelloway +2Objective Functions Industrial
Department of Chemical Engineering and Materials Science, University of Minnesota, Minneapolis, MN 55455, USA · The Dow Chemical Company, Midland, MI 48642, USA · Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, USA
Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming
May 18, 2026Tung Quoc Le, Anh Tuan Nguyen, Viet Anh NguyenMixed-Integer Programming Convex Relaxation
Université Grenoble Alpes, LJK, CNRS, Grenoble INP, 38000 Grenoble, France · Carnegie Mellon University, Machine Learning Department · Chinese University of Hong Kong, Department of Systems Engineering and Engineering Management.

Jul 24, 2026, math.OCJ/K move · Enter open · S save

Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs

Akira Kitaoka

Linear Programming Optimal Sample Complexity Objective Functions

Open paper AskPDF 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 integer linear programming (ILP). It is known that, by applying gradient-based optimization methods to the suboptimality loss, the inverse optimization of ILPs can be solved exactly within finitely many oracle iterations, and that the required number of iterations is bounded as

T=O(1/γ(\ell_{\mathrm{sub}})^2)

in terms of a problem-dependent geometric constant

γ(\ell_{\mathrm{sub}})

. However, no means of bounding

γ(\ell_{\mathrm{sub}})

from below as a function of the problem size has been available, and hence the number of iterations could not be given as an explicit function of the problem size. We therefore give, when the forward problem is an integer linear program (ILP), the number of iterations sufficient for projected subgradient descent applied to the suboptimality loss to achieve exact consistency with the observed data, as a fully explicit function of the number of samples, the dimension of the features, the ranges of the features, and the structure of the constraint coefficient matrix, up to polynomial factors in the basic constants (the diameter of the weight set, the step-size parameter, and the Lipschitz constant of the suboptimality loss).

Abstract

Explore similar work

Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs

Uncovering expert objectives in production planning via inverse optimization: An industrial case study

Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming