Skip to main content
SpringerLink
Log in

Finding all nondominated points of multi-objective integer programs

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

We develop exact algorithms for multi-objective integer programming (MIP) problems. The algorithms iteratively generate nondominated points and exclude the regions that are dominated by the previously-generated nondominated points. One algorithm generates new points by solving models with additional binary variables and constraints. The other algorithm employs a search procedure and solves a number of models to find the next point avoiding any additional binary variables. Both algorithms guarantee to find all nondominated points for any MIP problem. We test the performance of the algorithms on randomly-generated instances of the multi-objective knapsack, multi-objective shortest path and multi-objective spanning tree problems. The computational results show that the algorithms work well.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Corley H.W.: Efficient spanning trees. J. Optim. Theory Appl. 45, 481–485 (1985)

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Ehrgott M., Gandibleux X.: Approximative solution methods for multiobjective combinatorial optimization. Sociedad de Estadística e Investigación Operativa 12(1), 1–89 (2004)

    Google Scholar 

  • Gomes da Silva C., Clímaco J., Figueira J.R.: Core problems in bi-criteria 0–1 knapsack problems. Comput. Oper. Res. 35(7), 2292–2306 (2008)

    Article  Google Scholar 

  • Guerriero F., Musmanno R.: Label correcting methods to solve multicriteria shortest path problems. J. Optim. Theory Appl. 111(3), 589–613 (2001)

    Article  Google Scholar 

  • Köksalan M.M.: A heuristic approach to bicriteria scheduling. Nav. Res. Logist. 46, 777–789 (1999)

    Article  Google Scholar 

  • Köksalan M., Lokman B.: Approximating the nondominated frontiers of multi-objective combinatorial optimization problems. Nav. Res. Logist. 56, 191–198 (2009)

    Article  Google Scholar 

  • 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, 932–942 (2006)

    Article  Google Scholar 

  • Lokman, B.: Approaches for Multi-Objective Combinatorial Optimization Problems. Masters Thesis, Industrial Engineering Department, Middle East Technical University, Ankara (2007)

  • Martins E.Q.V.: On a multicriteria shortest path problem. Eur. J. Oper. Res. 16, 236–245 (1984)

    Article  Google Scholar 

  • Mavrotas G., Figueira J.R., Antoniadis A.: Using the idea of expanded core for the exact solution of bi-Objective multi-dimensional knapsack problems. J. Glob. Optim. 49(4), 589–606 (2011)

    Article  Google Scholar 

  • Mavrotas G., Diakoulaki D.: Multi-criteria branch and bound: A vector maximization algorithm for mixed 0-1 multiple objective linear programming. Appl. Math. Comput. 171, 53–71 (2005)

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Phelps S., Köksalan M.: An interactive evolutionary metaheuristic for multiobjective combinatorial optimization. Manag. Sci. 49, 1726–1738 (2003)

    Article  Google Scholar 

  • Prim R.C.: Shortest connection networks and some generations. Bell Syst. Tech. J. 36, 1389–1401 (1957)

    Article  Google Scholar 

  • 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. Discret. Optim. 7(3), 149–165 (2010)

    Article  Google Scholar 

  • Ramos R.M., Alonso S., Sicilia J., Gonzáles C.: The problem of the optimal biobjective spanning tree. Eur. J. Oper. Res. 111, 617–628 (1998)

    Article  Google Scholar 

  • Steiner S., Radzik T.: Computing all efficient solutions of the biobjective minimum spanning tree problem. Comput. Oper. Res. 35(1), 198–211 (2008)

    Article  Google Scholar 

  • Steuer R.E.: Multiple Criteria Optimization: Theory, Computation, and Application. Wiley, New York (1986)

    Google Scholar 

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

    Article  Google Scholar 

  • Sylva J., Crema A.: A method for finding well-dispersed subsets of nondominated vectors for multiple objective mixed integer linear programs. Eur. J. Oper. Res. 180, 1011–1027 (2007)

    Article  Google Scholar 

  • Tung C.T., Chew K.L.: A multicriteria pareto-optimal path algorithm. Eur. J. Oper. Res. 62, 203–209 (1992)

    Article  Google Scholar 

  • Ulungu E.L., Teghem J., Fortemps P.H., Tuyttens D.: MOSA method: a tool for solving multiobjective combinatorial optimization problems. J. Multi-criteria Decis. Anal. 8, 221–236 (1999)

    Article  Google Scholar 

  • Visée M., Teghem J., Pirlot M., Ulungu E.L.: Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem. J. Glob. Optim. 12, 139–155 (1998)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Industrial Engineering Department, TED University, 6420, Ankara, Turkey

    Banu Lokman

  2. Industrial Engineering Department, Middle East Technical University, 06531, Ankara, Turkey

    Murat Köksalan

Authors
  1. Banu Lokman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Murat Köksalan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Banu Lokman.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lokman, B., Köksalan, M. Finding all nondominated points of multi-objective integer programs. J Glob Optim 57, 347–365 (2013). https://doi.org/10.1007/s10898-012-9955-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-012-9955-7

Keywords

Search

Navigation