  


The Inverse Optimal Value Problem
Shabbir Ahmed (sahmedisye.gatech.edu) Abstract: This paper considers the following inverse optimization problem: given a linear program, a desired optimal objective value, and a set of feasible cost coefficients, determine a costcoefficient vector such that the corresponding optimal objective value of the linear program is closest to the given value. The above problem, referred here as the inverse optimal value problem, is significantly different from standard inverse optimization problems that involve determining a cost coefficient vector for a linear program such that a prespecified solution vector is optimal. In this paper, we show that the inverse optimal value problem is NPhard in general. We identify conditions under which the problem reduces to a concave maximization or a concave minimization problem. We provide sufficient conditions under which the associated concave minimization problem and, correspondingly, the inverse optimal value problem is polynomially solvable. For the case when the set of feasible cost coefficients is polyhedral, we describe an algorithm for the inverse optimal value problem based on solving linear and bilinear programming problems. Some preliminary computational experience is reported. Keywords: Inverse optimization, Complexity, Linear programming, Bilinear programming. Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 2: Global Optimization Category 3: Linear, Cone and Semidefinite Programming (Other ) Citation: Technical Report, School of Industrial & Systems Engineering, Georgia Institute of Technology, 2002. Download: [PDF] Entry Submitted: 07/22/2002 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  