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

Representing the nondominated set in multi-objective mixed-integer programs

Author

Listed:
  • Doğan, Ilgın
  • Lokman, Banu
  • Köksalan, Murat

Abstract

In this paper, we consider generating a representative subset of nondominated points at a prespecified precision in multi-objective mixed-integer programs (MOMIPs). The number of nondominated points grows exponentially with problem size and finding all nondominated points is typically hard in MOMIPs. Representing the nondominated set with a small subset of nondominated points is important for a decision maker to get an understanding of the layout of solutions. The shape and density of the nondominated points over the objective space may be critical in obtaining a set of solutions that represent the nondominated set well. We develop an exact algorithm that generates a representative set guaranteeing a prespecified precision. Our experiments on a variety of problems demonstrate that our algorithm outperforms existing approaches in terms of both the cardinality of the representative set and computation times.

Suggested Citation

  • Doğan, Ilgın & Lokman, Banu & Köksalan, Murat, 2022. "Representing the nondominated set in multi-objective mixed-integer programs," European Journal of Operational Research, Elsevier, vol. 296(3), pages 804-818.
  • Handle: RePEc:eee:ejores:v:296:y:2022:i:3:p:804-818
    DOI: 10.1016/j.ejor.2021.04.005
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721003179
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2021.04.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. Murat Köksalan & Banu Lokman, 2015. "Finding nadir points in multi-objective integer programs," Journal of Global Optimization, Springer, vol. 62(1), pages 55-77, May.
    2. Shao, Lizhen & Ehrgott, Matthias, 2016. "Discrete representation of non-dominated sets in multi-objective linear programming," European Journal of Operational Research, Elsevier, vol. 255(3), pages 687-698.
    3. Boland, Natashia & Charkhgard, Hadi & Savelsbergh, Martin, 2017. "A new method for optimizing a linear function over the efficient set of a multiobjective integer program," European Journal of Operational Research, Elsevier, vol. 260(3), pages 904-919.
    4. Laumanns, Marco & Thiele, Lothar & Zitzler, Eckart, 2006. "An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method," European Journal of Operational Research, Elsevier, vol. 169(3), pages 932-942, March.
    5. Murat Köksalan & Banu Lokman, 2009. "Approximating the nondominated frontiers of multi‐objective combinatorial optimization problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(2), pages 191-198, March.
    6. Boland, Natashia & Charkhgard, Hadi & Savelsbergh, Martin, 2017. "The Quadrant Shrinking Method: A simple and efficient algorithm for solving tri-objective integer programs," European Journal of Operational Research, Elsevier, vol. 260(3), pages 873-885.
    7. Tobias Kuhn & Stefan Ruzika, 2017. "A coverage-based Box-Algorithm to compute a representation for optimization problems with three objective functions," Journal of Global Optimization, Springer, vol. 67(3), pages 581-600, March.
    8. Dächert, Kerstin & Klamroth, Kathrin & Lacour, Renaud & Vanderpooten, Daniel, 2017. "Efficient computation of the search region in multi-objective optimization," European Journal of Operational Research, Elsevier, vol. 260(3), pages 841-855.
    9. Esra Karasakal & Murat Köksalan, 2009. "Generating a Representative Subset of the Nondominated Frontier in Multiple Criteria Decision Making," Operations Research, INFORMS, vol. 57(1), pages 187-199, February.
    10. Klamroth, Kathrin & Lacour, Renaud & Vanderpooten, Daniel, 2015. "On the representation of the search region in multi-objective optimization," European Journal of Operational Research, Elsevier, vol. 245(3), pages 767-778.
    11. Michael Masin & Yossi Bukchin, 2008. "Diversity Maximization Approach for Multiobjective Optimization," Operations Research, INFORMS, vol. 56(2), pages 411-424, April.
    12. Kerstin Dächert & Kathrin Klamroth, 2015. "A linear bound on the number of scalarizations needed to solve discrete tricriteria optimization problems," Journal of Global Optimization, Springer, vol. 61(4), pages 643-676, April.
    13. Sylva, John & Crema, Alejandro, 2007. "A method for finding well-dispersed subsets of non-dominated vectors for multiple objective mixed integer linear programs," European Journal of Operational Research, Elsevier, vol. 180(3), pages 1011-1027, August.
    14. Melih Ozlen & Benjamin A. Burton & Cameron A. G. MacRae, 2014. "Multi-Objective Integer Programming: An Improved Recursive Algorithm," Journal of Optimization Theory and Applications, Springer, vol. 160(2), pages 470-482, February.
    15. Özarık, Sami Serkan & Lokman, Banu & Köksalan, Murat, 2020. "Distribution based representative sets for multi-objective integer programs," European Journal of Operational Research, Elsevier, vol. 284(2), pages 632-643.
    16. Banu Lokman & Murat Köksalan, 2013. "Finding all nondominated points of multi-objective integer programs," Journal of Global Optimization, Springer, vol. 57(2), pages 347-365, October.
    17. Ceyhan, Gökhan & Köksalan, Murat & Lokman, Banu, 2019. "Finding a representative nondominated set for multi-objective mixed integer programs," European Journal of Operational Research, Elsevier, vol. 272(1), pages 61-77.
    18. Matthias Ehrgott, 2005. "Multicriteria Optimization," Springer Books, Springer, edition 0, number 978-3-540-27659-3, 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. Mesquita-Cunha, Mariana & Figueira, José Rui & Barbosa-Póvoa, Ana Paula, 2023. "New ϵ−constraint methods for multi-objective integer linear programming: A Pareto front representation approach," European Journal of Operational Research, Elsevier, vol. 306(1), pages 286-307.
    2. Pedersen, Jaap & Weinand, Jann Michael & Syranidou, Chloi & Rehfeldt, Daniel, 2024. "An efficient solver for large-scale onshore wind farm siting including cable routing," European Journal of Operational Research, Elsevier, vol. 317(2), pages 616-630.
    3. Kerstin Dächert & Tino Fleuren & Kathrin Klamroth, 2024. "A simple, efficient and versatile objective space algorithm for multiobjective integer programming," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(1), pages 351-384, August.

    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. Özarık, Sami Serkan & Lokman, Banu & Köksalan, Murat, 2020. "Distribution based representative sets for multi-objective integer programs," European Journal of Operational Research, Elsevier, vol. 284(2), pages 632-643.
    2. Ceyhan, Gökhan & Köksalan, Murat & Lokman, Banu, 2019. "Finding a representative nondominated set for multi-objective mixed integer programs," European Journal of Operational Research, Elsevier, vol. 272(1), pages 61-77.
    3. Mesquita-Cunha, Mariana & Figueira, José Rui & Barbosa-Póvoa, Ana Paula, 2023. "New ϵ−constraint methods for multi-objective integer linear programming: A Pareto front representation approach," European Journal of Operational Research, Elsevier, vol. 306(1), pages 286-307.
    4. David Bergman & Merve Bodur & Carlos Cardonha & Andre A. Cire, 2022. "Network Models for Multiobjective Discrete Optimization," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 990-1005, March.
    5. Kerstin Dächert & Tino Fleuren & Kathrin Klamroth, 2024. "A simple, efficient and versatile objective space algorithm for multiobjective integer programming," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(1), pages 351-384, August.
    6. Ozgu Turgut & Evrim Dalkiran & Alper E. Murat, 2019. "An exact parallel objective space decomposition algorithm for solving multi-objective integer programming problems," Journal of Global Optimization, Springer, vol. 75(1), pages 35-62, September.
    7. Satya Tamby & Daniel Vanderpooten, 2021. "Enumeration of the Nondominated Set of Multiobjective Discrete Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 72-85, January.
    8. Holzmann, Tim & Smith, J.C., 2018. "Solving discrete multi-objective optimization problems using modified augmented weighted Tchebychev scalarizations," European Journal of Operational Research, Elsevier, vol. 271(2), pages 436-449.
    9. De Santis, Marianna & Grani, Giorgio & Palagi, Laura, 2020. "Branching with hyperplanes in the criterion space: The frontier partitioner algorithm for biobjective integer programming," European Journal of Operational Research, Elsevier, vol. 283(1), pages 57-69.
    10. Burdett, Robert & Kozan, Erhan, 2016. "A multi-criteria approach for hospital capacity analysis," European Journal of Operational Research, Elsevier, vol. 255(2), pages 505-521.
    11. 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.
    12. William Pettersson & Melih Ozlen, 2020. "Multiobjective Integer Programming: Synergistic Parallel Approaches," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 461-472, April.
    13. Natashia Boland & Hadi Charkhgard & Martin Savelsbergh, 2015. "A Criterion Space Search Algorithm for Biobjective Integer Programming: The Balanced Box Method," INFORMS Journal on Computing, INFORMS, vol. 27(4), pages 735-754, November.
    14. Mansini, Renata & Zanella, Marina & Zanotti, Roberto, 2023. "Optimizing a complex multi-objective personnel scheduling problem jointly complying with requests from customers and staff," Omega, Elsevier, vol. 114(C).
    15. Julius Bauß & Michael Stiglmayr, 2024. "Augmenting bi-objective branch and bound by scalarization-based information," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(1), pages 85-121, August.
    16. Klamroth, Kathrin & Lacour, Renaud & Vanderpooten, Daniel, 2015. "On the representation of the search region in multi-objective optimization," European Journal of Operational Research, Elsevier, vol. 245(3), pages 767-778.
    17. Pham Thi Hoai & Hoai An Le Thi & Nguyen Canh Nam, 2021. "Half-open polyblock for the representation of the search region in multiobjective optimization problems: its application and computational aspects," 4OR, Springer, vol. 19(1), pages 41-70, March.
    18. Forget, Nicolas & Gadegaard, Sune Lauth & Nielsen, Lars Relund, 2022. "Warm-starting lower bound set computations for branch-and-bound algorithms for multi objective integer linear programs," European Journal of Operational Research, Elsevier, vol. 302(3), pages 909-924.
    19. Dächert, Kerstin & Klamroth, Kathrin & Lacour, Renaud & Vanderpooten, Daniel, 2017. "Efficient computation of the search region in multi-objective optimization," European Journal of Operational Research, Elsevier, vol. 260(3), pages 841-855.
    20. Sunney Fotedar & Ann-Brith Strömberg & Torgny Almgren & Stefan Cedergren, 2023. "A criterion space decomposition approach to generalized tri-objective tactical resource allocation," Computational Management Science, Springer, vol. 20(1), pages 1-28, December.

    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:296:y:2022:i:3:p:804-818. 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.