IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v36y2024i3p900-917.html
   My bibliography  Save this article

Approximate Kernel Learning Uncertainty Set for Robust Combinatorial Optimization

Author

Listed:
  • Benoît Loger

    (IMT Atlantique, LS2N, 44300 Nantes, France)

  • Alexandre Dolgui

    (IMT Atlantique, LS2N, 44300 Nantes, France)

  • Fabien Lehuédé

    (IMT Atlantique, LS2N, 44300 Nantes, France)

  • Guillaume Massonnet

    (IMT Atlantique, LS2N, 44300 Nantes, France)

Abstract

Support vector clustering (SVC) has been proposed in the literature as a data-driven approach to build uncertainty sets in robust optimization. Unfortunately, the resulting SVC-based uncertainty sets induces a large number of additional variables and constraints in the robust counterpart of mathematical formulations. We propose a two-phase method to approximate the resulting uncertainty sets and overcome these tractability issues. This method is controlled by a parameter defining a trade-off between the quality of the approximation and the complexity of the robust models formulated. We evaluate the approximation method on three distinct, well-known optimization problems. Experimental results show that the approximated uncertainty set leads to solutions that are comparable to those obtained with the classic SVC-based uncertainty set with a significant reduction of the computation time.

Suggested Citation

  • 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.
  • Handle: RePEc:inm:orijoc:v:36:y:2024:i:3:p:900-917
    DOI: 10.1287/ijoc.2022.0330
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.0330
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2022.0330?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. Han, Biao & Shang, Chao & Huang, Dexian, 2021. "Multiple kernel learning-aided robust optimization: Learning algorithm, computational tractability, and usage in multi-stage decision-making," European Journal of Operational Research, Elsevier, vol. 292(3), pages 1004-1018.
    2. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    3. Shen, Feifei & Zhao, Liang & Du, Wenli & Zhong, Weimin & Qian, Feng, 2020. "Large-scale industrial energy systems optimization under uncertainty: A data-driven robust optimization approach," Applied Energy, Elsevier, vol. 259(C).
    4. 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.
    5. Chassein, André & Dokka, Trivikram & Goerigk, Marc, 2019. "Algorithms and uncertainty sets for data-driven robust shortest path problems," European Journal of Operational Research, Elsevier, vol. 274(2), pages 671-686.
    6. 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)

    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. 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.
    3. 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.
    4. 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.
    5. 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.
    6. Mahdi Hamzeei & Alvin Lim & Jiefeng Xu, 2022. "Robust price optimization of multiple products under interval uncertainties," Journal of Revenue and Pricing Management, Palgrave Macmillan, vol. 21(4), pages 442-454, August.
    7. Shaojian Qu & Yuting Xu & Ying Ji & Can Feng & Jinpeng Wei & Shan Jiang, 2022. "Data-Driven Robust Data Envelopment Analysis for Evaluating the Carbon Emissions Efficiency of Provinces in China," Sustainability, MDPI, vol. 14(20), pages 1-26, October.
    8. Soyster, A.L. & Murphy, F.H., 2017. "Data driven matrix uncertainty for robust linear programming," Omega, Elsevier, vol. 70(C), pages 43-57.
    9. Alireza Ghahtarani & Ahmed Saif & Alireza Ghasemi, 2021. "Robust Portfolio Selection Problems: A Comprehensive Review," Papers 2103.13806, arXiv.org, revised Jan 2022.
    10. Seulgi Joung & Seyoung Oh & Kyungsik Lee, 2023. "Comparative analysis of linear programming relaxations for the robust knapsack problem," Annals of Operations Research, Springer, vol. 323(1), pages 65-78, April.
    11. Li, Xingchen & Xu, Guangcheng & Wu, Jie & Xu, Chengzhen & Zhu, Qingyuan, 2024. "Evaluation of bank efficiency by considering the uncertainty of nonperforming loans," Omega, Elsevier, vol. 126(C).
    12. Zhi Chen & Melvyn Sim & Huan Xu, 2019. "Distributionally Robust Optimization with Infinitely Constrained Ambiguity Sets," Operations Research, INFORMS, vol. 67(5), pages 1328-1344, September.
    13. Stefan Mišković, 2017. "A VNS-LP algorithm for the robust dynamic maximal covering location problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(4), pages 1011-1033, October.
    14. Jeong, Jaehee & Premsankar, Gopika & Ghaddar, Bissan & Tarkoma, Sasu, 2024. "A robust optimization approach for placement of applications in edge computing considering latency uncertainty," Omega, Elsevier, vol. 126(C).
    15. Chassein, André & Dokka, Trivikram & Goerigk, Marc, 2019. "Algorithms and uncertainty sets for data-driven robust shortest path problems," European Journal of Operational Research, Elsevier, vol. 274(2), pages 671-686.
    16. M. J. Naderi & M. S. Pishvaee, 2017. "Robust bi-objective macroscopic municipal water supply network redesign and rehabilitation," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 31(9), pages 2689-2711, July.
    17. Shen, Feifei & Zhao, Liang & Wang, Meihong & Du, Wenli & Qian, Feng, 2022. "Data-driven adaptive robust optimization for energy systems in ethylene plant under demand uncertainty," Applied Energy, Elsevier, vol. 307(C).
    18. Baringo, Luis & Boffino, Luigi & Oggioni, Giorgia, 2020. "Robust expansion planning of a distribution system with electric vehicles, storage and renewable units," Applied Energy, Elsevier, vol. 265(C).
    19. Xuejie Bai & Yankui Liu, 2016. "Robust optimization of supply chain network design in fuzzy decision system," Journal of Intelligent Manufacturing, Springer, vol. 27(6), pages 1131-1149, December.
    20. Zhang, Wei & (Ato) Xu, Wangtu, 2017. "Simulation-based robust optimization for the schedule of single-direction bus transit route: The design of experiment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 203-230.

    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:orijoc:v:36:y:2024:i:3:p:900-917. 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.