IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v55y2013i3p491-506.html
   My bibliography  Save this article

Branch-and-bound algorithms for the partial inverse mixed integer linear programming problem

Author

Listed:
  • Lizhi Wang

Abstract

This paper presents branch-and-bound algorithms for the partial inverse mixed integer linear programming (PInvMILP) problem, which is to find a minimal perturbation to the objective function of a mixed integer linear program (MILP), measured by some norm, such that there exists an optimal solution to the perturbed MILP that also satisfies an additional set of linear constraints. This is a new extension to the existing inverse optimization models. Under the weighted $$L_1$$ and $$L_\infty $$ norms, the presented algorithms are proved to finitely converge to global optimality. In the presented algorithms, linear programs with complementarity constraints (LPCCs) need to be solved repeatedly as a subroutine, which is analogous to repeatedly solving linear programs for MILPs. Therefore, the computational complexity of the PInvMILP algorithms can be expected to be much worse than that of MILP or LPCC. Computational experiments show that small-sized test instances can be solved within a reasonable time period. Copyright Springer Science+Business Media New York 2013

Suggested Citation

  • Lizhi Wang, 2013. "Branch-and-bound algorithms for the partial inverse mixed integer linear programming problem," Journal of Global Optimization, Springer, vol. 55(3), pages 491-506, March.
    • Handle: RePEc:spr:jglopt:v:55:y:2013:i:3:p:491-506
    DOI: 10.1007/s10898-013-0036-3
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10898-013-0036-3
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10898-013-0036-3?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. C. Audet & G. Savard & W. Zghal, 2007. "New Branch-and-Cut Algorithm for Bilevel Linear Programming," Journal of Optimization Theory and Applications, Springer, vol. 134(2), pages 353-370, August.
    2. Dial, Robert B., 1999. "Minimal-revenue congestion pricing part I: A fast algorithm for the single-origin case," Transportation Research Part B: Methodological, Elsevier, vol. 33(3), pages 189-202, April.
    3. Shimon Awerbuch, 2006. "Portfolio-Based Electricity Generation Planning: Policy Implications For Renewables And Energy Security," Mitigation and Adaptation Strategies for Global Change, Springer, vol. 11(3), pages 693-710, May.
    4. Wang, Lizhi & Mazumdar, Mainak & Bailey, Matthew D. & Valenzuela, Jorge, 2007. "Oligopoly models for market price of electricity under demand uncertainty and unit reliability," European Journal of Operational Research, Elsevier, vol. 181(3), pages 1309-1321, September.
    5. Omar Ben-Ayed & Charles E. Blair, 1990. "Computational Difficulties of Bilevel Linear Programming," Operations Research, INFORMS, vol. 38(3), pages 556-560, June.
    6. Zhaoyang Duan & Lizhi Wang, 2011. "Heuristic algorithms for the inverse mixed integer linear programming problem," Journal of Global Optimization, Springer, vol. 51(3), pages 463-471, November.
    7. Damian R. Beil & Lawrence M. Wein, 2003. "An Inverse-Optimization-Based Auction Mechanism to Support a Multiattribute RFQ Process," Management Science, INFORMS, vol. 49(11), pages 1529-1545, November.
    8. Dial, Robert B., 2000. "Minimal-revenue congestion pricing Part II: An efficient algorithm for the general case," Transportation Research Part B: Methodological, Elsevier, vol. 34(8), pages 645-665, November.
    9. 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.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Keji Wei & Vikrant Vaze, 2018. "Modeling Crew Itineraries and Delays in the National Air Transportation System," Transportation Science, INFORMS, vol. 52(5), pages 1276-1296, October.

    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. Zhaoyang Duan & Lizhi Wang, 2011. "Heuristic algorithms for the inverse mixed integer linear programming problem," Journal of Global Optimization, Springer, vol. 51(3), pages 463-471, November.
    2. Sheu, Jiuh-Biing & Yang, Hai, 2008. "An integrated toll and ramp control methodology for dynamic freeway congestion management," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 387(16), pages 4327-4348.
    3. Timothy C. Y. Chan & Tim Craig & Taewoo Lee & Michael B. Sharpe, 2014. "Generalized Inverse Multiobjective Optimization with Application to Cancer Therapy," Operations Research, INFORMS, vol. 62(3), pages 680-695, June.
    4. Zeynep Erkin & Matthew D. Bailey & Lisa M. Maillart & Andrew J. Schaefer & Mark S. Roberts, 2010. "Eliciting Patients' Revealed Preferences: An Inverse Markov Decision Process Approach," Decision Analysis, INFORMS, vol. 7(4), pages 358-365, December.
    5. Yang, Hai & Wang, Xiaolei, 2011. "Managing network mobility with tradable credits," Transportation Research Part B: Methodological, Elsevier, vol. 45(3), pages 580-594, March.
    6. Harks, Tobias & Schröder, Marc & Vermeulen, Dries, 2019. "Toll caps in privatized road networks," European Journal of Operational Research, Elsevier, vol. 276(3), pages 947-956.
    7. Zhang, H. M. & Ge, Y. E., 2004. "Modeling variable demand equilibrium under second-best road pricing," Transportation Research Part B: Methodological, Elsevier, vol. 38(8), pages 733-749, September.
    8. Jiashan Wang & Yingying Kang & Changhyun Kwon & Rajan Batta, 2012. "Dual Toll Pricing for Hazardous Materials Transport with Linear Delay," Networks and Spatial Economics, Springer, vol. 12(1), pages 147-165, March.
    9. Cheng, Chi-Bin, 2011. "Reverse auction with buyer-supplier negotiation using bi-level distributed programming," European Journal of Operational Research, Elsevier, vol. 211(3), pages 601-611, June.
    10. Yang, Hai & Huang, Hai-Jun, 2004. "The multi-class, multi-criteria traffic network equilibrium and systems optimum problem," Transportation Research Part B: Methodological, Elsevier, vol. 38(1), pages 1-15, January.
    11. 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.
    12. Yang, Hai & Zhang, Xiaoning & Meng, Qiang, 2004. "Modeling private highways in networks with entry-exit based toll charges," Transportation Research Part B: Methodological, Elsevier, vol. 38(3), pages 191-213, March.
    13. Penchina, Claude M., 2004. "Minimal-revenue congestion pricing: some more good-news and bad-news," Transportation Research Part B: Methodological, Elsevier, vol. 38(6), pages 559-570, July.
    14. 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.
    15. Zhou, Ying & Wang, Lizhi & McCalley, James D., 2011. "Designing effective and efficient incentive policies for renewable energy in generation expansion planning," Applied Energy, Elsevier, vol. 88(6), pages 2201-2209, June.
    16. Han, Deren & Lo, Hong K. & Sun, Jie & Yang, Hai, 2008. "The toll effect on price of anarchy when costs are nonlinear and asymmetric," European Journal of Operational Research, Elsevier, vol. 186(1), pages 300-316, April.
    17. Stewart, Kathryn, 2007. "Tolling traffic links under stochastic assignment: Modelling the relationship between the number and price level of tolled links and optimal traffic flows," Transportation Research Part A: Policy and Practice, Elsevier, vol. 41(7), pages 644-654, August.
    18. Merve Bodur & Timothy C. Y. Chan & Ian Yihang Zhu, 2022. "Inverse Mixed Integer Optimization: Polyhedral Insights and Trust Region Methods," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1471-1488, May.
    19. Rambha, Tarun & Boyles, Stephen D. & Unnikrishnan, Avinash & Stone, Peter, 2018. "Marginal cost pricing for system optimal traffic assignment with recourse under supply-side uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 110(C), pages 104-121.
    20. Libura, Marek, 2007. "On the adjustment problem for linear programs," European Journal of Operational Research, Elsevier, vol. 183(1), pages 125-134, November.

    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:spr:jglopt:v:55:y:2013:i:3:p:491-506. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.