Unified Karp-Reduction Equivalence and Direct Algorithms for Inverse Mixed Integer Linear Optimization

Bulut and Ralphs (SIAM J. Optim., 2021) classified the decision versions of the inverse mixed integer linear optimization problem (IMILP) — given a target vector $x^0$ and an estimate $c$ of the objective function, find the objective $d$ nearest to $c$ in a $p$-norm that makes $x^0$ optimal for the forward MILP — showing that primal bound verification is coNP-complete and dual bound verification NP-complete (the two placements reversed relative to the forward problem), and that optimal value verification is $D^P$-complete, the same class as for the forward problem; the inverse problem is equivalent to separation over the radial cone at $x^0$. They left open two linked questions, stated precisely: (i) whether a unified theorem in the style of the Grötschel–Lovász–Schrijver optimization–separation equivalence, expressed in terms of Karp reductions, can integrate the forward, inverse, and separation problems — including formally establishing the indicated $D^P$-completeness of boundary membership and the indicated coNP membership of complement-of-relative-interior membership for MILP feasible sets; and (ii) whether IMILP admits a direct, oracle-free exact algorithm, or whether reliance on a forward-problem oracle can be proven inherent. Both questions remain open as of 2026: subsequent work has improved oracle-based cutting-plane algorithms and proved neighboring complexity results, but neither the unified equivalence nor any direct algorithm or lower bound has been established.

Background

Inverse optimization reverses the usual direction of an optimization problem: given an observed decision $x^0$ (the target vector) and an estimate $c$ of the objective function, it asks for the parameters closest to the estimates under which $x^0$ is an optimal solution of the associated forward problem. The classical reference point is Ahuja and Orlin (2001), who showed that when the forward problem is polynomially solvable, the inverse problem under the $\ell_1$ and $\ell_\infty$ norms is also polynomially solvable; Heuberger (2004) surveys the broader landscape of inverse combinatorial optimization.

Here the forward problem is a mixed integer linear optimization problem (MILP) $\max\{d^\top x : x\in S\}$ with feasible region $S=\{x\in\mathbb{R}^n : Ax\le b\}\cap(\mathbb{Z}^r\times\mathbb{R}^{n-r})$ for rational data $A,b$. Writing $S^+=S\cup\{x^0\}$ (Bulut and Ralphs deliberately do not assume $x^0\in S$, since membership in $S$ can be checked in preprocessing and dropping the assumption is what connects the inverse problem to separation), a feasible objective is any $d$ with $d^\top x^0\ge d^\top x$ for all $x\in S^+$; the set of feasible objectives is a closed convex cone $C^\circ(x^0)$, the polar of the radial cone $C(x^0)=\mathrm{cone}(S^+-x^0)$ of feasible directions at $x^0$. The inverse MILP is then

$\mathrm{IMILP}:\quad \min_{d}\{\|c-d\|_p : d\in C^\circ(x^0)\},$

where $p\ge 1$ fixes the norm.

Algorithmically, Wang (2009) observed that under the $\ell_1$ and $\ell_\infty$ norms IMILP becomes a linear program with exponentially many constraints, solvable by a cutting-plane algorithm that repeatedly solves the forward MILP to generate violated constraints; Schaefer (2009) and Lamperski and Schaefer (2015) instead characterize the inverse-feasible region through the superadditive duality theory of integer programming (the analogue of linear-programming duality for integer programs, whose dual variables are superadditive functions on the integer lattice rather than vectors), giving direct single-level formulations with exponentially many variables and constraints; Bodur, Chan, and Zhu (2022) developed polyhedral characterizations of the inverse-feasible region and trust-region cutting-plane methods that solve smaller restricted forward problems per iteration, the current computational state of the art. All exact methods with practical performance solve forward MILPs as subroutines.

