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

On the computation of all supported efficient solutions in multi-objective integer network flow problems

Author

Listed:
  • Eusébio, Augusto
  • Figueira, José Rui

Abstract

This paper presents a new algorithm for identifying all supported non-dominated vectors (or outcomes) in the objective space, as well as the corresponding efficient solutions in the decision space, for multi-objective integer network flow problems. Identifying the set of supported non-dominated vectors is of the utmost importance for obtaining a first approximation of the whole set of non-dominated vectors. This approximation is crucial, for example, in two-phase methods that first compute the supported non-dominated vectors and then the unsupported non-dominated ones. Our approach is based on a negative-cycle algorithm used in single objective minimum cost flow problems, applied to a sequence of parametric problems. The proposed approach uses the connectedness property of the set of supported non-dominated vectors/efficient solutions to find all integer solutions in maximal non-dominated/efficient facets.

Suggested Citation

  • Eusébio, Augusto & Figueira, José Rui, 2009. "On the computation of all supported efficient solutions in multi-objective integer network flow problems," European Journal of Operational Research, Elsevier, vol. 199(1), pages 68-76, November.
    • Handle: RePEc:eee:ejores:v:199:y:2009:i:1:p:68-76
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00969-7
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Gal, Tomas, 1977. "A general method for determining the set of all efficient solutions to a linear vectormaximum problem," European Journal of Operational Research, Elsevier, vol. 1(5), pages 307-322, September.
    2. Dauer, Jerald P. & Gallagher, Richard J., 1996. "A combined constraint-space, objective-space approach for determining high-dimensional maximal efficient faces of multiple objective linear programs," European Journal of Operational Research, Elsevier, vol. 88(2), pages 368-381, January.
    3. Lee, Haijune & Simin Pulat, P., 1993. "Bicriteria network flow problems: Integer case," European Journal of Operational Research, Elsevier, vol. 66(1), pages 148-157, April.
    4. Hamacher, Horst W. & Pedersen, Christian Roed & Ruzika, Stefan, 2007. "Multiple objective minimum cost flow problems: A review," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1404-1422, February.
    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. Hela Masri & Saoussen Krichen, 2018. "Exact and approximate approaches for the Pareto front generation of the single path multicommodity flow problem," Annals of Operations Research, Springer, vol. 267(1), pages 353-377, August.
    2. Moradi, Siamak & Raith, Andrea & Ehrgott, Matthias, 2015. "A bi-objective column generation algorithm for the multi-commodity minimum cost flow problem," European Journal of Operational Research, Elsevier, vol. 244(2), pages 369-378.

    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. H. P. Benson & E. Sun, 2000. "Outcome Space Partition of the Weight Set in Multiobjective Linear Programming," Journal of Optimization Theory and Applications, Springer, vol. 105(1), pages 17-36, April.
    2. Mingue SUn, 2010. "A Branch-and-Bound Algorithm for Representative Integer Efficient Solutions in Multiple Objective Network Programming Problems," Working Papers 0007, College of Business, University of Texas at San Antonio.
    3. H. P. Benson, 1998. "Hybrid Approach for Solving Multiple-Objective Linear Programs in Outcome Space," Journal of Optimization Theory and Applications, Springer, vol. 98(1), pages 17-35, July.
    4. A.P. Wierzbicki, 1998. "Reference Point Methods in Vector Optimization and Decision Support," Working Papers ir98017, International Institute for Applied Systems Analysis.
    5. Minghe Sun, 2005. "Warm-Start Routines for Solving Augmented Weighted Tchebycheff Network Programs in Multiple-Objective Network Programming," INFORMS Journal on Computing, INFORMS, vol. 17(4), pages 422-437, November.
    6. Przybylski, Anthony & Gandibleux, Xavier & Ehrgott, Matthias, 2008. "Two phase algorithms for the bi-objective assignment problem," European Journal of Operational Research, Elsevier, vol. 185(2), pages 509-533, March.
    7. Ankhili, Z. & Mansouri, A., 2009. "An exact penalty on bilevel programs with linear vector optimization lower level," European Journal of Operational Research, Elsevier, vol. 197(1), pages 36-41, August.
    8. 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.
    9. Serpil Say{i}n & Panos Kouvelis, 2005. "The Multiobjective Discrete Optimization Problem: A Weighted Min-Max Two-Stage Optimization Approach and a Bicriteria Algorithm," Management Science, INFORMS, vol. 51(10), pages 1572-1581, October.
    10. 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.
    11. S. Razavyan, 2016. "A Method for Generating a Well-Distributed Pareto Set in Multiple Objective Mixed Integer Linear Programs Based on the Decision Maker’s Initial Aspiration Level," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(04), pages 1-23, August.
    12. Kalu, Timothy Ch. U., 1999. "An algorithm for systems welfare interactive goal programming modelling," European Journal of Operational Research, Elsevier, vol. 116(3), pages 508-529, August.
    13. Sedeno-Noda, A. & Gonzalez-Martin, C. & Gutierrez, J., 2005. "The biobjective undirected two-commodity minimum cost flow problem," European Journal of Operational Research, Elsevier, vol. 164(1), pages 89-103, July.
    14. Wierzbicki, Andrzej P. & Granat, Janusz, 1999. "Multi-objective modeling for engineering applications: DIDASN++ system," European Journal of Operational Research, Elsevier, vol. 113(2), pages 374-389, March.
    15. Abdelaziz, F. Ben & Lang, P. & Nadeau, R., 1995. "Distributional efficiency in multiobjective stochastic linear programming," European Journal of Operational Research, Elsevier, vol. 85(2), pages 399-415, September.
    16. H. P. Benson, 1998. "Further Analysis of an Outcome Set-Based Algorithm for Multiple-Objective Linear Programming," Journal of Optimization Theory and Applications, Springer, vol. 97(1), pages 1-10, April.
    17. Arevalo Quijada, Mª Teresa & Zapata Reina, Asunción, 1996. "La programación fraccionada múltiple: tratamiento del problema de la producción," Estudios de Economia Aplicada, Estudios de Economia Aplicada, vol. 6, pages 5-24, Diciembre.
    18. Schweigert, D. & Neumayer, P., 1997. "A reduction algorithm for integer multiple objective linear programs," European Journal of Operational Research, Elsevier, vol. 99(2), pages 459-462, June.
    19. A.P. Wierzbicki, 1993. "Augmented Simplex: A Modified and Parallel Version of Simplex Method Based on Multiple Objective and Subdifferential Optimization Approach," Working Papers wp93059, International Institute for Applied Systems Analysis.
    20. Panos Kouvelis & Serpil Sayın, 2006. "Algorithm robust for the bicriteria discrete optimization problem," Annals of Operations Research, Springer, vol. 147(1), pages 71-85, October.

    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:199:y:2009:i:1:p:68-76. 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.