The Inverse Optimal Value Problem

Shabbir Ahmed (sahmedisye.gatech.edu)
Yongpei Guan (guanypisye.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 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
Entry Accepted: 07/22/2002
Entry Last Modified: 07/22/2002

Modify/Update this entry