lynx   »   [go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v310y2023i1p315-327.html
   My bibliography  Save this article

Advancements in the computation of enclosures for multi-objective optimization problems

Author

Listed:
  • Eichfelder, Gabriele
  • Warnow, Leo
Abstract
A central goal for multi-objective optimization problems is to compute their nondominated sets. In most cases these sets consist of infinitely many points and it is not a practical approach to compute them exactly. One solution to overcome this problem is to compute an enclosure, a special kind of coverage, of the nondominated set. For that computation one often makes use of so-called local upper bounds. In this paper we present a generalization of this concept. For the first time, this allows to apply a warm start strategy to the computation of an enclosure. We also show how this generalized concept allows to remove empty areas of an enclosure by deleting certain parts of the lower and upper bound sets which has not been possible in the past. We demonstrate how to apply our ideas to the box approximation algorithm, a general framework to compute an enclosure, as recently used in the solver called BAMOP. We show how that framework can be simplified and improved significantly, especially concerning its practical numerical use. In fact, we show for selected numerical instances that our new approach is up to eight times faster than the original one. Hence, our new framework is not only of theoretical but also of practical use, for instance for continuous convex or mixed-integer quadratic optimization problems.

Suggested Citation

  • Eichfelder, Gabriele & Warnow, Leo, 2023. "Advancements in the computation of enclosures for multi-objective optimization problems," European Journal of Operational Research, Elsevier, vol. 310(1), pages 315-327.
    • Handle: RePEc:eee:ejores:v:310:y:2023:i:1:p:315-327
    DOI: 10.1016/j.ejor.2023.02.032
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221723001662
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2023.02.032?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. 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.
    2. 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.
    3. Gabriele Eichfelder & Peter Kirst & Laura Meng & Oliver Stein, 2021. "Correction to: A general branch-and-bound framework for continuous global multiobjective optimization," Journal of Global Optimization, Springer, vol. 80(1), pages 229-229, May.
    4. S. Ruzika & M. M. Wiecek, 2005. "Approximation Methods in Multiobjective Programming," Journal of Optimization Theory and Applications, Springer, vol. 126(3), pages 473-501, September.
    5. 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.
    6. Kaifeng Yang & Michael Emmerich & André Deutz & Thomas Bäck, 2019. "Efficient computation of expected hypervolume improvement using box decomposition algorithms," Journal of Global Optimization, Springer, vol. 75(1), pages 3-34, September.
    7. Kathrin Klamroth & Jørgen Tind & Margaret M. Wiecek, 2003. "Unbiased approximation in multicriteria optimization," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 56(3), pages 413-437, January.
    8. Soghra Nobakhtian & Narjes Shafiei, 2017. "A Benson type algorithm for nonconvex multiobjective programming problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(2), pages 271-287, July.
    9. 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.
    10. Gabriele Eichfelder & Peter Kirst & Laura Meng & Oliver Stein, 2021. "A general branch-and-bound framework for continuous global multiobjective optimization," Journal of Global Optimization, Springer, vol. 80(1), pages 195-227, May.
    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. Luca Benvenuti & Alberto Santis & Marianna Santis & Daniele Patria, 2024. "Designing sustainable diet plans by solving triobjective integer programs," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(3), pages 703-721, December.
    2. Gabriele Eichfelder & Tobias Gerlach & Leo Warnow, 2024. "A test instance generator for multiobjective mixed-integer optimization," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(1), pages 385-410, 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. Gabriele Eichfelder & Oliver Stein & Leo Warnow, 2024. "A Solver for Multiobjective Mixed-Integer Convex and Nonconvex Optimization," Journal of Optimization Theory and Applications, Springer, vol. 203(2), pages 1736-1766, November.
    2. Gabriele Eichfelder & Leo Warnow, 2022. "An approximation algorithm for multi-objective optimization problems using a box-coverage," Journal of Global Optimization, Springer, vol. 83(2), pages 329-357, June.
    3. Moritz Link & Stefan Volkwein, 2023. "Adaptive piecewise linear relaxations for enclosure computations for nonconvex multiobjective mixed-integer quadratically constrained programs," Journal of Global Optimization, Springer, vol. 87(1), pages 97-132, September.
    4. Gabriele Eichfelder & Leo Warnow, 2024. "A hybrid patch decomposition approach to compute an enclosure for multi-objective mixed-integer convex optimization problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(1), pages 291-320, August.
    5. Gabriele Eichfelder & Peter Kirst & Laura Meng & Oliver Stein, 2021. "A general branch-and-bound framework for continuous global multiobjective optimization," Journal of Global Optimization, Springer, vol. 80(1), pages 195-227, May.
    6. 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.
    7. 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.
    8. Samira Fallah & Ted K. Ralphs & Natashia L. Boland, 2024. "On the relationship between the value function and the efficient frontier of a mixed integer linear optimization problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 100(1), pages 175-220, August.
    9. 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.
    10. Kerstin Dächert & Ria Grindel & Elisabeth Leoff & Jonas Mahnkopp & Florian Schirra & Jörg Wenzel, 2022. "Multicriteria asset allocation in practice," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(2), pages 349-373, June.
    11. Burdett, Robert L & Corry, Paul & Yarlagadda, Prasad & Cook, David & Birgan, Sean, 2024. "Multicriteria optimization techniques for understanding the case mix landscape of a hospital," European Journal of Operational Research, Elsevier, vol. 319(1), pages 263-291.
    12. 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.
    13. Birgit Rudloff & Firdevs Ulus, 2019. "Certainty Equivalent and Utility Indifference Pricing for Incomplete Preferences via Convex Vector Optimization," Papers 1904.09456, arXiv.org, revised Oct 2020.
    14. 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.
    15. Angelo Aliano Filho & Antonio Carlos Moretti & Margarida Vaz Pato & Washington Alves Oliveira, 2021. "An exact scalarization method with multiple reference points for bi-objective integer linear optimization problems," Annals of Operations Research, Springer, vol. 296(1), pages 35-69, January.
    16. I. Kaliszewski & J. Miroforidis, 2018. "On upper approximations of Pareto fronts," Journal of Global Optimization, Springer, vol. 72(3), pages 475-490, November.
    17. Bazgan, Cristina & Jamain, Florian & Vanderpooten, Daniel, 2017. "Discrete representation of the non-dominated set for multi-objective optimization problems using kernels," European Journal of Operational Research, Elsevier, vol. 260(3), pages 814-827.
    18. Kerstin Dachert & Ria Grindel & Elisabeth Leoff & Jonas Mahnkopp & Florian Schirra & Jorg Wenzel, 2021. "Multicriteria asset allocation in practice," Papers 2103.10958, arXiv.org.
    19. Kerstin Dächert & Sauleh Siddiqui & Javier Saez-Gallego & Steven A. Gabriel & Juan Miguel Morales, 2019. "A Bicriteria Perspective on L-Penalty Approaches – a Corrigendum to Siddiqui and Gabriel’s L-Penalty Approach for Solving MPECs," Networks and Spatial Economics, Springer, vol. 19(4), pages 1199-1214, December.
    20. Przybylski, Anthony & Gandibleux, Xavier, 2017. "Multi-objective branch and bound," European Journal of Operational Research, Elsevier, vol. 260(3), pages 856-872.

    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:310:y:2023:i:1:p:315-327. 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.
    Лучший частный хостинг