The complexity-theoretic touchstone is the theorem of Grötschel, Lovász, and Schrijver (1993) (GLS) that optimization over a polyhedron of bounded facet complexity (the maximum encoding length of an inequality in a facet-defining description) and the associated separation problem — deciding whether a given point lies in a polyhedron described implicitly, and producing a violated valid inequality if not — are polynomially equivalent. The reductions in the GLS framework are Cook reductions: polynomial-time algorithms allowed polynomially many calls to an oracle for the other problem. A Karp reduction is the stronger, single-call notion: a polynomial-time mapping $f$ with $x\in L_2$ if and only if $f(x)\in L_1$. The two notions of completeness are known to differ in general under standard complexity assumptions, so pinning down which equivalence holds at Karp strength carries real information. The relevant classes beyond NP and coNP are $D^P=\{L_1\cap L_2 : L_1\in\mathrm{NP}, L_2\in\mathrm{coNP}\}$, introduced by Papadimitriou and Yannakakis (1982), who showed that the MILP optimal value verification problem is complete for it, and $\Delta_2^p$, the class of problems decidable in polynomial time with an NP oracle.

Bulut and Ralphs (2021) proved that for the inverse MILP, verification of a primal bound is coNP-complete, verification of a dual bound is NP-complete (the placements are reversed relative to the forward problem), and verification of the optimal value is $D^P$-complete, the same class as for the forward problem; these classifications hold for any $p$-norm. They further showed the inverse problem to be equivalent to the separation problem for the radial cone, and that, under the $\ell_1$ and $\ell_\infty$ norms, a cutting-plane algorithm solves IMILP with polynomially many calls to an oracle for the forward problem. Their conclusion states that the results lay the groundwork for a unified GLS-style theorem stated in terms of Karp reductions, but that its form is not obvious: separation is a two-way membership decision (point in the set or not), whereas the inverse problem implicitly demands a three-way decision — whether a given point lies in the relative interior of the convex hull of solutions, on its boundary, or in the complement of the set. They indicate, but do not formally prove, that boundary membership is $D^P$-complete and that membership in the complement of the relative interior (the union of the boundary and the complement of the set) is in coNP, with completeness for the latter neither claimed nor excluded; and they note that the existence of a direct (oracle-free) algorithm for the inverse problem cannot be ruled out by their results.

Problem Statement

Close the two theoretical gaps that Bulut and Ralphs (2021) explicitly left open concerning the relationship between the inverse MILP, its forward problem, and the associated separation problem.

(1) Unified Karp-reduction equivalence. State and prove — or refute — a version of the Grötschel–Lovász–Schrijver optimization–separation equivalence theorem, expressed in terms of Karp reductions, that integrates the inverse problem. The answer must fix the decision problems involved — primal bound, dual bound, and optimal value verification for the forward MILP and for the inverse MILP; separation over $\mathrm{conv}(S^+)$ and over the radial cone $C(x^0)$; and the three-way membership problem of deciding which of the three regions — the relative interior of $\mathrm{conv}(S^+)$, its boundary, or the complement of the set — contains a given rational point (equivalently, the two decision problems of boundary membership and of membership in the complement of the relative interior, the union of the boundary and the complement) — together with rational input encodings and polyhedral-complexity parameters, and must establish, by explicit many-one reductions and completeness proofs, which of these problems are Karp-equivalent and for which classes (P, NP, coNP, $D^P$) they are complete. The classifications already proved in the source anchor the answer: inverse primal bound verification is coNP-complete, inverse dual bound verification NP-complete, and both optimal value verification problems (forward and inverse) $D^P$-complete. Beyond these, the source indicates — but does not prove — that boundary membership is $D^P$-complete and that membership in the complement of the relative interior is in coNP, with completeness for the latter neither claimed nor excluded; and the Karp-strength reductions linking the inverse problems to the forward and separation problems remain to be given explicitly. A refutation of any one of the components required above — one of the Karp-equivalences or one of the completeness placements — resolves the question equally: refuting a single component discharges part (1), and the remaining classification need not then be supplied.

(2) Direct versus oracle-based algorithms. Determine whether the inverse MILP admits an exact algorithm that does not rely on an oracle for the forward MILP. Either construct such a direct algorithm with a provable complexity guarantee — stated against the encoding length of the instance and the polyhedral complexity of $\mathrm{conv}(S^+)$, and never solving a forward MILP to optimality as a subroutine — or prove that oracle access to the forward problem is inherent. Fixing the formalization of 'direct' is part of the problem: the source poses the question only informally, and exponential-size single-level formulations via superadditive duality already exist, so a meaningful answer must pin down the resource bound against which directness is measured. The formalization and that bound must be stated explicitly and fixed before the algorithm or the lower bound is given, and the answer is appraised against them: invoking or re-encoding one of the existing single-level formulations, or declaring a bound that those formulations already satisfy, does not resolve the question.

