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

Discrete representation of non-dominated sets in multi-objective linear programming

Author

Listed:
  • Shao, Lizhen
  • Ehrgott, Matthias

Abstract

In this paper we address the problem of representing the continuous but non-convex set of non-dominated points of a multi-objective linear programme by a finite subset of such points. We prove that a related decision problem is NP-complete. Moreover, we illustrate the drawbacks of the known global shooting, normal boundary intersection and normal constraint methods concerning the coverage error and uniformity level of the representation by examples. We propose a method which combines the global shooting and normal boundary intersection methods. By doing so, we overcome their limitations, but preserve their advantages. We prove that our method computes a set of evenly distributed non-dominated points for which the coverage error and the uniformity level can be guaranteed. We apply this method to an optimisation problem in radiation therapy and present illustrative results for some clinical cases. Finally, we present numerical results on randomly generated examples.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:255:y:2016:i:3:p:687-698
    DOI: 10.1016/j.ejor.2016.05.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716303010
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2016.05.001?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. 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.
    2. Lizhen Shao & Matthias Ehrgott, 2008. "Approximately solving multiobjective linear programmes in objective space and an application in radiotherapy treatment planning," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 68(2), pages 257-276, October.
    3. Stacey Faulkenberg & Margaret Wiecek, 2012. "Generating equidistant representations in biobjective programming," Computational Optimization and Applications, Springer, vol. 51(3), pages 1173-1210, April.
    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. Kai Kang & Wei Pu & Yanfang Ma & Xiaoyu Wang, 2018. "Bi-objective inventory allocation planning problem with supplier selection and carbon trading under uncertainty," PLOS ONE, Public Library of Science, vol. 13(11), pages 1-25, November.
    2. 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.
    3. 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.
    4. Oylum S¸eker & Mucahit Cevik & Merve Bodur & Young Lee & Mark Ruschin, 2023. "A Multiobjective Approach for Sector Duration Optimization in Stereotactic Radiosurgery Treatment Planning," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 248-264, January.
    5. 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.
    6. 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.
    7. Breedveld, Sebastiaan & Craft, David & van Haveren, Rens & Heijmen, Ben, 2019. "Multi-criteria optimization and decision-making in radiotherapy," European Journal of Operational Research, Elsevier, vol. 277(1), pages 1-19.
    8. Ali Najmi & Taha H. Rashidi & James Vaughan & Eric J. Miller, 2020. "Calibration of large-scale transport planning models: a structured approach," Transportation, Springer, vol. 47(4), pages 1867-1905, August.
    9. E. Filatovas & O. Kurasova & J. L. Redondo & J. Fernández, 2020. "A reference point-based evolutionary algorithm for approximating regions of interest in multiobjective problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(2), pages 402-423, July.
    10. Kuan-Min Lin & Matthias Ehrgott & Andrea Raith, 2017. "Integrating column generation in a method to compute a discrete representation of the non-dominated set of multi-objective linear programmes," 4OR, Springer, vol. 15(4), pages 331-357, December.
    11. 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.

    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. Rennen, G. & van Dam, E.R. & den Hertog, D., 2009. "Enhancement of Sandwich Algorithms for Approximating Higher Dimensional Convex Pareto Sets," Other publications TiSEM e2255959-6691-4ef1-88a4-5, Tilburg University, School of Economics and Management.
    2. Andreas Löhne & Birgit Rudloff & Firdevs Ulus, 2014. "Primal and dual approximation algorithms for convex vector optimization problems," Journal of Global Optimization, Springer, vol. 60(4), pages 713-736, December.
    3. Rastegar, Narges & Khorram, Esmaile, 2014. "A combined scalarizing method for multiobjective programming problems," European Journal of Operational Research, Elsevier, vol. 236(1), pages 229-237.
    4. Elzbieta Rynska & Joanna Klimowicz & Slawomir Kowal & Krzysztof Lyzwa & Michal Pierzchalski & Wojciech Rekosz, 2020. "Smart Energy Solutions as an Indispensable Multi-Criteria Input for a Coherent Urban Planning and Building Design Process—Two Case Studies for Smart Office Buildings in Warsaw Downtown Area," Energies, MDPI, vol. 13(15), pages 1-24, July.
    5. Przybylski, Anthony & Gandibleux, Xavier, 2017. "Multi-objective branch and bound," European Journal of Operational Research, Elsevier, vol. 260(3), pages 856-872.
    6. Ana B. Ruiz & Francisco Ruiz & Kaisa Miettinen & Laura Delgado-Antequera & Vesa Ojalehto, 2019. "NAUTILUS Navigator: free search interactive multiobjective optimization without trading-off," Journal of Global Optimization, Springer, vol. 74(2), pages 213-231, June.
    7. Matthias Ehrgott & Çiğdem Güler & Horst Hamacher & Lizhen Shao, 2010. "Mathematical optimization in intensity modulated radiation therapy," Annals of Operations Research, Springer, vol. 175(1), pages 309-365, March.
    8. 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.
    9. Gabriele Eichfelder, 2009. "Scalarizations for adaptively solving multi-objective optimization problems," Computational Optimization and Applications, Springer, vol. 44(2), pages 249-273, November.
    10. Kalyan Shankar Bhattacharjee & Hemant Kumar Singh & Tapabrata Ray, 2017. "An approach to generate comprehensive piecewise linear interpolation of pareto outcomes to aid decision making," Journal of Global Optimization, Springer, vol. 68(1), pages 71-93, May.
    11. Timothy C. Y. Chan & Tim Craig & Taewoo Lee & Michael B. Sharpe, 2014. "Generalized Inverse Multiobjective Optimization with Application to Cancer Therapy," Operations Research, INFORMS, vol. 62(3), pages 680-695, June.
    12. 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.
    13. 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.
    14. Brian Dandurand & Margaret M. Wiecek, 2016. "Quadratic scalarization for decomposed multiobjective optimization," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(4), pages 1071-1096, October.
    15. Matthias Ehrgott & Lizhen Shao & Anita Schöbel, 2011. "An approximation algorithm for convex multi-objective programming problems," Journal of Global Optimization, Springer, vol. 50(3), pages 397-416, July.
    16. 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.
    17. Markus Hartikainen & Alberto Lovison, 2015. "PAINT–SiCon: constructing consistent parametric representations of Pareto sets in nonconvex multiobjective optimization," Journal of Global Optimization, Springer, vol. 62(2), pages 243-261, June.
    18. Notte, Gastón & Cancela, Héctor & Pedemonte, Martín & Chilibroste, Pablo & Rossing, Walter & Groot, Jeroen C.J., 2020. "A multi-objective optimization model for dairy feeding management," Agricultural Systems, Elsevier, vol. 183(C).
    19. Fereshteh Akbari & Mehrdad Ghaznavi & Esmaile Khorram, 2018. "A Revised Pascoletti–Serafini Scalarization Method for Multiobjective Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 178(2), pages 560-590, August.
    20. Kathrin Klamroth & Kaisa Miettinen, 2008. "Integrating Approximation and Interactive Decision Making in Multicriteria Optimization," Operations Research, INFORMS, vol. 56(1), pages 222-234, February.

    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:255:y:2016:i:3:p:687-698. 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.