On the Complexity of Inverse Mixed Integer Linear Optimization
Aykut Bulut (aykutlehigh.edu)
Abstract: 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 target solution optimal. This study is concerned with inverse mixed integer linear optimization problems (MILPs) in which the missing parameters are objective function coefficients. This class generalizes the class studied by Ahuja and Orlin, who showed that inverse linear optimization problems can be solved in polynomial time under mild conditions. We extend their result to the discrete case and show that the decision version of the inverse MILP is coNP-complete, while the optimal value verification problem is D_p-complete. We derive a cutting plane algorithm for solving inverse MILPs and show that there is a close relationship between the inverse problem and the well-known separation problem in both a complexity and an algorithmic sense.
Keywords: Inverse optimization, mixed integer linear optimization, computational complexity, polynomial hierarchy
Category 1: Integer Programming ((Mixed) Integer Linear Programming )
Category 2: Integer Programming (Cutting Plane Approaches )
Citation: COR@L Laboratory Report 15T-001-R1, Department of Industrial and Systems Engineering, Lehigh University.
Entry Submitted: 08/09/2015
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|