Inverse optimization is the problem of determining the values of missing input parameters that are closest to given estimates and that will make a given solution optimal. This study is concerned with the relationship of a particular inverse mixed integer linear optimization problem (MILPs) to both the original problem and the separation problem associated with its feasible region. We show that the decision version of the inverse MILP is coNP-complete (extending the result of Ahuja and Orlin to the discrete case) and that the optimal value verification problem for both the inverse problem and the associated forward problem are both complete for the complexity class D^P. We also describe a cutting plane algorithm for solving inverse MILPs that illustrates the close relationship between the inverse problem and the separation problem for the convex hull of solutions to the forward problem. The inverse problem is shown to be equivalent to the separation problem for the radial cone defined by all inequalities valid for the convex hull of solutions to the MILP that are binding at the solution serving as input to the inverse problem. Thus, the inverse, forward, and separation problems can be said to be equivalent.
Citation
Laboratory for Computational Research at Lehigh (COR@L) Technical Report 15T-001-R4
Article
View On the Complexity of Inverse Mixed Integer Linear Optimization