  


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 coNPcomplete, while the optimal value verification problem is D_pcomplete. We derive a cutting plane algorithm for solving inverse MILPs and show that there is a close relationship between the inverse problem and the wellknown 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 15T001R1, Department of Industrial and Systems Engineering, Lehigh University. Download: [PDF] Entry Submitted: 08/09/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  