Inverse Optimization
Top Cited Papers
- 1 October 2001
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 49 (5), 771-783
- https://doi.org/10.1287/opre.49.5.771.10607
Abstract
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 x0 be a given feasible solution. The solution x0 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 x0 is an optimal solution of P with respect to d and ‖d−c‖p is minimum, where ‖d−c‖p is some selected Lp norm. In this paper, we consider the inverse linear programming problem under L1 norm (where ‖d−c‖p = Σi∈J wj|dj−cj|, with J denoting the index set of variables xj and wj denoting the weight of the variable j) and under L∞ norm (where ‖d−c‖p = maxj∈J{wj|dj−cj|}). We prove the following results: (i) If the problem P is a linear programming problem, then its inverse problem under the L1 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 L1 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 L1 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 L1 and L∞ norms are also polynomially solvable.Keywords
Other Versions
This publication has 22 references indexed in Scilit:
- A Faster Algorithm for the Inverse Spanning Tree ProblemJournal of Algorithms, 2000
- Beyond the flow decomposition barrierJournal of the ACM, 1998
- Inverse problem of minimum cutsMathematical Methods of Operations Research, 1998
- Inverse maximum flow and minimum cut problemsOptimization, 1997
- Calculating some inverse linear programming problemsJournal of Computational and Applied Mathematics, 1996
- Scaling Algorithms for the Shortest Paths ProblemSIAM Journal on Computing, 1995
- An inverse problem of the weighted shortest path problemJapan Journal of Industrial and Applied Mathematics, 1995
- Faster Scaling Algorithms for Network ProblemsSIAM Journal on Computing, 1989
- Efficient dual simplex algorithms for the assignment problemMathematical Programming, 1985
- A characterization of the minimum cycle mean in a digraphDiscrete Mathematics, 1978