Block-Bench: A Framework for Controllable and Transparent Discrete Optimization Benchmarking

Furong Ye; Frank Neumann; Thomas Bäck; Niki van Stein

cs.NEApr 8, 2026

Block-Bench: A Framework for Controllable and Transparent Discrete Optimization Benchmarking

Authors: Furong Ye, Frank Neumann, Thomas Bäck, Niki van Stein

Organizations: LIACS, Leiden University, Leiden, the Netherlands · Optimisation and Logistics, School of Computer Science and Information Technology, Adelaide University, Adelaide, Australia

Abstract

We present a novel approach for constructing discrete optimization benchmarks that enables fine-grained control over problem properties, and such benchmarks can facilitate analyzing discrete algorithm behaviors. We build benchmark problems based on a set of block functions, where each block function maps a subset of variables to a real value. Problems are instantiated through a set of block functions, weight factors, and an adjacency graph representing the dependency among the block functions. Through analyzing intermediate block values, our framework allows to analyze algorithm behavior not only in the objective space but also at the level of variable representations in the obtained solutions. This capacity is particularly useful for analyzing discrete heuristics in large-scale multi-modal problems, thereby enhancing the practical relevance of benchmark studies. We demonstrate how the proposed approach can inspire the related work in self-adaptation and diversity control in evolutionary algorithms. Moreover, we explain that the proposed benchmark design enables explicit control over problem properties, supporting research in broader domains such as dynamic algorithm configuration and multi-objective optimization.

Figures & tables

	Type	Block functions	$A$	$W$	$E$	$B$
F1	DBP	OneMax	$\{0\}^{m}$	$\{1\}^{m}$	$\{0\}^{m\times m}$	-
F2	DBP	LeadingOnes	$\{0\}^{m}$	$\{1\}^{m}$	$\{0\}^{m\times m}$	-
F3	DBP	Jump k	$\{0\}^{m}$	$\{1\}^{m}$	$\{0\}^{m\times m}$	-
F4	DBP	Epistasis	$\{0\}^{m}$	$\{1\}^{m}$	$\{0\}^{m\times m}$	-
F5	DBP	OneMax , LeadingOnes , Jump 3 , Epistasis	$\{0\}^{m}$	$\{1\}^{m}$	$\{0\}^{m\times m}$	-
F6	DBP	OneMax , Jump 2 , Jump 3 , Epistasis	$\{0\}^{m}$	$\{1\}^{m}$	$\{0\}^{m\times m}$	-

Table 1. The instances of block-structure problems mentioned in this paper.

n

is the problem dimensionality,

m

is the number of blocks,

i,j\in[m]

. The functions listed in the “Blocks functions” column are sequentially added as

m

increases. “F*” are single-objective problems, and “BF*” are bi-objective problems formed by the corresponding two problem instances.

Panel of Figure 1 — Figure 1. Correlations between block function values (in axes) to the minimal ( Left ) and maximal ( Right ) attainable objective values (indicated by colors) for a DBP.

Panel of Figure 2 — Figure 2. Diverse landscapes constructed by block functions OneMax (Left, F1), Jump 2 (Mid, F3), or Epistasis (Right, F4).

Figure 3. A complex but designed landscape constructed by several distinct block functions.

Panel of Figure 4 — Figure 4. Correlations between block function values (in axes) to the minimal (Top) and maximal (Bottom) attainable objective values (indicated by colors) for a GCP. We present the pairs between $v4$ and the others.

Panel of Figure 5 — Figure 5. The minimal (Top) and maximal (Bottom) attainable objective values with respect to the corresponding Hamming distance of each block to its optimal solution, for the GCP F10 with the same objective space in Figure 4 .

Panel of Figure 6 — Figure 6. Convergence process of EAs for F5 over the FEs. Results are the average of 50 runs.

Panel of Figure 7 — Figure 7. Convergence process of EAs for F10 over the FEs. Results are the average of 50 runs.

	$(1+(\lambda,\lambda))$ GA	$(1+\lambda)$ EA	$(1+\lambda)~$ two-rate EA	$(1+\lambda)~$ var EA	fGA
OneMax	474 (4)	284 (2)	504 (5)	273 (1)	346 (3)
LeadingOnes	2 070 (5)	970 (2)	1542 (4)	903 (1)	1190 (3)
Jump	216 926 (5)	130 661 (4)	65 110 (1)	91 394 (2)	126 513 (3)
Epistasis	22 636 (5)	10 241 (2)	9 386 (1)	12 756 (3)	15 609 (4)
DBP (F5)	194 190 (5)	37 086 (2)	15 505 (1)	67 061 (4)	43 790 (3)
GCP (F16)	156 569 (4)	46 326 (2)	62 190 (3)	175 894 (5)	40 883 (1)

