Representing the Non-dominated Set of Multi-objective Network Problems by Supported Non-dominated Points

Source: arXiv:2607.11821 · Published 2026-07-13 · By David Könen, Lara Löhken, Michael Stiglmayr

TL;DR

This work investigates the suitability of supported non-dominated points as representations of the Pareto front in multi-objective network optimization problems, focusing on differences between binary/low-capacity and capacitated flow problems. Prior research showed that extreme supported points suffice as high-quality approximations for binary combinatorial problems like knapsack or assignment problems. The authors provide evidence that this result does not generalize to capacitated network flow problems, where supported non-dominated points exceed extreme supported ones in number and offer superior representation quality. However, supported sets themselves can be large, so the paper proposes using them as candidate pools for selecting small fixed-size subsets rather than relying on the entire non-dominated set. Empirical experiments on multiple network problem classes using established quality metrics demonstrate that restricting subset selection to supported points yields nearly the same representational quality as selection from the full non-dominated set, significantly improving computational practicality. The paper also makes code and test instances publicly available for reproducibility. Overall, the study refines the understanding of supported points’ representational power in network optimization and offers practical guidance for producing manageable high-quality Pareto front approximations.

Key findings

• In binary network problems (e.g. minimum spanning tree), the number of supported (YS) and extreme supported (YES) non-dominated points nearly coincide, and YES alone provides a high-quality representation.
• In capacitated flow problems like the multi-objective minimum cost flow (MOIMCF), YS is significantly larger than YES and offers substantially better representation quality according to coverage error, hypervolume ratio, and ε-indicator.
• Representation quality of YES decreases as arc capacities increase, while YS remains consistently high in quality.
• Selecting fixed-size (e.g. 5–20 points) representations from YS yields nearly the same coverage error and hypervolume ratio as selection from the entire non-dominated set YN, but with much lower computational cost.
• The maximum coverage error for supported representations was around 0.075 in examples versus 0.267 for extreme supported only (Fig. 3.1).
• Hypervolume ratio for YS representations reached 0.97 compared to 0.73 for YES alone (Fig. 3.2).
• All experiments were conducted on multiple classes including MOMST, MOSP, BCTP/BGCTP, and MOIMCF with varying graph sizes and objective counts up to 5.
• Test instances and source code are publicly provided to enable reproducibility and future extensions.

Threat model

Not applicable; this paper focuses on multi-objective optimization theory and empirical evaluation of Pareto set representation quality in network problems rather than adversarial threat scenarios.

Methodology — deep read

1. Threat Model & Assumptions: The adversary context is not explicitly considered; this is a methodological study focusing on multi-objective integer linear programs modeling network optimization problems, assuming a known complete non-dominated set (YN) for evaluation. Supported points are defined via weighted sum scalarizations with positive weights (Λp). The study differentiates unsupported, supported, and extreme supported non-dominated points.

2. Data: The authors generate synthetic instances for multiple problem classes: multi-objective minimum spanning tree (MOMST), multi-objective shortest path (MOSP), bi-objective cable-trench problems (BCTP/BGCTP), and multi-objective minimum cost flow (MOIMCF). Instance generation uses established approaches: NETGEN for MOIMCF, random spanning trees with extra arcs for MOMST and BCTP, and a re-implemented NetMaker for MOSP. Each test class comprises 15 instances varying in size, arc capacities (especially for MOIMCF), and cost coefficients. Objective counts range mostly between 2 and 5. All instances and generation code are publicly available.

3. Architecture/Algorithm: The complete non-dominated set YN is computed using known exact algorithms—Defining Point Algorithm for MOIMCF/MOSP/BCTP, and problem-specific branch-and-cut for MOMST. Then sets of supported points YS and extreme supported points YES are extracted from YN by solving linear programs derived from Sayın (2024). Supportedness is tested by checking existence of weighting vectors λ producing a given point as an optimum of the weighted sum scalarization. Extreme supported points are vertices of the upper image. Candidate sets for fixed-size representations are formed from these subsets.

4. Training Regime: Not applicable; this is an empirical optimization study rather than fitted ML.

5. Evaluation Protocol: Representations R are evaluated with respect to the full non-dominated set YN (treated as ground truth). Four main quality metrics are computed: coverage error (maximum weighted Chebyshev distance from any point in YN to nearest point in R), uniformity (minimum distance between points in R), hypervolume ratio (dominated volume by R divided by dominated volume by YN, reference point is shifted Nadir point), and ε-indicator (smallest scaling factor so that every YN point is dominated by some R point). These metrics capture worst-case approximation, diversity, and multi-dimensional coverage quality. Fixed-size subsets (5–20 points) are optimized w.r.t these metrics either from the full YN or restricted candidate sets YS and YES to assess quality loss from restriction.

