IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v328y2026i3p912-924.html

Generator sets for the Minkowski sum problem

Author

Listed:
  • Lyngesen, Mark
  • Gadegaard, Sune Lauth
  • Nielsen, Lars Relund

Abstract

This paper develops a new theoretical framework for generator sets in the context of Minkowski Sum Problems (MSPs) arising in multi-objective optimization. In MSPs, the nondominated set of the global problem equals the nondominated set of the Minkowski sum of several local nondominated sets. We introduce the concept of generator sets: subsets of local nondominated vectors that are sufficient to construct the global nondominated set. We present novel theoretical results that characterize conditions for vectors to belong to a generator set or to be redundant. Moreover, we develop algorithms for finding generator sets and identifying redundant local vectors. Finally, we conduct extensive numerical experiments to test the impact of varying characteristics of the instances on the resulting global nondominated set and the number of redundant vectors.

Suggested Citation

  • Lyngesen, Mark & Gadegaard, Sune Lauth & Nielsen, Lars Relund, 2026. "Generator sets for the Minkowski sum problem," European Journal of Operational Research, Elsevier, vol. 328(3), pages 912-924.
    • Handle: RePEc:eee:ejores:v:328:y:2026:i:3:p:912-924
    DOI: 10.1016/j.ejor.2025.07.005
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221725005302
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2025.07.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

    for a different version of it.

    References listed on IDEAS

    as
    1. Michael Stiglmayr & José Figueira & Kathrin Klamroth, 2014. "On the multicriteria allocation problem," Annals of Operations Research, Springer, vol. 222(1), pages 535-549, November.
    2. Dietz, Tobias & Klamroth, Kathrin & Kraus, Konstantin & Ruzika, Stefan & Schäfer, Luca E. & Schulze, Britta & Stiglmayr, Michael & Wiecek, Margaret M., 2020. "Introducing multiobjective complex systems," European Journal of Operational Research, Elsevier, vol. 280(2), pages 581-596.
    3. Melissa Gardenghi & Trinidad Gómez & Francisca Miguel & Margaret M. Wiecek, 2011. "Algebra of Efficient Sets for Multiobjective Complex Systems," Journal of Optimization Theory and Applications, Springer, vol. 149(2), pages 385-410, May.
    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. Eduardo Fernández & Claudia Gómez-Santillán & Nelson Rangel-Valdez & Laura Cruz-Reyes, 2022. "Group Multi-Objective Optimization Under Imprecision and Uncertainty Using a Novel Interval Outranking Approach," Group Decision and Negotiation, Springer, vol. 31(5), pages 945-994, October.
    2. Paredes-Vergara, Matías & Palma-Behnke, Rodrigo & Haas, Jannik, 2024. "Characterizing decision making under deep uncertainty for model-based energy transitions," Renewable and Sustainable Energy Reviews, Elsevier, vol. 192(C).
    3. José Antonio Cuenca Mira & Francisca Miguel García, 2017. "On the Parametric Decomposition Theorem in Multiobjective Optimization," Journal of Optimization Theory and Applications, Springer, vol. 174(3), pages 945-953, September.
    4. Konur, Dinçer & Campbell, James F. & Monfared, Sepideh A., 2017. "Economic and environmental considerations in a stochastic inventory control model with order splitting under different delivery schedules among suppliers," Omega, Elsevier, vol. 71(C), pages 46-65.
    5. Natashia Boland & Hadi Charkhgard & Martin Savelsbergh, 2015. "A Criterion Space Search Algorithm for Biobjective Mixed Integer Programming: The Triangle Splitting Method," INFORMS Journal on Computing, INFORMS, vol. 27(4), pages 597-618, November.
    6. Christian Hoyer & Indra Gunawan & Carmen Haule Reaiche, 2020. "The Implementation of Industry 4.0 – A Systematic Literature Review of the Key Factors," Systems Research and Behavioral Science, Wiley Blackwell, vol. 37(4), pages 557-578, July.
    7. Richard B. Canty & Jeffrey A. Bennett & Keith A. Brown & Tonio Buonassisi & Sergei V. Kalinin & John R. Kitchin & Benji Maruyama & Robert G. Moore & Joshua Schrier & Martin Seifrid & Shijing Sun & Tej, 2025. "Science acceleration and accessibility with self-driving labs," Nature Communications, Nature, vol. 16(1), pages 1-11, December.
    8. Dinçer Konur & Hadi Farhangi & Cihan H. Dagli, 2016. "A multi-objective military system of systems architecting problem with inflexible and flexible systems: formulation and solution methods," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(4), pages 967-1006, October.
    9. Balderas, Fausto & Fernández, Eduardo & Cruz-Reyes, Laura & Gómez-Santillán, Claudia & Rangel-Valdez, Nelson, 2022. "Solving group multi-objective optimization problems by optimizing consensus through multi-criteria ordinal classification," European Journal of Operational Research, Elsevier, vol. 297(3), pages 1014-1029.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:328:y:2026:i:3:p:912-924. 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.