acceptodds
Under review as a conference paper at ICLR 2027

Does Fairness Help in Multi-Objective Local Search

Abstract

Local search, a long-established optimisation technique, has recently attracted renewed attention in multi-objective optimisation. It has been successfully applied to a wide range of practical problems and has recently been shown to outperform well-established evolutionary algorithms. Despite these promising results, the search behaviour of different local search methods, particularly when and why one method is better than another, remains poorly understood. In this paper, we provide both empirical and theoretical insights into this question. We show that local search methods that select solutions more fairly (i.e., according to the number of times they have been visited) generally achieve faster search progress, particularly during the early stages of optimisation. We validate these findings using three local search methods with different levels of fairness on a diverse suite of well-studied problems, including the multi-objective knapsack, travelling salesman, resource allocation, NK-landscape, and quadratic assignment problems.

Primary area:
optimization
Keywords:
Multi-Objective Optimisation, Multi-Objective Local Search

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_ZUASOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates whether fairly allocating neighbour-evaluation budgets across archive solutions can accelerate Pareto-based multi-objective local search. The authors compare s-PLS, which systematically scans neighbourhoods; r-PLS, which selects archive solutions uniformly at random; and f-PLS, which prioritises the least-visited solutions. Under a fixed-archive model, the paper uses an arbitrary discrete distribution to characterise good-neighbour counts, derives the expected numbers of evaluations required by s-PLS and r-PLS to find the next good neighbour, and establishes sufficient conditions for comparing their efficiency. Under a fair-round model, it also proves that the waiting time of f-PLS is stochastically no greater than that of r-PLS.

The paper also presents experiments covering five classes of bi-objective combinatorial optimisation problems with 100, 200, and 500 variables. The results show that fairer strategies achieve better early-stage performance and final hypervolume (HV) on several problems, although these advantages do not hold universally.

Critical strengths

The paper provides a clear analytical framework for identifying when fairness is beneficial, rather than making a blanket claim that fairness is always better. The experiments demonstrate the practical relevance of the budget allocation problem under study.

Critical weaknesses
  • The theoretical contribution offers limited new insight and has a restricted scope of applicability, while the correspondence between its strongest guarantee and the algorithm’s actual search states remains unclear. The analysis is confined to the first success under a fixed archive and prescribed sampling schemes, and its additional predictive value for actual dynamic search has not been sufficiently demonstrated. The two main threshold theorems likewise provide sufficient conditions derived from bounds on local waiting times, rather than a characterisation of the entire search process.

  • The theory and experiments lack a direct, quantitative connection, leaving the paper’s main explanatory contribution insufficiently supported. The theory examines how many evaluations are needed to find the next good neighbour from the same fixed archive. The experiments primarily examine the HV achieved within a given budget by the different algorithms’ evolving archives. These quantities are not equivalent. Different good neighbours may contribute differently to HV, and discovering new solutions also changes the subsequent archive and search opportunities.

  • The paper’s current contributions seem more directly relevant to the multi-objective optimisation and heuristic search communities, with limited impact on the ICLR community.

Questions for authors
  • The paper derives waiting-time relationships among the three PLS strategies for finding the next good neighbour under a fixed archive, but does not directly validate how well these theoretical results explain actual search behaviour. Could the authors extract archive snapshots from the experiments and, using the same snapshots for each strategy under the corresponding theoretical assumptions, compare theoretically predicted and empirically measured waiting times? Could they also report the proportion of archive states satisfying the sufficient conditions in Theorems 1 and 2 across different problems and search stages? Furthermore, do shorter waiting times correspond to larger HV gains per evaluation?

  • Proposition 2 appears to omit an important assumption about the initial visit counts. The proof in Appendix C.7 relies on a complete fair-round structure, which requires equal initial visit counts across all archive solutions. However, Algorithm A.3 retains historical visit counts and initialises newly added solutions with a count of zero. Thus, the proposition does not appear to apply directly to arbitrary search states encountered during actual execution.

  • The theoretical analysis focuses on the number of evaluations needed to find the first good neighbour, which aligns more closely with the stopping condition of the s-PLSs\text{-PLS}’ first-improvement variant. However, the main experiments use s-PLS with full neighbourhood scans, while the first-improvement variants are compared only in the appendix. Why was the variant not used as a primary experimental baseline to better align the theoretical analysis and experimental setup?

  • In the experiments, all problem sizes use the same absolute evaluation budget, while for some problems the neighbourhood size grows quadratically with the number of variables. I therefore suspect that the more pronounced performance gaps at larger problem sizes may primarily reflect an anytime-performance advantage under relatively tighter budgets, rather than a separate, independent advantage.

