Optimization Online


On the Complexity of Inverse Mixed Integer Linear Optimization

Aykut Bulut (aykut***at***lehigh.edu)
Ted Ralphs (ted***at***lehigh.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.

Download: [PDF]

Entry Submitted: 08/09/2015
Entry Accepted: 08/10/2015
Entry Last Modified: 11/02/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society