Generator Sets for the Minkowski Sum Problem -- Theory and Insights
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913672512667648 |
|---|---|
| author | Lyngesen, Mark Gadegaard, Sune Lauth Nielsen, Lars Relund |
| author_facet | Lyngesen, Mark Gadegaard, Sune Lauth Nielsen, Lars Relund |
| contents | This paper considers a class of multi-objective optimization problems known as Minkowski sum problems. Minkowski sum problems have a decomposable structure, where the global nondominated (Pareto) set corresponds to the Minkowski sum of several local nondominated sets. In some cases, the vectors of local sets does not contribute to the generation of the global nondominated set, and may therefore lead to wasted computational efforts. Therefore, we investigate theoretical properties of both necessary and redundant vectors, and propose an algorithm based on bounding sets for identifying unnecessary local vectors. We conduct extensive numerical experiments to test the the impact of varying characteristics of the instances on the resulting global nondominated set and the number of redundant vectors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_18420 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Generator Sets for the Minkowski Sum Problem -- Theory and Insights Lyngesen, Mark Gadegaard, Sune Lauth Nielsen, Lars Relund Optimization and Control 90C29 This paper considers a class of multi-objective optimization problems known as Minkowski sum problems. Minkowski sum problems have a decomposable structure, where the global nondominated (Pareto) set corresponds to the Minkowski sum of several local nondominated sets. In some cases, the vectors of local sets does not contribute to the generation of the global nondominated set, and may therefore lead to wasted computational efforts. Therefore, we investigate theoretical properties of both necessary and redundant vectors, and propose an algorithm based on bounding sets for identifying unnecessary local vectors. We conduct extensive numerical experiments to test the the impact of varying characteristics of the instances on the resulting global nondominated set and the number of redundant vectors. |
| title | Generator Sets for the Minkowski Sum Problem -- Theory and Insights |
| topic | Optimization and Control 90C29 |
| url | https://arxiv.org/abs/2501.18420 |