Representing the Non-dominated Set of Multi-objective Network Problems by Supported Non-dominated Points
2026-07-13 • Discrete Mathematics
Discrete MathematicsNeural and Evolutionary Computing
AI summaryⓘ
The authors study how to best represent solutions in problems where many good options exist, specifically in multi-objective combinatorial optimization. They find that in capacitated network problems, the quality of using only extreme supported points worsens as capacity increases, but using all supported points still works well. Because computing all non-dominated solutions is costly and produces too many options, the authors propose using supported points as a smaller, manageable set to pick from. Their tests show this smaller set nearly matches the quality of selections made from the full set, making it a practical compromise.
multi-objective combinatorial optimizationnon-dominated pointssupported pointscapacitated network optimizationextreme pointssubset selectionquality indicatorsrepresentation quality
Authors
David Könen, Lara Löhken, Michael Stiglmayr
Abstract
In multi-objective combinatorial optimization, unsupported non-dominated points typically outnumber supported points and are often significantly more challenging to compute. Recent studies show that extreme supported non-dominated points provide high-quality representations of the non-dominated set for certain binary problems. We demonstrate that this observation does not generalize to capacitated network optimization problems: representation quality decreases with increasing arc capacities, whereas supported non-dominated points consistently provide high-quality representations with respect to several quality indicators. However, supported point sets may still be too large in practical applications, where only a small, fixed number of alternatives is typically desired. Selecting fixed-size representations from the non-dominated set requires its computationally expensive generation and thus diminishes the computational advantages that representations are intended to provide. We therefore suggest the (extreme) supported points as alternative candidate sets in subset selection problems. Our numerical results show that restricting the candidate set to supported non-dominated points yields fixed-size representations of nearly the same quality as those selected from the complete non-dominated set. Overall, supported non-dominated points serve both as high-quality representations and as reasonable candidate sets for subset selection.