Table 2. FEs and ranks (in brackets) of the EAs to reach the optimum of

40

D problems. Results are the average of

50

runs.

Panel of Figure 8 — Figure 8. The attainable objective values of a $40$ D DBP (F3) and GCP (F7) with only Jump 3 block functions vs. the number of 1-bits in the solution. $m=1,2,4$ from left to right.

Panel of Figure 9 — Figure 9. The FEs of $(\mu+1)$ GAs to reach the optimum of $40$ D DBPs and GCPs with Jump 3 , Epistasis , and heterogeneous block functions.

Panel of Figure 10 — Figure 10. The bi-objective search space of GCPs with the weight vectors of the objectives are $\{1\}^{4}$ vs. $\{-1\}^{4}$ on the Left , and $\{1,-1,1,1\}$ vs. $\{-1,1,1,-1\}$ on the Right .

Panel of Figure 11 — Figure 11. The HV convergence on the bi-objective optimization problems with objective space in Figure 10 . The block functions are all OneMax in (a) and LeadingOnes in (b).

Benchmark Design

Benchmark design creates tasks, datasets, metrics, and protocols that make AI capabilities measurable and comparisons credible.

See all 394 papers

An Evolutionary Framework for Automatic Optimization Benchmark Generation via Large Language Models
Jan 19, 2026Yuhiro Ono, Tomohiro Harada, Yukiya MiuraEvolutionary Optimization Benchmark Design
Graduate School of Systems Design, Tokyo Metropolitan University, 6-6, Asahigaoka, Hino, 1910065, Tokyo, Japan. · Graduate School of Science and Engineering, Saitama University, 2552026 Shimo-okubo, Sakura-ku, Saitama, 3388570, Saitama, Japan.
GNBG-C: A Unified and Configurable Benchmark Generator for Constrained Continuous Optimization
Oct 27, 2026Ali Ghasemzadeh, Erfan Babakhani, Armin Khosravi +4Synthetic Benchmark Generation Constrained Optimization
Department of Data and Systems Engineering, the University of Hong Kong, Hong Kong SAR, China · Independent Researcher, Isfahan, Iran · Centre for Artificial Intelligence Research and Optimisation, Torrens University Australia, Brisbane, Australia +3
A Dynamic Decomposition Strategy for the MOEA/D With Proven Performance Guarantees
Oct 26, 2026Benjamin Doerr, Martin S. Krejca, Noé WeeksMulti-Objective Evolutionary Optimization Multi-Objective Optimization
Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, Institut Polytechnique de Paris, Palaiseau, France · École Normale Supérieure, Paris, France

Jan 19, 2026J/K move · Enter open · S save

An Evolutionary Framework for Automatic Optimization Benchmark Generation via Large Language Models

Yuhiro Ono, Tomohiro Harada, Yukiya Miura

Graduate School of Systems Design, Tokyo Metropolitan University, 6-6, Asahigaoka, Hino, 1910065, Tokyo, Japan. · Graduate School of Science and Engineering, Saitama University, 2552026 Shimo-okubo, Sakura-ku, Saitama, 3388570, Saitama, Japan.

Evolutionary Optimization Benchmark Design Synthetic Benchmark Generation

Open paper AskPDF arXiv

Optimization benchmarks play a fundamental role in assessing algorithm performance; however, existing artificial benchmarks often fail to capture the diversity and irregularity of real-world problem structures, while benchmarks derived from real-world problems are costly and difficult to construct. To address these challenges, we propose an evolutionary automatic benchmark generation framework that leverages a large language model (LLM) as a generative operator, termed the LLM-driven evolutionary benchmark generator (LLM-EBG). In this framework, the LLM serves as an evolutionary operator that generates and evolves benchmark problems within a flexible, expressive representation space. As a case study, we generate unconstrained single-objective continuous minimization problems represented as mathematical expressions designed to induce significant performance differences between a genetic algorithm (GA) and differential evolution (DE). Experimental results show that LLM-EBG successfully produces benchmark problems in which the designated target algorithm consistently outperforms the comparative algorithm in more than 80% of trials. Furthermore, exploratory landscape analysis reveals that benchmarks favoring GA are highly sensitive to variable scaling, demonstrating that the proposed framework can generate problems with distinct geometric characteristics that reflect the intrinsic search behaviors of different optimization algorithms.

Abstract

Benchmark Design

Explore similar work

An Evolutionary Framework for Automatic Optimization Benchmark Generation via Large Language Models

GNBG-C: A Unified and Configurable Benchmark Generator for Constrained Continuous Optimization

A Dynamic Decomposition Strategy for the MOEA/D With Proven Performance Guarantees