Inverse Optimization, Part I: Linear Programming and General Problem
Ravindra K. Ahuja, James B. Orlin · 1998
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 x 0 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 x 0 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