IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v70y2017icp43-57.html
   My bibliography  Save this article

Data driven matrix uncertainty for robust linear programming

Author

Listed:
  • Soyster, A.L.
  • Murphy, F.H.

Abstract

In this paper we consider robust linear programs with uncertainty sets defined by the convex hull of a finite number of m×n matrices. Embedded within the matrices are related robust linear programs defined by the rows, columns, and coefficients of the matrices. This results in a nested set of primal (and dual) linear programs with predictably different optimal objective values. The set of matrices also embed a covariance structure for the matrix coefficients and we show that when negative covariances predominate in the rows, more favorable optimal objective values for the primal can be expected.

Suggested Citation

  • Soyster, A.L. & Murphy, F.H., 2017. "Data driven matrix uncertainty for robust linear programming," Omega, Elsevier, vol. 70(C), pages 43-57.
    • Handle: RePEc:eee:jomega:v:70:y:2017:i:c:p:43-57
    DOI: 10.1016/j.omega.2016.09.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048316305941
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2016.09.001?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. Gilbert Laporte & François Louveaux & Hélène Mercure, 1992. "The Vehicle Routing Problem with Stochastic Travel Times," Transportation Science, INFORMS, vol. 26(3), pages 161-170, August.
    2. Murthy Mudrageda & Frederic H. Murphy, 2008. "OR PRACTICE---An Economic Equilibrium Model of the Market for Marine Transportation Services in Petroleum Products," Operations Research, INFORMS, vol. 56(2), pages 278-285, April.
    3. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    4. A. Charnes & W. W. Cooper, 1959. "Chance-Constrained Programming," Management Science, INFORMS, vol. 6(1), pages 73-79, October.
    5. Thanh Luong & Frederic H. Murphy & Reginald Sanders & Susan H. Holte & Peter Whitman, 1998. "Modeling the Impacts of the 1990 Clean Air Act Amendments," Interfaces, INFORMS, vol. 28(2), pages 1-15, April.
    6. David J. Thuente, 1980. "Technical Note—Duality Theory for Generalized Linear Programs with Computational Methods," Operations Research, INFORMS, vol. 28(4), pages 1005-1011, August.
    7. Soyster, A.L. & Murphy, F.H., 2013. "A unifying framework for duality and modeling in robust linear programs," Omega, Elsevier, vol. 41(6), pages 984-997.
    8. Frederic H. Murphy & Reginald C. Sanders & Susan H. Shaw & Richard L. Thrasher, 1981. "Modeling Natural Gas Regulatory Proposals Using the Project Independence Evaluation System," Operations Research, INFORMS, vol. 29(5), pages 876-902, October.
    9. A. L. Soyster, 1973. "Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming," Operations Research, INFORMS, vol. 21(5), pages 1154-1157, October.
    10. Gorissen, Bram L. & Yanıkoğlu, İhsan & den Hertog, Dick, 2015. "A practical guide to robust optimization," Omega, Elsevier, vol. 53(C), pages 124-137.
    11. Julia L. Higle & Suvrajeet Sen, 1991. "Stochastic Decomposition: An Algorithm for Two-Stage Linear Programs with Recourse," Mathematics of Operations Research, INFORMS, vol. 16(3), pages 650-669, August.
    12. Joyce W. Yen & John R. Birge, 2006. "A Stochastic Programming Approach to the Airline Crew Scheduling Problem," Transportation Science, INFORMS, vol. 40(1), pages 3-14, February.
    13. Soyster, A. L. & Gordon, R. L. & Enscore, E. E. & We, Y., 1985. "An evaluation of the competitiveness of the US coal market," Energy Economics, Elsevier, vol. 7(1), pages 3-8, January.
    14. Dimitris Bertsimas & David B. Brown, 2009. "Constructing Uncertainty Sets for Robust Linear Optimization," Operations Research, INFORMS, vol. 57(6), pages 1483-1495, December.
    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. Xiang, Xi & Liu, Changchun, 2021. "An almost robust optimization model for integrated berth allocation and quay crane assignment problem," Omega, Elsevier, vol. 104(C).
    2. Feng Yang & Zhong Wu & Xiaoyan Teng & Shaojian Qu, 2022. "Robust Counterpart Models for Fresh Agricultural Product Routing Planning Considering Carbon Emissions and Uncertainty," Sustainability, MDPI, vol. 14(22), pages 1-17, November.
    3. Xiang, Xi & Liu, Changchun, 2021. "An expanded robust optimisation approach for the berth allocation problem considering uncertain operation time," Omega, Elsevier, vol. 103(C).
    4. Jianhui Du & Peng Wu & Yiqing Wang & Dan Yang, 2023. "Multi-stage humanitarian emergency logistics: robust decisions in uncertain environment," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 115(1), pages 899-922, January.

    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. Wenqing Chen & Melvyn Sim & Jie Sun & Chung-Piaw Teo, 2010. "From CVaR to Uncertainty Set: Implications in Joint Chance-Constrained Optimization," Operations Research, INFORMS, vol. 58(2), pages 470-485, April.
    2. Sun, Hao & Yang, Jun & Yang, Chao, 2019. "A robust optimization approach to multi-interval location-inventory and recharging planning for electric vehicles," Omega, Elsevier, vol. 86(C), pages 59-75.
    3. Antonio G. Martín & Manuel Díaz-Madroñero & Josefa Mula, 2020. "Master production schedule using robust optimization approaches in an automobile second-tier supplier," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 28(1), pages 143-166, March.
    4. Mehdi Ansari & Juan S. Borrero & Leonardo Lozano, 2023. "Robust Minimum-Cost Flow Problems Under Multiple Ripple Effect Disruptions," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 83-103, January.
    5. Wang, Tian & Deng, Shiming, 2019. "Multi-Period energy procurement policies for smart-grid communities with deferrable demand and supplementary uncertain power supplies," Omega, Elsevier, vol. 89(C), pages 212-226.
    6. Chassein, André & Goerigk, Marc, 2018. "Variable-sized uncertainty and inverse problems in robust optimization," European Journal of Operational Research, Elsevier, vol. 264(1), pages 17-28.
    7. Moret, Stefano & Babonneau, Frédéric & Bierlaire, Michel & Maréchal, François, 2020. "Overcapacity in European power systems: Analysis and robust optimization approach," Applied Energy, Elsevier, vol. 259(C).
    8. Robin Vujanic & Paul Goulart & Manfred Morari, 2016. "Robust Optimization of Schedules Affected by Uncertain Events," Journal of Optimization Theory and Applications, Springer, vol. 171(3), pages 1033-1054, December.
    9. Andrew J. Keith & Darryl K. Ahner, 2021. "A survey of decision making and optimization under uncertainty," Annals of Operations Research, Springer, vol. 300(2), pages 319-353, May.
    10. Claire Nicolas & Stéphane Tchung-Ming & Emmanuel Hache, 2016. "Energy transition in transportation under cost uncertainty, an assessment based on robust optimization," Working Papers hal-02475943, HAL.
    11. Marla, Lavanya & Rikun, Alexander & Stauffer, Gautier & Pratsini, Eleni, 2020. "Robust modeling and planning: Insights from three industrial applications," Operations Research Perspectives, Elsevier, vol. 7(C).
    12. Andreas Thorsen & Tao Yao, 2017. "Robust inventory control under demand and lead time uncertainty," Annals of Operations Research, Springer, vol. 257(1), pages 207-236, October.
    13. Aura Jalal & Aldair Alvarez & Cesar Alvarez-Cruz & Jonathan La Vega & Alfredo Moreno, 2023. "The robust multi-plant capacitated lot-sizing problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 31(2), pages 302-330, July.
    14. Güray Kara & Ayşe Özmen & Gerhard-Wilhelm Weber, 2019. "Stability advances in robust portfolio optimization under parallelepiped uncertainty," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(1), pages 241-261, March.
    15. Kramer, Anja & Krebs, Vanessa & Schmidt, Martin, 2021. "Strictly and Γ-robust counterparts of electricity market models: Perfect competition and Nash–Cournot equilibria," Operations Research Perspectives, Elsevier, vol. 8(C).
    16. Schrotenboer, Albert H. & Wenneker, Rob & Ursavas, Evrim & Zhu, Stuart X., 2023. "Reliable reserve-crew scheduling for airlines," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 178(C).
    17. Curcio, Eduardo & Amorim, Pedro & Zhang, Qi & Almada-Lobo, Bernardo, 2018. "Adaptation and approximate strategies for solving the lot-sizing and scheduling problem under multistage demand uncertainty," International Journal of Production Economics, Elsevier, vol. 202(C), pages 81-96.
    18. Zhang, Yu & Tang, Jiafu, 2018. "A robust optimization approach for itinerary planning with deadline," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 113(C), pages 56-74.
    19. Bruni, M.E. & Di Puglia Pugliese, L. & Beraldi, P. & Guerriero, F., 2017. "An adjustable robust optimization model for the resource-constrained project scheduling problem with uncertain activity durations," Omega, Elsevier, vol. 71(C), pages 66-84.
    20. Benoît Loger & Alexandre Dolgui & Fabien Lehuédé & Guillaume Massonnet, 2024. "Approximate Kernel Learning Uncertainty Set for Robust Combinatorial Optimization," INFORMS Journal on Computing, INFORMS, vol. 36(3), pages 900-917, May.

    More about this item

    Statistics

    Access and download statistics

    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:eee:jomega:v:70:y:2017:i:c:p:43-57. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description .

    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.