[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Multi-Objective Integer Programming: An Improved Recursive Algorithm

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

This paper introduces an improved recursive algorithm to generate the set of all nondominated objective vectors for the Multi-Objective Integer Programming (MOIP) problem. We significantly improve the earlier recursive algorithm of Özlen and Azizoğlu by using the set of already solved subproblems and their solutions to avoid solving a large number of IPs. A numerical example is presented to explain the workings of the algorithm, and we conduct a series of computational experiments to show the savings that can be obtained. As our experiments show, the improvement becomes more significant as the problems grow larger in terms of the number of objectives.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Algorithm 2

Similar content being viewed by others

References

  1. Ehrgott, M.: Multicriteria Optimization. Springer, Berlin (2005)

    MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

  3. Abbas, M., Chaabane, D.: Optimizing a linear function over an integer efficient set. Eur. J. Oper. Res. 174(2), 1140–1161 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  4. Jorge, J.: An algorithm for optimizing a linear function over an integer efficient set. Eur. J. Oper. Res. 195(1), 98–103 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  5. Ozlen, M., Azizoğlu, M., Burton, B.A.: Optimising a nonlinear utility function in multi-objective integer programming. J. Glob. Optim. 56(1), 93–102 (2013)

    Article  MATH  Google Scholar 

  6. Przybylski, A., Gandibleux, X., Ehrgott, M.: A recursive algorithm for finding all nondominated extreme points in the outcome set of a multiobjective integer programme. INFORMS J. Comput. 22(3), 371–386 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  7. Özpeynirci, Ö., Köksalan, M.: An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs. Manag. Sci. 56(12), 2302–2315 (2010)

    Article  MATH  Google Scholar 

  8. Benson, H.P., Sun, E.: Outcome space partition of the weight set in multiobjective linear programming. J. Optim. Theory Appl. 105(1), 17–36 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  9. Benson, H.P., Sun, E.: A weight set decomposition algorithm for finding all efficient extreme points in the outcome set of a multiple objective linear program. Eur. J. Oper. Res. 139(1), 26–41 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  10. Klein, D., Hannan, E.: An algorithm for the multiple objective integer linear programming problem. Eur. J. Oper. Res. 9(4), 378–385 (1982)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  12. Laumanns, M., Thiele, L., Zitzler, E.: An adaptive scheme to generate the Pareto front based on the epsilon-constraint method. In: Branke, J., Deb, K., Miettinen, K., Steuer, R.E. (eds.) Practical Approaches to Multi-Objective Optimization, Dagstuhl Seminar Proceedings, vol. 04461. Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl (2005)

    Google Scholar 

  13. Laumanns, M., Thiele, L., Zitzler, E.: An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. Eur. J. Oper. Res. 169(3), 932–942 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  14. Przybylski, A., Gandibleux, X., Ehrgott, M.: A two-phase method for multi-objective integer programming and its application to the assignment problem with three objectives. Discrete Optim. 7(3), 149–165 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  15. Burton, B., Ozlen, M.: Projective geometry and the outer approximation algorithm for multiobjective linear programming (2010). arXiv:1006.3085

  16. Przybylski, A., Gandibleux, X., Ehrgott, M.: Computational results for four exact methods to solve the three-objective assignment problem. Lect. Notes Econ. Math. Syst. 618, 79–88 (2009)

    Article  Google Scholar 

Download references

Acknowledgements

We are thankful to anonymous reviewers for their constructive comments that helped to improve this paper substantially. Dr. Marco Laumanns kindly sent us the code and problem instances of Laumanns et al. [12]. Dr. Özgur Özpeynirci kindly sent us their problem generator and instances from Özpeynirci and Köksalan [7]. Dr. Anthony Przybylski kindly sent us their problem instances from Przybylski et al. [14].

The second author is supported by the Australian Research Council under the Discovery Projects funding scheme (project DP1094516).

Author information

Authors and Affiliations

  1. School of Mathematical and Geospatial Sciences, RMIT University, Melbourne, VIC 3000, Australia

    Melih Ozlen & Cameron A. G. MacRae

  2. School of Mathematics and Physics, University of Queensland, Brisbane, QLD 4072, Australia

    Benjamin A. Burton

Authors
  1. Melih Ozlen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Benjamin A. Burton
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Cameron A. G. MacRae
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Melih Ozlen.

Additional information

Communicated by Harold P. Benson.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ozlen, M., Burton, B.A. & MacRae, C.A.G. Multi-Objective Integer Programming: An Improved Recursive Algorithm. J Optim Theory Appl 160, 470–482 (2014). https://doi.org/10.1007/s10957-013-0364-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-013-0364-y

Keywords

Search

Navigation