6. Reproducibility: All computational code, instance generators, and test instances are publicly available in an associated repository referenced by the authors (Könen et al., 2026). Computations use C++ with CPLEX 22.1.1 and open-source hypervolume libraries. Hardware specs are provided. While runtimes are not the focus, detailed methodology is presented enabling independent reproduction.

Concrete Example: For a BOIMCF instance with 10 non-dominated points, coverage error of 0.075 is achieved using supported non-dominated points YS, while extreme supported points YES only achieved 0.267 (Fig. 3.1). The hypervolume ratio even more clearly highlights quality differences (0.97 vs 0.73) (Fig. 3.2). This example illustrates how capacitated flow problems yield many supported points between extreme points, reducing approximation error when included.

Technical innovations

• Demonstration that the equivalence between extreme supported points and high-quality Pareto set representations in binary problems does not generalize to capacitated network flow problems.
• Proposal to use supported non-dominated points as computationally efficient candidate sets for subset selection of fixed-size Pareto front representations.
• Comprehensive empirical comparison of coverage error, hypervolume ratio, and ε-indicator quality metrics on multiple multi-objective network optimization problems, including capacitated flows.
• Release of public instance generators and code supporting reproducibility in multi-objective combinatorial network optimization representation research.

Datasets

• Synthetic MOMST instances — 15 per configuration — Generated via random spanning trees + arcs
• Synthetic MOSP instances — 15 per configuration — Generated via re-implemented NetMaker approach
• Synthetic BCTP/BGCTP instances — 15 per configuration — Similar generation as MOMST
• Synthetic MOIMCF instances — 15 per configuration — Generated using NETGEN adapted parameters

Baselines vs proposed

• Extreme supported non-dominated points (YES) only: coverage error ~0.267 vs supported set (YS) coverage error ~0.075
• YES hypervolume ratio: 0.73 vs YS hypervolume ratio: 0.97 on example BOIMCF instance
• Fixed-size subset selected from full non-dominated set YN: near identical coverage and hypervolume to subsets selected from YS set
• YS size substantially larger than YES in capacitated problems, but offers superior quality vs YES subset alone

Limitations

• Computational experiments limited to up to five objectives due to scalability constraints; higher-dimensional Pareto sets not evaluated.
• Complete non-dominated sets YN are assumed known a priori; real-world problems may not admit full enumeration.
• Evaluation focuses on synthetic benchmark instances; generalization to complex real-world network data requires confirmation.
• Runtime and computational cost analysis is minimal, with main focus on representational quality rather than efficiency metrics.
• Adversarial or noisy scenarios where input data or cost vectors are uncertain are not considered.

Open questions / follow-ons

• How do supported/non-supported set size and quality scale with increasing numbers of objectives beyond five?
• Can heuristic or approximation algorithms leveraging supported points provide practical Pareto front approximations in large-scale real networks?
• What are the impacts of uncertainty in network parameters or imprecise cost coefficients on supported point representations?
• Could integration of supported points improve interactive decision-making or online multi-objective optimization workflows?

Why it matters for bot defense

From a bot-defense and CAPTCHA perspective, this study’s insights on efficiently representing high-dimensional Pareto fronts have indirect relevance. Multi-objective network optimization models can arise in designing robust detection or authentication systems that balance security, usability, and computational cost. The paper’s demonstration that supported non-dominated points serve as high-quality, computationally tractable representations suggests that similar approaches might help efficiently characterize trade-offs in CAPTCHA difficulty versus user friction or attack resilience. Moreover, using supported points as candidate pools for fixed-size subset selection aligns with the practical need to present only a small number of challenge parameter options to users or systems while preserving representational diversity. While the paper does not address security or adversarial aspects explicitly, its methods for multi-objective solution set summarization could aid researchers and practitioners modeling CAPTCHA parameter tuning or bot-defense strategy optimization under multiple competing criteria.

Cite

@article{arxiv2607_11821,
  title={ Representing the Non-dominated Set of Multi-objective Network Problems by Supported Non-dominated Points },
  author={ David Könen and Lara Löhken and Michael Stiglmayr },
  journal={arXiv preprint arXiv:2607.11821},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.11821}
}

Read the full paper

• arXiv:2607.11821 (abstract)
• arXiv:2607.11821 (PDF)