License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2023.9
URN: urn:nbn:de:0030-drops-183599
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18359/
Tamby, Satya ;
Vanderpooten, Daniel
Optimizing over the Efficient Set of a Multi-Objective Discrete Optimization Problem
Abstract
Optimizing over the efficient set of a discrete multi-objective problem is a challenging issue. The main reason is that, unlike when optimizing over the feasible set, the efficient set is implicitly characterized. Therefore, methods designed for this purpose iteratively generate efficient solutions by solving appropriate single-objective problems. However, the number of efficient solutions can be quite large and the problems to be solved can be difficult practically. Thus, the challenge is both to minimize the number of iterations and to reduce the difficulty of the problems to be solved at each iteration.
In this paper, a new enumeration scheme is proposed. By introducing some constraints and optimizing over projections of the search region, potentially large parts of the search space can be discarded, drastically reducing the number of iterations. Moreover, the single-objective programs to be solved can be guaranteed to be feasible, and a starting solution can be provided allowing warm start resolutions. This results in a fast algorithm that is simple to implement.
Experimental computations on two standard multi-objective instance families show that our approach seems to perform significantly faster than the state of the art algorithm.
BibTeX - Entry
@InProceedings{tamby_et_al:LIPIcs.SEA.2023.9,
author = {Tamby, Satya and Vanderpooten, Daniel},
title = {{Optimizing over the Efficient Set of a Multi-Objective Discrete Optimization Problem}},
booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)},
pages = {9:1--9:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-279-2},
ISSN = {1868-8969},
year = {2023},
volume = {265},
editor = {Georgiadis, Loukas},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18359},
URN = {urn:nbn:de:0030-drops-183599},
doi = {10.4230/LIPIcs.SEA.2023.9},
annote = {Keywords: discrete optimization, multi-objective optimization, non-dominated set, efficient set}
}
|
Keywords: |
|
discrete optimization, multi-objective optimization, non-dominated set, efficient set |
|
Collection: |
|
21st International Symposium on Experimental Algorithms (SEA 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
19.07.2023 |
