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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Corley H.W.: Efficient spanning trees. J. Optim. Theory Appl. 45, 481–485 (1985)
Ehrgott M., Gandibleux X.: An annotated bibliography of multiobjective combinatorial optimization. OR Spektrum 22, 425–460 (2000)
Ehrgott M., Gandibleux X.: Approximative solution methods for multiobjective combinatorial optimization. Sociedad de Estadística e Investigación Operativa 12(1), 1–89 (2004)
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)
Guerriero F., Musmanno R.: Label correcting methods to solve multicriteria shortest path problems. J. Optim. Theory Appl. 111(3), 589–613 (2001)
Köksalan M.M.: A heuristic approach to bicriteria scheduling. Nav. Res. Logist. 46, 777–789 (1999)
Köksalan M., Lokman B.: Approximating the nondominated frontiers of multi-objective combinatorial optimization problems. Nav. Res. Logist. 56, 191–198 (2009)
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)
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)
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)
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)
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)
Phelps S., Köksalan M.: An interactive evolutionary metaheuristic for multiobjective combinatorial optimization. Manag. Sci. 49, 1726–1738 (2003)
Prim R.C.: Shortest connection networks and some generations. Bell Syst. Tech. J. 36, 1389–1401 (1957)
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)
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)
Steiner S., Radzik T.: Computing all efficient solutions of the biobjective minimum spanning tree problem. Comput. Oper. Res. 35(1), 198–211 (2008)
Steuer R.E.: Multiple Criteria Optimization: Theory, Computation, and Application. Wiley, New York (1986)
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)
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)
Tung C.T., Chew K.L.: A multicriteria pareto-optimal path algorithm. Eur. J. Oper. Res. 62, 203–209 (1992)
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)
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)
Author information
Authors and Affiliations
Corresponding author
Rights 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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-012-9955-7