×

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
PDF BibTeX Cite
Full Text: DOI