Inverse optimization

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(0) 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 parallel tod - c parallel to (p) is minimum, where parallel tod - c parallel to (p) is some selected L-p norm. In this paper, we consider the inverse linear programming problem under L-1 norm (where parallel tod - c parallel to (p) = Sigma (t epsilon integral) omega (integral) \d(integral) - c(integral)\ with J denoting the index set of variables x(j) and w(j) denoting the weight of the variable j) and under L-infinity norm (where parallel tod - c parallel to (p) = max(j epsilonJ) (w(j)\d(j) - c(j)\}). We prove. the following results (i) If the problem P is a linear programming problem, then its inverse problem under the L, as well as L. norm is also a linear programming problem. (ii) If the problem P is a shortest path, assignment or minimum cut problem, then its inverse problem under the L, norm and unit weights can be solved by solving a problem of the same kind. For the nonunit weight case, the inverse problem reduces to solving a minimum cost flow problem. (iii) If the problem P is a minimum cost flow problem, then its inverse problem under the L, norm and unit weights reduces to solving a unit-capacity minimum cost flow problem. For the nonunit weight case, the inverse problem reduces to solving a minimum cost flow problem. (iv) If the problem P is a minimum cost flow problem, then its inverse problem under the L. norm and unit weights reduces to solving a minimum mean cycle problem. For the nonunit weight case, the inverse problem reduces to solving a minimum cost-to-time. ratio cycle problem. (v) If the problem P is polynomially solvable for linear cost functions, then inverse versions of P under the. L-1 and L-infinity norms are also polynomially solvable.