k-Pareto Optimality-Based Sorting with Maximization of Choice

Jean Ruppert, Marharyta Aleksandrova, Thomas Engel
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:1138-1160, 2022.

Abstract

Topological sorting is an important technique in numerous practical applications, such as information retrieval, recommender systems, optimization, etc. In this paper, we introduce a problem of generalized topological sorting with maximization of choice, that is, of choosing a subset of items of a predefined size that contains the maximum number of equally preferable options (items) with respect to a dominance relation. We formulate this problem in a very abstract form and prove that sorting by k-Pareto optimality yields a valid solution. Next, we show that the proposed theory can be useful in practice. We apply it during the selection step of genetic optimization and demonstrate that the resulting algorithm outperforms existing state-of-the-art approaches such as NSGA-II and NSGA-III. We also demonstrate that the provided general formulation allows discovering interesting relationships and applying the developed theory to different applications.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-ruppert22a, title = { k-Pareto Optimality-Based Sorting with Maximization of Choice }, author = {Ruppert, Jean and Aleksandrova, Marharyta and Engel, Thomas}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {1138--1160}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/ruppert22a/ruppert22a.pdf}, url = {https://proceedings.mlr.press/v151/ruppert22a.html}, abstract = { Topological sorting is an important technique in numerous practical applications, such as information retrieval, recommender systems, optimization, etc. In this paper, we introduce a problem of generalized topological sorting with maximization of choice, that is, of choosing a subset of items of a predefined size that contains the maximum number of equally preferable options (items) with respect to a dominance relation. We formulate this problem in a very abstract form and prove that sorting by k-Pareto optimality yields a valid solution. Next, we show that the proposed theory can be useful in practice. We apply it during the selection step of genetic optimization and demonstrate that the resulting algorithm outperforms existing state-of-the-art approaches such as NSGA-II and NSGA-III. We also demonstrate that the provided general formulation allows discovering interesting relationships and applying the developed theory to different applications. } }
Endnote
%0 Conference Paper %T k-Pareto Optimality-Based Sorting with Maximization of Choice %A Jean Ruppert %A Marharyta Aleksandrova %A Thomas Engel %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-ruppert22a %I PMLR %P 1138--1160 %U https://proceedings.mlr.press/v151/ruppert22a.html %V 151 %X Topological sorting is an important technique in numerous practical applications, such as information retrieval, recommender systems, optimization, etc. In this paper, we introduce a problem of generalized topological sorting with maximization of choice, that is, of choosing a subset of items of a predefined size that contains the maximum number of equally preferable options (items) with respect to a dominance relation. We formulate this problem in a very abstract form and prove that sorting by k-Pareto optimality yields a valid solution. Next, we show that the proposed theory can be useful in practice. We apply it during the selection step of genetic optimization and demonstrate that the resulting algorithm outperforms existing state-of-the-art approaches such as NSGA-II and NSGA-III. We also demonstrate that the provided general formulation allows discovering interesting relationships and applying the developed theory to different applications.
APA
Ruppert, J., Aleksandrova, M. & Engel, T.. (2022). k-Pareto Optimality-Based Sorting with Maximization of Choice . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:1138-1160 Available from https://proceedings.mlr.press/v151/ruppert22a.html.

Related Material