Jul 2026· GECCO Companion· pp. 35-36· 0 citations· 15 references
Computer Science
TL;DR
This paper provides the first proof that the more complex σ-distance mechanism of the SPEA2 yields a provably superior approximation ability, and shows the first result showing a provable qualitative gap between the approximation abilities of these two algorithms.
Abstract
The SPEA2 and the NSGA-II are two of the most widely used dominance-based multi-objective evolutionary algorithms (MOEAs). While prior theoretical work established similar runtime guarantees for both, the differences in their selection mechanisms were not well understood from an approximation perspective. We provide the first proof that the more complex σ-distance mechanism of the SPEA2 yields a provably superior approximation ability. Specifically, the steady-state SPEA2 computes an optimal spread of the OneMinMax Pareto front in O(μ2n log(μ;) log(n)) expected function evaluations. In contrast, the steady-state NSGA-II, when started near an optimal spread with just two sub-optimal gaps, fails to achieve optimality within polynomial time with overwhelming probability. This is the first result showing a provable qualitative gap between the approximation abilities of these two algorithms. This paper summarizes the work Yasser Alghouass, Benjamin Doerr, Martin S. Krejca, and Mohammed Lagmah: Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II. International Joint Conference on Artificial Intelligence, IJCAI 2025. [1].
This paper introduces the bi-objective problem class CLIMB and analyzes the runtime of GSEMO and the widely used NSGA-II on this problem, and proves that GSEMO and NSGA-II-DYN, a version of NSGA-II with dynamic population sizes, can find the Pareto front of CLIMB in expected fitness evaluations.
Mixed-integer programming (MIP) models are highly successful in both academic and industrial settings, but they often suffer from scalability issues and weak relaxations. These issues have been effectively addressed by Dantzig-Wolfe decomposition and branch-cut-and-price (BCP) approaches in many different applications. Such approaches are among the most successful for solving large-scale MIP models; however, their complex and sophisticated implementations might not be practical for nonspecialists. This has prompted the development of generic BCP frameworks, which aim to simplify the implementation process while maintaining a high level of efficiency and flexibility. The present paper introduces Coluna.jl, an innovative BCP framework developed in Julia, a language known for its high computational performance and ease of use. Coluna.jl is an open-source package that enhances user experience by enabling more accessible coding and rapid prototyping without compromising computational efficiency. Among its key advantages, Coluna.jl provides a framework for advanced features like state-of-the-art column generation with dual stabilization, strong branching, and a comprehensive presolve routine. This combination of enabling advanced features and user-friendly implementation establishes Coluna.jl as a significant contribution to the field of optimization software.
History: Accepted by Ted Ralphs, Area Editor for Software Tools.
Funding: This work was supported by Fundação de Apoio à Pesquisa do Estado da Paraíba [Grants 041/2023, 2021/3182, and 261/2020], Universidade Federal da Paraíba [Grants PVL13395-2020 and PVL13400-2020], and Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 309580/2021-8, 314088/2021-0, 311654/2023-1, and 406245/2021-5].
Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1130 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1130 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
F. Vanderbeck, Guillaume Marquès, R. Sadykov et al.· INFORMS journal on computing· 1 citation
We ask whether large language models (LLMs) can design effective algorithms for well-specified operations research (OR) problems. We study inventory control, queueing network control, and assortment optimization. We evaluate two levels of LLM use: at level 1, the model receives one problem instance and returns a solution for that instance; at level 2, it receives only the problem class description and broad parameter ranges, and returns an algorithm that maps instance parameters to solutions. Human input is minimal: we give one untuned prompt that describes the problem, and the model has access to a Python sandbox tool with a fixed compute budget. The strongest model we test, gpt-5.6-sol, matches or outperforms the best existing method on almost all evaluated instances. This holds even at level 2, where the returned algorithm is fixed before seeing the evaluation instances. Performance also improves sharply across models released less than eight months apart, suggesting that this capability is moving quickly. Thus, for the well-specified operations problems we study, a single untuned LLM query can already produce algorithms competitive with specialized methods. These results suggest that frontier LLMs can be a serious empirical baseline for algorithm design in well-specified OR problems.
This study investigates the efficiency of five metaheuristic algorithms, namely Differential Evolution (DE), Genetic Algorithm (GA), Grey Wolf Optimizer (GWO), Harmony Search (HS), and Particle Swarm Optimization (PSO), when deployed on a Raspberry Pi 5 edge device. The evaluation focuses on both optimization quality and computational cost, using four standard benchmark functions that represent a range of landscape characteristics: Sphere, Rosenbrock, Rastrigin, and Ackley. Each function is tested at dimensions 10, 30, and 50 to probe scalability. In addition to objective values, the experiments collect per-iteration processor usage and memory (RAM) to provide a practical view of runtime overhead under constrained resources. Among the five candidates, GWO consistently delivers the fastest or near-fastest convergence while keeping variability tight. Its trajectories show smooth descent across functions and dimensions, paired with comparatively modest CPU and RAM footprints. PSO typically ranks second in speed with stable dynamics, though brief CPU spikes often appear at early iterations as swarms synchronize. DE demonstrates resilience on rugged functions but generally requires more iterations to close the final gap. GA and HS can reach competitive objective values on some settings, yet they display wider dispersion and higher overhead at larger dimensions, which reduces their suitability for small devices. Overall, the evidence indicates that GWO is the most efficient choice for edge deployment on Raspberry Pi 5, striking a favorable balance between convergence speed, stability, and resource usage. PSO is a strong alternative when slightly higher processor activity is acceptable. These findings support the adoption of lightweight, variance-stable metaheuristics for edge optimization workloads where CPU and memory budgets are tight.
Ziadan Qowi, Akhdan Musyaffa Firdaus, Hari Purnama· The eurasia proceedings of s...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
