Answers are grounded in this paper and cite their sources.
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 ‖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 (where ‖d−c‖ p = Σ i∈J w j |d j −c j |, with J denoting the index set of variables x j and w j denoting the weight of the variable j) and under L ∞ norm (where ‖d−c‖ p = max j∈J {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 1 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 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 ∞ 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 ∞ norms are also polynomially solvable.
No takes yet. Share an insight, caveat, or question.
Ahuja et al. (2001) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: