zbMATH — the first resource for mathematics

Inverse optimization. (English) Zbl 1163.90764
Summary: 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 ||$$d-c||_{p}$$ is minimum, where ||$$d-c||_{p}$$ is some selected $$L_{p}$$ norm. In this paper, we consider the inverse linear programming problem under $$L_{1}$$ norm and under $$L_{\infty}$$ norm. We prove the following results: (i) If the problem P is a linear programming problem, then its inverse problem under the $$L_{1}$$ as well as $$L_{\infty}$$ 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_{1}$$ 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_{1}$$ 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_{\infty}$$ 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_{\infty}$$ norms are also polynomially solvable.

MSC:
 90C35 Programming involving graphs or networks 90C46 Optimality conditions and duality in mathematical programming
Full Text: