Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Variants of the \( \varepsilon \)-constraint method for biobjective integer programming problems: application to p-median-cover problems

  • Original Article
  • Published:
Mathematical Methods of Operations Research Aims and scope Submit manuscript

Abstract

We conduct an in-depth analysis of the \(\varepsilon \)-constraint method (ECM) for finding the exact Pareto front for biobjective integer programming problems. We have found up to six possible different variants of the ECM. We first discuss the complexity of each of these variants and their relationship with other exact methods for solving biobjective integer programming problems. By extending some results of Neumayer and Schweigert (OR Spektrum 16:267–276, 1994), we develop two variants of the ECM, both including an augmentation term and requiring \(N+1\) integer programs to be solved, where N is the number of nondominated points. In addition, we present another variant of the ECM, based on the use of elastic constraints and also including an augmentation term. This variant has the same complexity, namely \(N+1\), which is the minimum reached for any exact method. A comparison of the different variants is carried out on a set of biobjective location problems which we call p-median-cover problems; these include the objectives of the p-median and the maximal covering problems. As computational results show, for this class of problems, the augmented ECM with elastic constraint is the most effective variant for finding the Pareto front in an exact manner.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  • Bérubé JF, Gendreau M, Potvin JY (2009) An exact \(\varepsilon \)-constraint method for bi-objective combinatorial optimization problems: application to the traveling salesman problem with profits. Eur J Oper Res 194(1):39–50

    Article  MathSciNet  MATH  Google Scholar 

  • Boland N, Charkhgard H, Savelsbergh MA (2015) Criterion space search algorithms for biobjective integer programming: the balanced box method. INFORMS J Comput 27:735–754

    Article  MathSciNet  MATH  Google Scholar 

  • Chalmet LG, Lemonidis L, Elzinga DJ (1986) An algorithm for the bi-criterion integer programming problem. Eur J Oper Res 25:292–300

    Article  MathSciNet  MATH  Google Scholar 

  • Chankong V, Haimes Y (1983) Multiobjective decision making. Theory and methodology. Elsevier, Amsterdam

    MATH  Google Scholar 

  • Cohon JL (1978) Multiobjective programming and planning. Academic Press, London

    MATH  Google Scholar 

  • Dächert K, Gorski J, Klamroth K (2012) An augmented weighted Tchebycheff method with adaptively chosen parameters for discrete bicriteria optimization problems. Comput Oper Res 39:2929–2943

    Article  MathSciNet  MATH  Google Scholar 

  • Daskin MS (2013) Network and discrete location. Models, algorithms and applications, 2nd edn. Wiley, London

    MATH  Google Scholar 

  • Ehrgott M (2005) Multicriteria optimization. Springer, Berlin

    MATH  Google Scholar 

  • Ehrgott M (2006) A discussion of scalarization techniques for multiple objective integer programming. Ann Oper Res 147:343–360

    Article  MathSciNet  MATH  Google Scholar 

  • Ehrgott M, Gandibleux X (2000) A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum 22:425–460

    Article  MathSciNet  MATH  Google Scholar 

  • Ehrgott M, Gandibleux X (2003) Multiobjective combinatorial optimization. Theory, methodology and applications. In: Ehrgott M, Gandibleux X (eds) Multiple criteria optimization: state of the art annotated bibliographic surveys. Surveys international series in operations research and management science, vol 52. Kluwer Academic Publishers, Dordrecht, pp 369–444

    Google Scholar 

  • Ehrgott M, Ruzika S (2008) An improved epsilon constraint method for multiobjective programming. J Optim Theory Appl 138(3):375–396

    Article  MathSciNet  MATH  Google Scholar 

  • Ehrgott M, Ryan D (2002) Constructing robust crew schedules with bicriteria optimization. J Multicriteria Decis Anal 11:139–150

    Article  MATH  Google Scholar 

  • FICO Xpress Optimization Suite (2016) XPRESS-MP optimizer reference manual. Fair Isaac Corporation, Leamington Spa

    Google Scholar 

  • Figueira J, Greco S, Ehrgott M (2005) Multiple criteria decision analysis: state of the art surveys. Springer, Berlin

    Book  MATH  Google Scholar 

  • Filippi C, Stevanato E (2013) A two-phase method for bi-objective combinatorial optimization and its application to the TSP with profits. Algorithm Operations Research 7:125–139

    MathSciNet  MATH  Google Scholar 

  • Grandinetti L, Guerriero F, Lagana D, Pisacane O (2010) An approximate \(\varepsilon \)-constraint method for the multi-objective undirected capacitated arc routing problem. In: Paola F (ed) 9th International symposium on experimental algorithms SEA 2010. Springer, Berlin

  • Haimes Y, Lasdon L, Wismer D (1971) On a bicriterion formulation of the problems of integrated system identification and system optimization. IEEE Trans Syst Man Cybern Soc 1:296–297

    MathSciNet  MATH  Google Scholar 

  • Hamacher HW, Pedersen CR, Ruzika S (2007) Finding representative systems for discrete bicriterion optimization problems. Oper Res Lett 35(3):336–344

    Article  MathSciNet  MATH  Google Scholar 

  • Hugot H, Vanderpooten D, Vanpeperstraete JM (2006) A bi-criteria approach for the data association problem. Ann Oper Res 147:217–234

    Article  MathSciNet  MATH  Google Scholar 

  • Laumanns M, Thiele L, Zitzler E (2006) An efficient, adaptive parameter scheme for metaheuristic based on the \(\varepsilon \)-constraint method. Eur J Oper Res 169:932–942

  • Mavrotas G (2009) Effective implementation of the \(\varepsilon \)-constraint method in multi-objective mathematical programming problems. Appl Math Comput 213:455–465

    MathSciNet  MATH  Google Scholar 

  • Nemhauser GL, Wolsey LA (1999) Integer and combinatorial optimization. Wiley, London

    MATH  Google Scholar 

  • Neumayer P, Schweigert D (1994) Three algorithms for bicriteria integer linear programs. OR Spektrum 16:267–276

    Article  MathSciNet  MATH  Google Scholar 

  • Özpeynirci O, Köksalan M (2007) Pyramidal tours and multiple objectives. J Glob Optim 48:569–582

    Article  MathSciNet  MATH  Google Scholar 

  • Özlen M, Azizoǧlu M (2009) Multi-objective integer programming: a general approach for generating all nondominated solutions. Eur J Oper Res 199(1):25–35

    Article  MATH  Google Scholar 

  • Ralphs TK, Saltzman MJ, Wiecek MM (2006) An improved algorithm for solving biobjective integer programs. Ann Oper Res 147:43–70

    Article  MathSciNet  MATH  Google Scholar 

  • Ramesh R, Karwan MH, Zionts S (1990) An interactive method for bicriteria integer programming. IEEE Trans Systems Man Cybern Soc 20(3):395–403

    Article  MathSciNet  MATH  Google Scholar 

  • Sáez-Aguado J, Trandafir PC (2012) Some heuristic methods for solving p-median problems with a coverage constraint. Eur J Oper Res 220:320–327

    Article  MathSciNet  MATH  Google Scholar 

  • Soland RM (1979) Multicriteria optimization: a general characterization of efficient solutions. Decis Sci 10:26–38

    Article  Google Scholar 

  • Steuer R (1985) Multiple criteria optimization: theory. Computation and application. Wiley, New York

    MATH  Google Scholar 

  • Sylva J, Crema A (2004) A method for finding the set of nondominated vectors for multiple objective integer linear programs. Eur J Oper Res 158:46–55

    Article  MATH  Google Scholar 

  • Ulungu EL, Teghem J (1994) Multi-objective combinatorial optimization problems: a survey. J Multi Criteria Decis Anal 3:83–104

    Article  MATH  Google Scholar 

Download references

Acknowledgements

The authors wish to thank the anonymous referees for their useful suggestions and comments that improved the paper, and to FICO for providing the Xpress Optimizer application, which has been used to obtain the computational results.

Author information

Authors and Affiliations

  1. Department of Statistics and Operational Research, University of Valladolid, Paseo de Belen 7, 47011, Valladolid, Spain

    Jesús Sáez-Aguado

  2. Department of Statistics and Operational Research, Public University of Navarre, Avda. de Tarazona s/n, 31500, Tudela, Spain

    Paula Camelia Trandafir

Authors
  1. Jesús Sáez-Aguado
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paula Camelia Trandafir
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jesús Sáez-Aguado.

Appendix

Appendix

See Tables 3, 4, 5, 6 and 7.

Table 3 Computational performance, data set 1, \(p=8\), DC \(=\) 10
Full size table
Table 4 Computational performance, data set 2, \(p=8\), DC \(=\) 15
Full size table
Table 5 Computational performance, data set 2, \(p=15\), DC \(=\) 9
Full size table
Table 6 Computational performance, data set 2, \(p=20\), DC \(=\) 10
Full size table
Table 7 Computational performance, data set 2, \(p=30\), DC \(=\) 8
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sáez-Aguado, J., Trandafir, P.C. Variants of the \( \varepsilon \)-constraint method for biobjective integer programming problems: application to p-median-cover problems. Math Meth Oper Res 87, 251–283 (2018). https://doi.org/10.1007/s00186-017-0618-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00186-017-0618-9

Keywords

Search

Navigation