References

1. Aykut Bulut and Ted K. Ralphs. On the Complexity of Inverse Mixed Integer Linear Optimization. SIAM Journal on Optimization, 31(4):3014–3043, 2021. DOI: 10.1137/20M1377369. arXiv:2104.09002. https://doi.org/10.1137/20M1377369
2. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics 2, Springer, second corrected edition, 1993. DOI: 10.1007/978-3-642-78240-4. https://link.springer.com/book/10.1007/978-3-642-78240-4
3. Ravindra K. Ahuja and James B. Orlin. Inverse optimization. Operations Research, 49(5):771–783, 2001. DOI: 10.1287/opre.49.5.771.10607. https://doi.org/10.1287/opre.49.5.771.10607
4. Lizhi Wang. Cutting plane algorithms for the inverse mixed integer linear programming problem. Operations Research Letters, 37(2):114–116, 2009. DOI: 10.1016/j.orl.2008.12.001. https://doi.org/10.1016/j.orl.2008.12.001
5. Andrew J. Schaefer. Inverse integer programming. Optimization Letters, 3(4):483–489, 2009. DOI: 10.1007/s11590-009-0131-z. https://doi.org/10.1007/s11590-009-0131-z
6. Jourdain B. Lamperski and Andrew J. Schaefer. A polyhedral characterization of the inverse-feasible region of a mixed-integer program. Operations Research Letters, 43(6):575–578, 2015. DOI: 10.1016/j.orl.2015.08.010. https://doi.org/10.1016/j.orl.2015.08.010
7. Merve Bodur, Timothy C. Y. Chan, and Ian Yihang Zhu. Inverse Mixed Integer Optimization: Polyhedral Insights and Trust Region Methods. INFORMS Journal on Computing, 34(3):1471–1488, 2022. DOI: 10.1287/ijoc.2021.1138. arXiv:2008.00301. https://doi.org/10.1287/ijoc.2021.1138
8. Christos H. Papadimitriou and Mihalis Yannakakis. The complexity of facets (and some facets of complexity). Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing (STOC '82), pages 255–260, 1982. DOI: 10.1145/800070.802199. https://doi.org/10.1145/800070.802199
9. Rui Chen and Haoran Zhu. The Complexity of Recognizing Facets for the Knapsack Polytope. Mathematics of Operations Research, 2025. DOI: 10.1287/moor.2024.0481. arXiv:2211.03311. https://doi.org/10.1287/moor.2024.0481
10. Timothy C. Y. Chan, Rafid Mahmood, and Ian Yihang Zhu. Inverse Optimization: Theory and Applications. Operations Research, 73(2):1046–1074, 2025. DOI: 10.1287/opre.2022.0382. arXiv:2109.03920. https://doi.org/10.1287/opre.2022.0382
11. Akira Kitaoka. Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs. arXiv:2607.22263, 2026. https://arxiv.org/abs/2607.22263
12. Clemens Heuberger. Inverse Combinatorial Optimization: A Survey on Problems, Methods, and Results. Journal of Combinatorial Optimization, 8(3):329–361, 2004. DOI: 10.1023/B:JOCO.0000038914.26975.9b. https://doi.org/10.1023/B:JOCO.0000038914.26975.9b
13. Ari J. Smith and Justin J. Boutilier. Gap-gradient methods for solving generalized mixed integer inverse optimization: an application to political gerrymandering. arXiv:2406.09457, 2024. https://arxiv.org/abs/2406.09457
14. Eva Ley and Maximilian Merkert. Solution methods for partial inverse combinatorial optimization problems in which weights can only be increased. Journal of Global Optimization, 93(1):263–298, 2025. DOI: 10.1007/s10898-025-01529-x. https://doi.org/10.1007/s10898-025-01529-x