Inverse optimization problems are bilevel optimization problems in which the leader modifies the follower’s objective such that a prescribed feasible solution becomes an optimal solution of the follower. They capture hierarchical decision-making problems like parameter estimation tasks or situations where a planner wants to steer an agent’s choice.
In this work, we study integral inverse optimization problems, in which the leader’s cost modifications must be integral. We focus on the version where the modifications are minimized with respect to the (\ell_1\)-norm. Adding this integrality constraint for the cost modifications changes the optimal objective value for some inverse optimization problems like the inverse linear program, the inverse min weight perfect matching problem, the inverse knapsack problem and the inverse travelling salesman problem. In contrast, others like the inverse shortest path problem, the inverse assignment problem, the inverse min cut problem or the inverse min spanning tree problem have optimal integral solutions if all original weights are integer. Interestingly, the integrality constraint does not affect the complexity of the problem in many cases. For instance, we prove that (primal bound verification for) integral inverse mixed-integer linear optimization lies in coNP, similar to (continuous) inverse mixed-integer linear optimization. Thus, for example, the integral inverse knapsack problem is coNP-complete. In contrast to the continuous inverse problem, the optimal objective values of the optimistic and pessimistic version of the integral inverse problem can be arbitrarily far apart.