An Output-Polynomial Time Algorithm to Determine all Supported Efficient Solutions for Multi-Objective Integer Network Flow Problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918039495114752 |
|---|---|
| author | Könen, David Stiglmayr, Michael |
| author_facet | Könen, David Stiglmayr, Michael |
| contents | This paper addresses the problem of enumerating all supported efficient solutions for a linear multi-objective integer minimum cost flow problem (MOIMCF). It derives an output-polynomial time algorithm to determine all supported efficient solutions for MOIMCF problems. This is the first approach to solve this general problem in output-polynomial time. Moreover, we prove that the existence of an output-polynomial time algorithm to determine all weakly supported nondominated vectors (or all weakly supported efficient solutions) for a MOIMCF problem with a fixed number of d >= 3 objectives can be excluded unless P = NP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_12867 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | An Output-Polynomial Time Algorithm to Determine all Supported Efficient Solutions for Multi-Objective Integer Network Flow Problems Könen, David Stiglmayr, Michael Optimization and Control This paper addresses the problem of enumerating all supported efficient solutions for a linear multi-objective integer minimum cost flow problem (MOIMCF). It derives an output-polynomial time algorithm to determine all supported efficient solutions for MOIMCF problems. This is the first approach to solve this general problem in output-polynomial time. Moreover, we prove that the existence of an output-polynomial time algorithm to determine all weakly supported nondominated vectors (or all weakly supported efficient solutions) for a MOIMCF problem with a fixed number of d >= 3 objectives can be excluded unless P = NP. |
| title | An Output-Polynomial Time Algorithm to Determine all Supported Efficient Solutions for Multi-Objective Integer Network Flow Problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2305.12867 |