- | ||||
|
![]()
|
The Inverse Optimal Value Problem
Shabbir Ahmed (sahmed 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 cost-coefficient 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 pre-specified solution vector is optimal. In this paper, we show that the inverse optimal value problem is NP-hard 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 | |
![]() |