Inverse Optimization

Ravindra K. Ahuja () and James B. Orlin ()
Additional contact information
Ravindra K. Ahuja: Industrial and Systems Engineering Department, University of Florida, Gainesville, Florida 32611
James B. Orlin: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Operations Research, 2001, vol. 49, issue 5, 771-783

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 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 = (Sigma) i(in)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 (infinity) norm (where || d - c || p = max j(in)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 (infinity) 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 (infinity) 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.

Keywords: Programming; linear: inverse linear programming problems; Networks/graphs; flow algorithms: inverse shortest path; minimum cut; minimum cost flows; Transportation; mass transit: toll pricing in mass transportation networks (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (65)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.49.5.771.10607 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:49:y:2001:i:5:p:771-783

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().