Abstract
This paper studies output-sensitive algorithms for enumeration problems in multiobjective combinatorial optimization (MOCO). We develop two methods for enumerating the extreme points of the Pareto-frontier of MOCO problems. The first method is based on a dual variant of Benson’s algorithm, which has been originally proposed for multiobjective linear optimization problems. We prove that the algorithm runs in output polynomial time for every fixed number of objectives if the weighted-sum scalarization can be solved in polynomial time. Hence, we propose the first algorithm which solves this general problem in output polynomial time. We also propose a new lexicographic version of the dual Benson algorithm that runs in incremental polynomial time in the case that the lexicographic optimization variant can be solved in polynomial time. As a consequence, the extreme points of the Pareto-frontier of the multiobjective spanning tree problem as well as the multiobjective global min-cut problem can be computed in polynomial time for a fixed number of objectives. Our computational experiments show the practicability of our improved algorithm: We present the first computational study for computing the extreme points of the multiobjective version of the assignment problem with five and more objectives. We also empirically investigate the running time behavior of our new lexicographic version compared to the original algorithm.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agarwal, P.K., Eppstein, D., Guibas, L.J., Henzinger, M.R.: Parametric and kinetic minimum spanning trees. In: IEEE FoCS, pp. 596–605 (1998)
Aissi, H., Mahjoub, A.R., McCormick, S.T., Queyranne, M.: A strongly polynomial time algorithm for multicriteria global minimum cuts. In: Lee, J., Vygen, J. (eds.) IPCO 2014. LNCS, vol. 8494, pp. 25–36. Springer, Heidelberg (2014)
Aneja, Y.P., Nair, K.P.K.: Bicriteria transportation problem. Management Science 25(1), 73–78 (1979)
Avis, D., Fukuda, K.: A pivoting algorithm for convex hulls and vertex enumeration of arrangements of polyhedra. Discrete and Computational Geometry 8(1), 295–313 (1992)
Brunsch, T., Röglin, H.: Improved smoothed analysis of multiobjective optimization. In: ACM SToC, pp. 407–426 (2012)
Chazelle, B.: An optimal convex hull algorithm in any fixed dimension. Discrete Computational Geometry 10, 377–409 (1993)
Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum 22, 425–460 (2000)
Ehrgott, M., Löhne, A., Shao, L.: A dual variant of Benson’s “outer approximation algorithm” for multiple objective linear programming. Journal of Global Optimization 52, 757–778 (2012)
Fukuda, K., Prodon, A.: Double description method revisited. In: Deza, M., Manoussakis, I., Euler, R. (eds.) CCS 1995. LNCS, vol. 1120, pp. 91–111. Springer, Heidelberg (1996)
Ganley, J.L., Golin, M.J., Salowe, J.S.: The multi-weighted spanning tree problem. In: Li, M., Du, D.-Z. (eds.) COCOON 1995. LNCS, vol. 959, pp. 141–150. Springer, Heidelberg (1995)
Hamel, A.H., Löhne, A., Rudloff, B.: Benson type algorithms for linear vector optimization and applications. arXiv:1302.2415 [math.OC] (July 2013)
Heyde, F., Löhne, A.: Geometric duality in multiple objective linear programming. SIAM Journal of Optimization 19(2), 836–845 (2008)
Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Information Processing Letters 27, 119–123 (1988)
Okamoto, Y., Uno, T.: A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 609–620. Springer, Heidelberg (2007)
Özpeynirci, Ö., Köksalan, M.: An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs. Management Science 56(12), 2302–2315 (2010)
Papadimitriou, C.H., Yannakakis, M.: On the approximability of trade-offs and optimal access of web sources. In: IEEE FoCS, pp. 86–92 (2000)
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 Journal on Computing 22(3), 371–386 (2010)
Seidel, R.: The upper bound theorem for polytopes: an easy proof of its asymptotic version. Computational Geometry 5, 115–116 (1995)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bökler, F., Mutzel, P. (2015). Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems. In: Bansal, N., Finocchi, I. (eds) Algorithms - ESA 2015. Lecture Notes in Computer Science(), vol 9294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48350-3_25
Download citation
DOI: https://doi.org/10.1007/978-3-662-48350-3_25
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48349-7
Online ISBN: 978-3-662-48350-3
eBook Packages: Computer ScienceComputer Science (R0)