IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v49y2001i5p771-783.html
   My bibliography  Save this article

Inverse Optimization

Author

Listed:
  • 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)

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.

Suggested Citation

  • Ravindra K. Ahuja & James B. Orlin, 2001. "Inverse Optimization," Operations Research, INFORMS, vol. 49(5), pages 771-783, October.
    • Handle: RePEc:inm:oropre:v:49:y:2001:i:5:p:771-783
    DOI: 10.1287/opre.49.5.771.10607
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.49.5.771.10607
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.49.5.771.10607?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Jianzhong Zhang & Mao Cai, 1998. "Inverse problem of minimum cuts," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 47(1), pages 51-58, February.
    2. P. T. Sokkalingam & Ravindra K. Ahuja & James B. Orlin, 1999. "Solving Inverse Spanning Tree Problems Through Network Flow Techniques," Operations Research, INFORMS, vol. 47(2), pages 291-298, April.
    3. Ravindra K. Ahuja & James B. Orlin, 2001. "A Fast Scaling Algorithm for Minimizing Separable Convex Functions Subject to Chain Constraints," Operations Research, INFORMS, vol. 49(5), pages 784-789, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Zhang, Jianzhong & Xu, Chengxian, 2010. "Inverse optimization for linearly constrained convex separable programming problems," European Journal of Operational Research, Elsevier, vol. 200(3), pages 671-679, February.
    2. Clemens Heuberger, 2004. "Inverse Combinatorial Optimization: A Survey on Problems, Methods, and Results," Journal of Combinatorial Optimization, Springer, vol. 8(3), pages 329-361, September.
    3. Ravindra K. Ahuja & Dorit S. Hochbaum & James B. Orlin, 2003. "Solving the Convex Cost Integer Dual Network Flow Problem," Management Science, INFORMS, vol. 49(7), pages 950-964, July.
    4. Stout, Quentin F., 2008. "Unimodal regression via prefix isotonic regression," Computational Statistics & Data Analysis, Elsevier, vol. 53(2), pages 289-297, December.
    5. Xianyue Li & Ruowang Yang & Heping Zhang & Zhao Zhang, 2022. "Partial inverse maximum spanning tree problem under the Chebyshev norm," Journal of Combinatorial Optimization, Springer, vol. 44(5), pages 3331-3350, December.
    6. Chung, Yerim & Culus, Jean-François & Demange, Marc, 2015. "Inverse chromatic number problems in interval and permutation graphs," European Journal of Operational Research, Elsevier, vol. 243(3), pages 763-773.
    7. Cui, Zhenyu & Lee, Chihoon & Zhu, Lingjiong & Zhu, Yunfan, 2021. "Non-convex isotonic regression via the Myersonian approach," Statistics & Probability Letters, Elsevier, vol. 179(C).
    8. Nguyen, Kien Trung & Hung, Nguyen Thanh, 2021. "The minmax regret inverse maximum weight problem," Applied Mathematics and Computation, Elsevier, vol. 407(C).
    9. Ahuja, Ravindra K., 1956- & Orlin, James B., 1953-, 1998. "Inverse optimization," Working papers WP 4003-98., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    10. Dorit S. Hochbaum, 2003. "Efficient Algorithms for the Inverse Spanning-Tree Problem," Operations Research, INFORMS, vol. 51(5), pages 785-797, October.
    11. M. Cai & X. Yang & Y. Li, 2000. "Inverse Problems of Submodular Functions on Digraphs," Journal of Optimization Theory and Applications, Springer, vol. 104(3), pages 559-575, March.
    12. Zhenhong Liu & Jianzhong Zhang, 2003. "On Inverse Problems of Optimum Perfect Matching," Journal of Combinatorial Optimization, Springer, vol. 7(3), pages 215-228, September.
    13. Qie He & Stefan Irnich & Yongjia Song, 2019. "Branch-and-Cut-and-Price for the Vehicle Routing Problem with Time Windows and Convex Node Costs," Transportation Science, INFORMS, vol. 53(5), pages 1409-1426, September.
    14. Xiucui Guan & Xinyan He & Panos M. Pardalos & Binwu Zhang, 2017. "Inverse max $$+$$ + sum spanning tree problem under Hamming distance by modifying the sum-cost vector," Journal of Global Optimization, Springer, vol. 69(4), pages 911-925, December.
    15. Xianyue Li & Xichao Shu & Huijing Huang & Jingjing Bai, 2019. "Capacitated partial inverse maximum spanning tree under the weighted Hamming distance," Journal of Combinatorial Optimization, Springer, vol. 38(4), pages 1005-1018, November.
    16. Zhang, Jianzhong & Liu, Zhenhong & Ma, Zhongfan, 2000. "Some reverse location problems," European Journal of Operational Research, Elsevier, vol. 124(1), pages 77-88, July.
    17. Adrian Deaconu & Laura Ciupala, 2020. "Inverse Minimum Cut Problem with Lower and Upper Bounds," Mathematics, MDPI, vol. 8(9), pages 1-10, September.
    18. Rishabh Gupta & Qi Zhang, 2022. "Decomposition and Adaptive Sampling for Data-Driven Inverse Linear Optimization," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2720-2735, September.
    19. Hughes, Michael S. & Lunday, Brian J., 2022. "The Weapon Target Assignment Problem: Rational Inference of Adversary Target Utility Valuations from Observed Solutions," Omega, Elsevier, vol. 107(C).
    20. Dorit S. Hochbaum, 2004. "50th Anniversary Article: Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today," Management Science, INFORMS, vol. 50(6), pages 709-723, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:49:y:2001:i:5:p:771-783. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.