Reviewer_eNzmOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the impact of fairness on multiobjective local search. The authors compare three local search methods with different levels of fairness and conduct experiments on multiobjective knapsack, travelling salesman, resource allocation, NK-landscape, and quadratic assignment problems.

Critical strengths
  • The research question is interesting and valuable. The authors explain the search behaviour of different local search methods from the perspective of fairness.
  • The experiments cover different types of multiobjective combinatorial optimization problems.
Critical weaknesses
  • The experiments mainly compare three Pareto-based local search methods, without evaluating whether the findings extend to other advanced multiobjective local search approaches.
  • Although the experiments cover five types of combinatorial optimization problems, they mainly focus on bi-objective problems with no more than 500 decision variables. Experiments on problems with more objectives and larger decision spaces are lacking.
Questions for authors
  • When the number of objectives increases beyond two, the number and distribution of non-dominated solutions and good neighbours in the archive may change. Do the main conclusions still hold in these cases?
  • As the archive size increases, does the additional computational overhead introduced by the fairness-based selection mechanism affect the actual runtime of the algorithm?
Reviewer_8tZJOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper compares systematic (s-PLS), random (r-PLS), and fair (f-PLS) multi-objective local search methods. It derives the waiting time for discovering the next non-dominated neighbor under a fixed archive and evaluates search performance on five classes of combinatorial optimization problems. Extending the analysis to arbitrary favorable-neighbor count distributions and identifying the conditions under which fairness yields advantages constitutes a valuable contribution. The experiments cover multiple problem scales and include paired statistical tests.

Critical strengths

The topic is suitable. The manuscript is well written.

Critical weaknesses
  1. The proofs for Proposition 2 and Appendix C.7 on random round-robin rely on balanced initial access counts. However, Algorithm A.3 retains the counts of old solutions while resetting the counts of newly added solutions to zero. For illustration, suppose the favorable-neighbor probabilities of two solutions are given; under a certain historical count state, f-PLS may first visit the solution with no favorable neighbors, leading to an expected waiting time of 4.5 iterations, whereas r-PLS requires only 4 iterations. Accordingly, these guarantees cannot be directly generalized to arbitrary historical states. The counting preconditions and their scope of applicability to the practical algorithm must be clarified.

  2. s-PLS uses sampling without replacement and maintains a set of unexplored solutions, while r-PLS and f-PLS adopt sampling with replacement. Moreover, f-PLS prioritizes new solutions by resetting their counters. Hence, the claim in Section 4 that the algorithms differ only in their degree of fairness is inadequate. Comparisons of selection rules should be conducted with the neighborhood sampling scheme fixed, and ablation studies on count retention, count resetting, and new-solution prioritization should be performed.

  3. The theoretical comparisons assume the same fixed archive, yet Figures 4 and B.1 present archives independently generated by each algorithm. Distribution discrepancies may themselves be outcomes of the search process. Although the paper acknowledges that local waiting time does not determine long-term hypervolume, the strategies should still be compared on identical archives extracted from real algorithm runs to validate waiting-time predictions and record the hypervolume gain of newly discovered neighbors.

  4. Appendix B samples at most 2,000 moves per solution, while the analysis depends on full and positive count distributions. A 500-variable QAP instance has 124,750 neighbors. If only one favorable neighbor exists, sampling 2,000 times without replacement still carries approximately a 98.4% probability of missing it. Zero successful samples cannot be equated to the absence of favorable neighbors. The estimation uncertainty and sampling sensitivity should be reported, and validation using small instances with exactly enumerable neighborhoods is required.

  5. All experiments adopt bi-objective random instances with fixed NK parameters, and the correlation between objectives is not systematically varied. The first-improvement variant narrows some performance gaps but is only tested on 100-variable instances. Each instance is run only once; the existing Wilcoxon tests with Holm correction cannot separate the effects of instance heterogeneity and algorithmic randomness. Additional validations are needed, including large-scale first-improvement baselines, repeated runs with multiple random seeds, and tests under varying objective correlations or numbers of objectives.

Questions for authors

N/A

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.