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

On a constant factor approximation for minmax regret problems using a symmetry point scenario

Author

Listed:
  • Conde, Eduardo

Abstract

In order to find a robust solution under an unknown linear cost function it will be considered the minmax regret criterion. It is assumed the vector of costs can take on values from a given uncertainty set. The resulting optimization model has been extensively analyzed in the literature when the uncertain costs are modeled by closed intervals. Unfortunately, except for rare applications, this problem has NP-hard complexity which has led to the appearance of approximated methods seeking for good solutions in a short computational time.

Suggested Citation

  • Conde, Eduardo, 2012. "On a constant factor approximation for minmax regret problems using a symmetry point scenario," European Journal of Operational Research, Elsevier, vol. 219(2), pages 452-457.
    • Handle: RePEc:eee:ejores:v:219:y:2012:i:2:p:452-457
    DOI: 10.1016/j.ejor.2012.01.005
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221712000069
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2012.01.005?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. Chanas, Stefan & Zielinski, Pawel, 2002. "The computational complexity of the criticality problems in a network with interval activity times," European Journal of Operational Research, Elsevier, vol. 136(3), pages 541-550, February.
    2. Averbakh, Igor & Lebedev, Vasilij, 2005. "On the complexity of minmax regret linear programming," European Journal of Operational Research, Elsevier, vol. 160(1), pages 227-231, January.
    3. Montemanni, R. & Gambardella, L. M., 2005. "A branch and bound algorithm for the robust spanning tree problem with interval data," European Journal of Operational Research, Elsevier, vol. 161(3), pages 771-779, March.
    4. Zielinski, Pawel, 2004. "The computational complexity of the relative robust shortest path problem with interval data," European Journal of Operational Research, Elsevier, vol. 158(3), pages 570-576, November.
    5. Conde, Eduardo, 2009. "A minmax regret approach to the critical path method with task interval times," European Journal of Operational Research, Elsevier, vol. 197(1), pages 235-242, August.
    6. Mausser, Helmut E. & Laguna, Manuel, 1999. "A heuristic to minimax absolute regret for linear programs with interval objective function coefficients," European Journal of Operational Research, Elsevier, vol. 117(1), pages 157-174, August.
    7. Montemanni, Roberto, 2006. "A Benders decomposition approach for the robust spanning tree problem with interval data," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1479-1490, November.
    8. Richard L. Daniels & Panagiotis Kouvelis, 1995. "Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production," Management Science, INFORMS, vol. 41(2), pages 363-376, February.
    9. Mustajoki, Jyri & Hamalainen, Raimo P. & Lindstedt, Mats R.K., 2006. "Using intervals for global sensitivity and worst-case analyses in multiattribute value trees," European Journal of Operational Research, Elsevier, vol. 174(1), pages 278-292, October.
    10. Aissi, Hassene & Bazgan, Cristina & Vanderpooten, Daniel, 2009. "Min-max and min-max regret versions of combinatorial optimization problems: A survey," European Journal of Operational Research, Elsevier, vol. 197(2), pages 427-438, 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. Chassein, André B. & Goerigk, Marc, 2015. "A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem," European Journal of Operational Research, Elsevier, vol. 244(3), pages 739-747.
    2. Chassein, André & Goerigk, Marc, 2017. "Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets," European Journal of Operational Research, Elsevier, vol. 258(1), pages 58-69.
    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.

    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. Alireza Amirteimoori & Simin Masrouri, 2021. "DEA-based competition strategy in the presence of undesirable products: An application to paper mills," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 31(2), pages 5-21.
    2. Aissi, Hassene & Bazgan, Cristina & Vanderpooten, Daniel, 2009. "Min-max and min-max regret versions of combinatorial optimization problems: A survey," European Journal of Operational Research, Elsevier, vol. 197(2), pages 427-438, September.
    3. Chassein, André B. & Goerigk, Marc, 2015. "A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem," European Journal of Operational Research, Elsevier, vol. 244(3), pages 739-747.
    4. Wei Wu & Manuel Iori & Silvano Martello & Mutsunori Yagiura, 2022. "An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2523-2539, September.
    5. Conde, Eduardo & Candia, Alfredo, 2007. "Minimax regret spanning arborescences under uncertain costs," European Journal of Operational Research, Elsevier, vol. 182(2), pages 561-577, October.
    6. Mohammad Javad Feizollahi & Igor Averbakh, 2014. "The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 321-335, May.
    7. Scott E. Sampson, 2008. "OR PRACTICE---Optimization of Vacation Timeshare Scheduling," Operations Research, INFORMS, vol. 56(5), pages 1079-1088, October.
    8. Jungho Park & Hadi El-Amine & Nevin Mutlu, 2021. "An Exact Algorithm for Large-Scale Continuous Nonlinear Resource Allocation Problems with Minimax Regret Objectives," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1213-1228, July.
    9. Adam Kasperski & Paweł Zieliński, 2019. "Risk-averse single machine scheduling: complexity and approximation," Journal of Scheduling, Springer, vol. 22(5), pages 567-580, October.
    10. Cohen, Izack & Postek, Krzysztof & Shtern, Shimrit, 2023. "An adaptive robust optimization model for parallel machine scheduling," European Journal of Operational Research, Elsevier, vol. 306(1), pages 83-104.
    11. Kasperski, Adam & Zielinski, Pawel, 2010. "Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights," European Journal of Operational Research, Elsevier, vol. 200(3), pages 680-687, February.
    12. Carlo Meloni & Marco Pranzo, 2020. "Expected shortfall for the makespan in activity networks under imperfect information," Flexible Services and Manufacturing Journal, Springer, vol. 32(3), pages 668-692, September.
    13. Luo, Chunling & Tan, Chin Hon & Liu, Xiao, 2020. "Maximum excess dominance: Identifying impractical solutions in linear problems with interval coefficients," European Journal of Operational Research, Elsevier, vol. 282(2), pages 660-676.
    14. An, Jaehyung & Mikhaylov, Alexey & Jung, Sang-Uk, 2021. "A Linear Programming approach for robust network revenue management in the airline industry," Journal of Air Transport Management, Elsevier, vol. 91(C).
    15. Ng, K.K.H. & Lee, C.K.M. & Chan, Felix T.S. & Qin, Yichen, 2017. "Robust aircraft sequencing and scheduling problem with arrival/departure delay using the min-max regret approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 106(C), pages 115-136.
    16. Conde, Eduardo, 2009. "A minmax regret approach to the critical path method with task interval times," European Journal of Operational Research, Elsevier, vol. 197(1), pages 235-242, August.
    17. Kasperski, Adam & Kurpisz, Adam & Zieliński, Paweł, 2012. "Approximating a two-machine flow shop scheduling under discrete scenario uncertainty," European Journal of Operational Research, Elsevier, vol. 217(1), pages 36-43.
    18. Chen, Xujin & Hu, Jie & Hu, Xiaodong, 2009. "A polynomial solvable minimum risk spanning tree problem with interval data," European Journal of Operational Research, Elsevier, vol. 198(1), pages 43-46, October.
    19. Pätzold, Julius & Schöbel, Anita, 2020. "Approximate cutting plane approaches for exact solutions to robust optimization problems," European Journal of Operational Research, Elsevier, vol. 284(1), pages 20-30.
    20. Nikulin, Y. & Karelkina, O. & Mäkelä, M.M., 2013. "On accuracy, robustness and tolerances in vector Boolean optimization," European Journal of Operational Research, Elsevier, vol. 224(3), pages 449-457.

    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:219:y:2012:i:2:p:452-457. 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.