Inverse Optimization, Part I: Linear Programming and General Problem
Inverse Optimization, Part I: Linear Programming and General Problem
复制标题
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
R. Ahuja;J. Orlin
中科院分区：
文献类型：
--
作者：
R. Ahuja;J. Orlin
In this paper, we study inverse optimization problems defined as follows: Let S denote the set of feasible solutions of an optimization problem P, let c be a specified cost vector, and x0 be a given feasible solution. The solution x° may or may not be an optimal solution of P with respect to the cost vector c. The inverse optimization problem is to perturb the cost vector c to d so that x0 is an optimal solution of P with respect to d and lid clip is minimum, where lid clip is some selected Lp norm. In this paper, we consider the inverse linear programming problem under the L 1 norm (where we minimize Ejj ldj -cj, with J denoting the index set of variables xj) and under the Lo norm (where we minimize max{ldj cjl: j E J}). We show that the dual of the inverse linear programming problem with the L 1 norm reduces to a modification of the original problem obtained by eliminating the non-binding constraints (with respect to x) and imposing the following additional lower and upper bound constraints: Ixj xj < 1 for all j J. We next study the inverse linear programming problem with the Loo norm and show that its dual reduces to a modification of the original problem obtained by eliminating the non-binding constraints (with respect to x) and imposing the following single additional constraint: jEj xj x9° < 1. Finally, we show that (under reasonable regularity conditions) if the problem P is polynomially solvable then the inverse versions of P under L1 and L, norms are also polynomially solvable. This result uses ideas from the ellipsoid algorithm and, therefore, does not lead to combinatorial algorithms for solving inverse optimization problems. 1 Sloan School of Management, MIT, Cambridge, MA 02139, USA; On leave from Indian Institute of Technology, Kanpur 208 016, INDIA. 2 Sloan School of Management, MIT, Cambridge, MA 02139, USA.
