IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v278y2019i1p136-148.html
   My bibliography  Save this article

Robust recoverable 0–1 optimization problems under polyhedral uncertainty

Author

Listed:
  • Hradovich, Mikita
  • Kasperski, Adam
  • Zieliński, Paweł

Abstract

This paper deals with a robust recoverable approach to 0–1 programming problems. It is assumed that a solution constructed in the first stage can be modified to some extent in the second stage. This modification consists in choosing a solution in some prescribed neighborhood of the current solution. The second stage solution cost can be uncertain and a polyhedral structure of uncertainty is used. The resulting robust recoverable problem is a min-max-min problem, which can be hard to solve when the number of variables is large. In this paper we provide a framework for solving robust recoverable 0–1 programming problems with a specified polyhedral uncertainty and propose several lower bounds and approximate solutions, which can be used for a wide class of 0–1 optimization problems. The results of computational tests for two problems, namely the assignment and the knapsack ones, are also presented.

Suggested Citation

  • Hradovich, Mikita & Kasperski, Adam & Zieliński, Paweł, 2019. "Robust recoverable 0–1 optimization problems under polyhedral uncertainty," European Journal of Operational Research, Elsevier, vol. 278(1), pages 136-148.
    • Handle: RePEc:eee:ejores:v:278:y:2019:i:1:p:136-148
    DOI: 10.1016/j.ejor.2019.04.017
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719303376
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.04.017?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. Chassein, André & Goerigk, Marc & Kasperski, Adam & Zieliński, Paweł, 2018. "On recoverable and two-stage robust selection problems with budgeted uncertainty," European Journal of Operational Research, Elsevier, vol. 265(2), pages 423-436.
    2. Onur Şeref & Ravindra K. Ahuja & James B. Orlin, 2009. "Incremental Network Optimization: Theory and Algorithms," Operations Research, INFORMS, vol. 57(3), pages 586-594, June.
    3. Mikita Hradovich & Adam Kasperski & Paweł Zieliński, 2017. "Recoverable robust spanning tree problem under interval uncertainty representations," Journal of Combinatorial Optimization, Springer, vol. 34(2), pages 554-573, August.
    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. Goerigk, Marc & Lendl, Stefan & Wulf, Lasse, 2022. "Recoverable robust representatives selection problems with discrete budgeted uncertainty," European Journal of Operational Research, Elsevier, vol. 303(2), pages 567-580.
    2. Chassein, André & Goerigk, Marc & Kasperski, Adam & Zieliński, Paweł, 2018. "On recoverable and two-stage robust selection problems with budgeted uncertainty," European Journal of Operational Research, Elsevier, vol. 265(2), pages 423-436.
    3. Fridman, Ilia & Pesch, Erwin & Shafransky, Yakov, 2020. "Minimizing maximum cost for a single machine under uncertainty of processing times," European Journal of Operational Research, Elsevier, vol. 286(2), pages 444-457.
    4. Fragkos, Ioannis & Cordeau, Jean-François & Jans, Raf, 2021. "Decomposition methods for large-scale network expansion problems," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 60-80.
    5. Krumke, Sven O. & Schmidt, Eva & Streicher, Manuel, 2019. "Robust multicovers with budgeted uncertainty," European Journal of Operational Research, Elsevier, vol. 274(3), pages 845-857.
    6. Marc Goerigk & Adam Kasperski & Paweł Zieliński, 2021. "Combinatorial two-stage minmax regret problems under interval uncertainty," Annals of Operations Research, Springer, vol. 300(1), pages 23-50, May.
    7. Mikita Hradovich & Adam Kasperski & Paweł Zieliński, 2017. "Recoverable robust spanning tree problem under interval uncertainty representations," Journal of Combinatorial Optimization, Springer, vol. 34(2), pages 554-573, August.
    8. Bendotti, Pascale & Chrétienne, Philippe & Fouilhoux, Pierre & Pass-Lanneau, Adèle, 2021. "Dominance-based linear formulation for the Anchor-Robust Project Scheduling Problem," European Journal of Operational Research, Elsevier, vol. 295(1), pages 22-33.
    9. Marc Goerigk & Adam Kasperski & Paweł Zieliński, 2022. "Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty," Journal of Combinatorial Optimization, Springer, vol. 43(3), pages 497-527, April.
    10. Ximing Wang & Panos M. Pardalos, 2017. "A modified active set algorithm for transportation discrete network design bi-level problem," Journal of Global Optimization, Springer, vol. 67(1), pages 325-342, January.
    11. Ali Koç & David P. Morton, 2015. "Prioritization via Stochastic Optimization," Management Science, INFORMS, vol. 61(3), pages 586-603, March.
    12. Letsios, Dimitrios & Mistry, Miten & Misener, Ruth, 2021. "Exact lexicographic scheduling and approximate rescheduling," European Journal of Operational Research, Elsevier, vol. 290(2), pages 469-478.
    13. Goerigk, Marc & Lendl, Stefan & Wulf, Lasse, 2022. "Two-Stage robust optimization problems with two-stage uncertainty," European Journal of Operational Research, Elsevier, vol. 302(1), pages 62-78.

    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:ejores:v:278:y:2019:i:1:p:136-148. 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/locate/eor .

    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.