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

Approximating combinatorial optimization problems with the ordered weighted averaging criterion

Author

Listed:
  • Chassein, André
  • Goerigk, Marc
  • Kasperski, Adam
  • Zieliński, Paweł

Abstract

This paper deals with combinatorial optimization problems with K cost scenarios, inducing K linear objectives. The popular Ordered Weighted Averaging (OWA) criterion is used to aggregate the objectives and compute a solution. It is well-known that minimizing OWA for most basic combinatorial problems is weakly NP-hard even if the number of scenarios K equals two, and strongly NP-hard when K is a part of the input. In this paper, the problem with nonincreasing weights in the OWA criterion and a large K is first considered. A method of reducing the number of scenarios, by appropriately aggregating the costs before solving the problem, is proposed. It is shown that an optimal solution to the reduced problem has a guaranteed worst-case approximation ratio. Some new approximation results for the Hurwicz criterion, which is a special case of OWA, are also presented.

Suggested Citation

  • Chassein, André & Goerigk, Marc & Kasperski, Adam & Zieliński, Paweł, 2020. "Approximating combinatorial optimization problems with the ordered weighted averaging criterion," European Journal of Operational Research, Elsevier, vol. 286(3), pages 828-838.
    • Handle: RePEc:eee:ejores:v:286:y:2020:i:3:p:828-838
    DOI: 10.1016/j.ejor.2020.04.018
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720303520
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.04.018?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. Vittorio Bilò & Ioannis Caragiannis & Angelo Fanelli & Michele Flammini & Gianpiero Monaco, 2017. "Simple Greedy Algorithms for Fundamental Multidimensional Graph Problems," Post-Print hal-02089412, HAL.
    2. R. T. Rockafellar & Roger J.-B. Wets, 1991. "Scenarios and Policy Aggregation in Optimization Under Uncertainty," Mathematics of Operations Research, INFORMS, vol. 16(1), pages 119-147, February.
    3. Peter Kall & János Mayer, 2005. "Stochastic Linear Programming," International Series in Operations Research and Management Science, Springer, number 978-0-387-24440-2, December.
    4. Boland, Natashia & Charkhgard, Hadi & Savelsbergh, Martin, 2019. "Preprocessing and cut generation techniques for multi-objective binary programming," European Journal of Operational Research, Elsevier, vol. 274(3), pages 858-875.
    5. Lindroth, Peter & Patriksson, Michael & Strömberg, Ann-Brith, 2010. "Approximating the Pareto optimal set using a reduced set of objective functions," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1519-1534, December.
    6. Dimitris Bertsimas & David B. Brown, 2009. "Constructing Uncertainty Sets for Robust Linear Optimization," Operations Research, INFORMS, vol. 57(6), pages 1483-1495, December.
    7. Kostreva, Michael M. & Ogryczak, Wlodzimierz & Wierzbicki, Adam, 2004. "Equitable aggregations and multiple criteria analysis," European Journal of Operational Research, Elsevier, vol. 158(2), pages 362-377, October.
    8. Ogryczak, Wlodzimierz & Sliwinski, Tomasz, 2003. "On solving linear programs with the ordered weighted averaging objective," European Journal of Operational Research, Elsevier, vol. 148(1), pages 80-91, July.
    9. Nguyen Thoai, 2012. "Criteria and dimension reduction of linear multiple criteria optimization problems," Journal of Global Optimization, Springer, vol. 52(3), pages 499-508, March.
    10. Ogryczak, Wlodzimierz, 2000. "Inequality measures and equitable approaches to location problems," European Journal of Operational Research, Elsevier, vol. 122(2), pages 374-391, April.
    11. Gal, Tomas & Leberling, Heiner, 1977. "Redundant objective functions in linear vector maximum problems and their determination," European Journal of Operational Research, Elsevier, vol. 1(3), pages 176-184, May.
    12. Fernández, Elena & Pozo, Miguel A. & Puerto, Justo & Scozzari, Andrea, 2017. "Ordered Weighted Average optimization in Multiobjective Spanning Tree Problem," European Journal of Operational Research, Elsevier, vol. 260(3), pages 886-903.
    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. Mut, Murat & Wiecek, Margaret M., 2011. "Generalized equitable preference in multiobjective programming," European Journal of Operational Research, Elsevier, vol. 212(3), pages 535-551, August.
    2. Karsu, Özlem & Morton, Alec & Argyris, Nikos, 2018. "Capturing preferences for inequality aversion in decision support," European Journal of Operational Research, Elsevier, vol. 264(2), pages 686-706.
    3. Zhou, Feng & Huang, Gordon H. & Chen, Guo-Xian & Guo, Huai-Cheng, 2009. "Enhanced-interval linear programming," European Journal of Operational Research, Elsevier, vol. 199(2), pages 323-333, December.
    4. Kasin Ransikarbum & Scott J. Mason, 2016. "Multiple-objective analysis of integrated relief supply and network restoration in humanitarian logistics operations," International Journal of Production Research, Taylor & Francis Journals, vol. 54(1), pages 49-68, January.
    5. Boland, Natashia & Charkhgard, Hadi & Savelsbergh, Martin, 2019. "Preprocessing and cut generation techniques for multi-objective binary programming," European Journal of Operational Research, Elsevier, vol. 274(3), pages 858-875.
    6. Jesús Sánchez-Oro & Ana D. López-Sánchez & Anna Martínez-Gavara & Alfredo G. Hernández-Díaz & Abraham Duarte, 2021. "A Hybrid Strategic Oscillation with Path Relinking Algorithm for the Multiobjective k -Balanced Center Location Problem," Mathematics, MDPI, vol. 9(8), pages 1-21, April.
    7. Bashir Bashir & Özlem Karsu, 2022. "Solution approaches for equitable multiobjective integer programming problems," Annals of Operations Research, Springer, vol. 311(2), pages 967-995, April.
    8. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    9. Argyris, Nikolaos & Karsu, Özlem & Yavuz, Mirel, 2022. "Fair resource allocation: Using welfare-based dominance constraints," European Journal of Operational Research, Elsevier, vol. 297(2), pages 560-578.
    10. Gutjahr, Walter J., 2021. "Inequity-averse stochastic decision processes," European Journal of Operational Research, Elsevier, vol. 288(1), pages 258-270.
    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. Włodzimierz Ogryczak, 2009. "Inequality measures and equitable locations," Annals of Operations Research, Springer, vol. 167(1), pages 61-86, March.
    13. Kostreva, Michael M. & Ogryczak, Wlodzimierz & Wierzbicki, Adam, 2004. "Equitable aggregations and multiple criteria analysis," European Journal of Operational Research, Elsevier, vol. 158(2), pages 362-377, October.
    14. Patrice Perny & Olivier Spanjaard & Louis-Xavier Storme, 2006. "A decision-theoretic approach to robust optimization in multivalued graphs," Annals of Operations Research, Springer, vol. 147(1), pages 317-341, October.
    15. Hui-Chin Tang & Shen-Tai Yang, 2018. "Optimizing Three-Dimensional Constrained Ordered Weighted Averaging Aggregation Problem with Bounded Variables," Mathematics, MDPI, vol. 6(9), pages 1-16, September.
    16. Kaynar, Nur & Karsu, Özlem, 2018. "Equitable decision making approaches over allocations of multiple benefits to multiple entities," Omega, Elsevier, vol. 81(C), pages 85-98.
    17. Akoluk, Damla & Karsu, Özlem, 2022. "Ensuring multidimensional equality in public service," Socio-Economic Planning Sciences, Elsevier, vol. 80(C).
    18. 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.
    19. David Rea & Craig Froehle & Suzanne Masterson & Brian Stettler & Gregory Fermann & Arthur Pancioli, 2021. "Unequal but Fair: Incorporating Distributive Justice in Operational Allocation Models," Production and Operations Management, Production and Operations Management Society, vol. 30(7), pages 2304-2320, July.
    20. 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.

    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:286:y:2020:i:3:p:828-838. 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.