1 Introduction↩︎

Combinatorial and optimization problems are central to many industrial AI applications, including the automated engineering of technical systems (e.g., configuring and planning the composition of large electronic systems) [1] and the automation of process planning and scheduling [2]. A long-standing vision in AI is that domain experts should specify what constitutes a correct solution, while the computer should determine how to obtain it efficiently [3].

In practice, however, applying state-of-the-art solvers from constraint [4], logic [5], or mathematical programming [6] to large real-world problem instances still demands substantial expert intervention beyond the what. Effective deployment often requires redesigning problem specifications [7], crafting problem-specific heuristics [8], decomposing the problem into manageable subproblems [9], or implementing tailored local-search procedures [10].

To address these challenges, we build on recent advances in program generation via code evolution [11]. Our approach integrates a new CheckMate component into the OpenEvolve [12] controller loop. Given a natural-language description and a formal specification of what solutions are, along with a training set of representative instances, OpenEvolve+CheckMate automatically synthesizes a problem-specific solver—implemented as a Python program—without requiring any formulation of how to solve the problem.

We investigate the following research questions:

1. Can OpenEvolve+CheckMate solve hard real-world (a) combinatorial and (b) optimization problems, such as configuration and scheduling?

2. How does the performance of the generated programs compare to state-of-the-art solvers?

3. How well do these evolved programs scale?

Our evaluation targets configuration problems from automated engineering and an industrial scheduling problem. We analyze two configuration tasks from Siemens that capture pivotal real-world challenges: one stresses solver scalability with respect to solution size [13], and the other examines solver behavior when several difficult problems are combined [14]. In addition, we evaluate a real-world scheduling problem from metalworking at voestalpine [15].

Across all tasks, OpenEvolve+CheckMate generated problem-specific code that outperformed the respective state-of-the-art solvers by orders of magnitude on large or hard instances. Thus, our approach extends to solving problems where leading solvers cannot deliver solutions.

2 Preliminaries↩︎

Since our contribution integrates with OpenEvolve [12], an open-source implementation of AlphaEvolve [11], we provide a brief overview of this framework. OpenEvolve is a code optimization framework that automatically generates programs capable of solving specified problems by leveraging evolutionary computation and the capabilities of Large Language Models (LLMs) in program synthesis. This framework operates through an asynchronous pipeline consisting of four core modules: (i) a prompt sampler that generates prompts using previously evolved programs and their evaluation scores, (ii) an LLM ensemble, i.e., a set of LLMs that process prompts and produce full code rewrites or targeted edits, (iii) an evaluator pool that scores and ranks generated programs, and (iv) a program database that stores these programs and their scores in a structured grid [16], organizing them according to diverse user-defined criteria, such as code complexity and correctness. Note that the evaluator pool, at its core, is an evaluation function that the user must implement. An island-based genetic algorithm [17] manages selection, migration, and evolution across iterations.

Adopting OpenEvolve’s terminology, we denote an artifact as a textual error-feedback provided to the LLM, and the combined score \(z_j\in[0,1]\) as a numerical score assigned to program \(p_j\). Intuitively, the higher the combined score, the higher the likelihood for the program to be selected by the prompt sampler and to guide further evolution.

3 Approach↩︎

Extending OpenEvolve’s pipeline (Sec. 2), our approach CheckMate provides a general, problem-independent implementation of the evaluator pool that employs state-of-the-art solvers as verifiers to check the correctness of programs’ produced problem solutions. Fig. 1 illustrates the integrated framework, with our contributions highlighted in the dashed blue box. OpenEvolve+CheckMate expects the following inputs: (i) a natural language description \(D\) of the problem (prompt), (ii) a formal specification \(\mathit{F}\) defining valid problem solutions, (iii) a solution verifier \(V\), (iv) a set of training problem instances \(I\) (for which valid problem solutions are assumed to exist), (v) a set \(S\) of scoring functions for program evaluation, (vi) a (possibly empty) initial program \(p_0\), and (vii) a set of evolution and LLM hyperparameters \(\Lambda\).

Given the inputs, OpenEvolve+CheckMate, denoted as the function generator \(g\), produces a program \(p^*\). Formally: \[g : (\mathit{D},\mathit{F},\mathit{V},\mathit{I},\mathit{S},\mathit{p_0},\Lambda) \mapsto p^*\] The generation of \(p^*\) involves \(N\) training iterations, with \(N\) defined in \(\Lambda\). At each iteration \(1 \le j \le N\), the LLM ensemble non-deterministically generates an intermediate program \(p_j\), aiming to improve the programs \(p_0, \ldots, p_{j-1}\). CheckMate evaluates \(p_j\) by producing the combined score \(z_j\). After \(N\) iterations, the \(p_j\) achieving the highest \(z_j\) will then correspond to the final best program \(p^*\).

At the core of CheckMate, the solution verifier \(V\) is used to check the correctness of program outputs. Specifically, given a program \(p_j\), which (possibly) generates a candidate solution \(c_{ji}\) for a problem instance \(i\), \(V\) outputs (i) a \(\mathit{verdict}\in\{ \mathit{correct}, \mathit{incorrect} \}\) indicating whether \(c_{ji}\) is an (in)correct solution for \(\mathit{i}\), and, (b) in case of \(\mathit{incorrect}\), some \(\mathit{feedback}\) detailing which parts of the formal specification \(F\) are violated by \(c_{ji}\). Formally: \[p_j : \mathit{i} \mapsto \mathit{c_{ji}} \qquad V : (F, i, c_{ji}) \mapsto \langle \mathit{verdict}, \mathit{feedback} \rangle\] CheckMate’s overall program evaluation process, employing \(V\), is detailed next.

3.1 Program Execution and Evaluation↩︎

In each training iteration \(j \le N\), in order to evaluate the generated program \(p_j\), \(\mathrm{\small CheckMate}\):

1. Executes \(p_j\) on a training instance \(i \in I\): if \(p_j\) fails, go to [enum:checking:eval] and forward \(\langle \mathit{incorrect}, \mathit{feedback} \rangle\), where the feedback details the failure reason, e.g., an error stack trace; otherwise, go to [enum:checking:synt] and forward candidate solution \(c_{ji}\);

2. Syntactically checks \(c_{ji}\): if the check fails, go to [enum:checking:eval] and forward \(\langle \mathit{incorrect}, \mathit{feedback} \rangle\), where the feedback includes, e.g., syntactic errors in \(c_{ji}\); else, go to [enum:checking:sem] and forward \(c_{ji}\) parsed into the verifier-specific format;

3. Checks the correctness of \(c_{ji}\) using the verifier \(V\): if the check returns positively, go to [enum:checking:eval] and forward \(\langle \mathit{correct}, \emptyset \rangle\); else, go to [enum:checking:eval] and forward \(\langle \mathit{incorrect}, \mathit{feedback} \rangle\), where feedback includes, e.g., violated constraints in \(F\);

4. Stores \(\mathit{feedback}\) and evaluates \(p_j\)’s performance on instance \(i\) using the scoring functions \(S\), based on the verdict (\(\mathit{correct}\)/\(\mathit{incorrect}\)) as well as statistics such as runtime, consumed memory, and resulting objective values.

This process is repeated for all training instances \(i \in I\), or until the early stopping is triggered due to \(k\) consecutive \(\mathit{incorrect}\) verdicts.²

Finally, CheckMate (i) aggregates the instance-level scores from Step (4) to determine \(z_j\), the combined score of \(p_j\), and (ii) returns \(z_j\) with the stored feedback for all instances (i.e., artifacts) to OpenEvolve’s main controller loop.

3.2 Textual Feedback↩︎

The artifacts (cf.Sec. 2) are used to provide textual feedback directly to the LLM. They depend on the underlying failure type, of which we distinguish five kinds: (i) execution exceptions, such as compilation or runtime errors, (ii) intentional exceptions, raised by the evolved program itself due to a precondition or invariant violation, (iii) exceeded resource errors, whenever (user-defined) time or memory limits are reached, (iv) syntactic errors, e.g., an incomplete candidate solution, and (v) semantic errors, if the verdict of \(V\) for \(c_{ji}\) equals \(\mathit{incorrect}\).

Each artifact comprises the failed instance, the failure type, and a suggestion for repairing the failure. The suggestion proposes an improvement to the program in natural language, depending on the failure type. It can include the stack trace, the error message, the position of syntactic errors, or the set of violated constraints or logical sentences. The artifact is stored alongside program \(p_j\) and is injected into the prompt whenever \(p_j\) is selected in subsequent iterations.

3.2.0.1 Failure Protocol: Self-refined feedback on program-level.

To support the evolution process when programs do not produce candidate solutions, we introduce the Failure Protocol as part of the textual feedback mechanism. By instructing the LLM via the prompt to implement this protocol, we enable a program-level self-refinement loop. Whenever the program expects that the ongoing candidate solution generation will fail, it should raise one of the following exceptions, indicating that it believes (i) the instance has no correct solution, (ii) the instance has a correct solution but the implemented search strategy will not find it, or (iii) it cannot recover from wrong decisions.

Exceptions raised in accordance with the Failure Protocol are referred to as intentional exceptions. They include additional information that the program considers useful feedback for evolution. During execution, CheckMate intercepts intentional exceptions and parses them into artifacts, including the suggestion that the error indeed lies within the program, because all instances are assumed to be satisfiable.

3.3 Inputs↩︎

In this section, we present the inputs to the code evolution framework that are either novel or central to our approach.

3.3.0.1 Formal specification and solution verifier.

The formal specification \(F\) is used by the verifier \(V\) to check if a candidate solution \(c_{ij}\) yielded by the program \(p_j\) is correct for the problem instance \(i\). It can be provided, e.g., in the form of constraints or logical sentences depending on the selected \(V\), such as clingo [18], or CP Optimizer [4]. Since \(F\) is used solely to check, there is no need to tune it for solving, e.g., by employing guessing or symmetry-breaking techniques.

3.3.0.2 Prompt.

The natural language description \(D\) is a solver-agnostic specification designed to be independent from the format of the solution verifier. It is structured as a domain-specific prompt which contains: (i) the LLM identity, (ii) the task to be performed, (iii) the problem description including context, core entities, and constraints that must be satisfied, and (iv) instructions on expected input/output formats and algorithm requirements. This structured approach provides the LLM with the necessary context for generating programs.

3.3.0.3 Scoring functions.

The scoring functions constitute one of the most fundamental components of the learning process, as they affect how programs are ranked, selected, and evolved across iterations. As introduced in Sec. 3.1, they are employed to derive \(z_j\), the combined score of each program \(p_j\). Specifically, \(z_j\) is built upon the correctness \(z_{j}^{\mathit{c}}\) and the quality-efficiency \(z_{j}^{\mathit{qe}}\) trade-off scores. The correctness score builds upon the number of training instances \(i \in I\) solved, while the quality-efficiency score combines the quality score \(z_{j}^{q}\) and the efficiency score \(z_{j}^{e}\). The quality score reflects the optimization of the objective values, whereas the efficiency score combines the runtime and memory consumption.

In particular, CheckMate (i) normalizes the raw statistics into scores in \([0,1]\);³ (ii) aggregates the instance-level scores into the overall correctness \(z_{j}^{c}\), quality \(z_{j}^{q}\), and efficiency \(z_{j}^{e}\) scores; (iii) combines the quality and efficiency scores into the composite quality-efficiency tradeoff score \(z_{j}^{\mathit{qe}}\); and (iv) combines \(z_{j}^{c}\), \(z_{j}^{\mathit{qe}}\) into the combined score \(z_{j}\). To address these tasks, we employed an exponential decay function for Step (i), the arithmetic mean for (ii), and combinations of harmonic mean, product, and Prioritized Ordered Weighted Average (\(\mathit{POWA}\)) [19] for (iii) and (iv).

3.3.0.4 Training set.

The training set should include representative instances of various difficulty levels. Since the initial program \(p_0\) is empty, including sufficiently easy instances is highly recommended to enable the evolutionary process to get started. In early iterations, the main challenge is to solve at least some instances. Once this occurs, the scoring function becomes informative, yielding non-zero correctness values and therefore a useful combined score, enabling the program to evolve effectively. As training progresses, it appears that instances of moderate difficulty promote generalization, while hard ones support scaling and efficiency improvements.

4 Case Studies↩︎

In this work, we demonstrate the effectiveness of our approach on the three case studies motivated in Sec. 1. This section provides a high-level overview of these case studies.

4.1 House Configuration Problem↩︎

The technology-independent House Configuration Problem (HCP) [20], [21] was introduced by Siemens and abstracts electronic modules, frames, and racks into things, cabinets, and rooms. Specifically, persons own multiple things, whereas each thing belongs to exactly one person. The task is to assign things to cabinets and cabinets to rooms while satisfying capacity, ownership, and ordering constraints (the latter introduced in [13]).

4.2 Combined Configuration Problem↩︎

The Combined Configuration Problem (CCP) [14] is a combinatorial benchmark motivated by industrial product configuration tasks at Siemens, such as the configuration of railway control and safety systems [1]. The problem is defined via a directed acyclic graph with vertices, paths, bins, colors, areas, and border elements. The CCP integrates multiple interacting subproblems that must be solved simultaneously: (P1) vertex coloring, (P2) bin packing, (P3) partitioning into disjoint paths, (P4) matching border elements to areas, and (P5) ensuring the connectedness of color-induced subgraphs. The combination of these subproblems makes the CCP very challenging for solvers.

4.3 Energy-Aware Double-Flexible Job-Shop↩︎

The Energy-Aware Double-Flexible Job Shop Problem (E-DFJSP) scheduling problem [22] exemplifies a real-world production process at voestalpine⁴, where jobs consist of multiple metal-cutting operations. Each cut operation requires selecting an eligible machine and its corresponding parameters, from a \(k \times k\) grid. Between cuts, workers perform setup and transport operations on the machines. A correct schedule assigns the operations to the corresponding machines and workers while satisfying all constraints, such as preventing resource overlaps. Schedules are evaluated according to lexicographically prioritized objectives to be minimized: (1) job tardiness \(\mathit{Tard}\), (2) total energy consumption \(\mathit{TEC}\)—including auxiliary, idle, and processing energy—, and (3) makespan \(C_\mathit{max}\). Note that, as the machine parameters influence both processing time and energy consumption, optimizing such a problem is a highly complex task.

We map the objective values to the quality score \(z_j^q\) as follows. First, \(\mathit{Tard}\), \(\mathit{TEC}\), and \(C_\mathit{max}\) are normalized into \([0,1]\) using the corresponding theoretical lower and upper bounds. Next, an exponential decay function is applied to compute the scores \(z_j^{\mathit{Tard}}\), \(z_j^{\mathit{TEC}}\), and \(z_j^{C_\mathit{max}}\), which are subsequently combined into \(z_j^q = \mathit{POWA}(z_j^{\mathit{Tard}},\) \(z_j^{\mathit{TEC}}, z_j^{C_\mathit{max}})\).

5 Evaluation↩︎

In this section, we evaluate the proposed approach experimentally. [23] provides datasets, evolved programs, and results.

5.1 Datasets↩︎

For each case study, we use separate training and test sets, all comprising easy, moderate, and hard instances.

For the CCP, we reuse the dataset of [14] ([14]), which comprises \(99\) instances: \(30\) easy, \(33\) moderate, and \(36\) hard, which, for brevity, we will denote by \(30/33/36\). For the training set, we select \(20\) instances, split as \(3/7/10\), as such a split was employed to define the CCP’s competition instances for the 6th ASP Competition [24]. Moreover, we generate and include \(5\) more very easy instances (cf.Sec. 3.3.0.4) by reducing the number of components in the easy ones. Hence, the CCP’s training set includes \(25\) instances (\(8/7/10\)), while the test set comprises the \(79\) remaining ASP competition instances (\(27/26/26\)). For the HCP and the E-DFJSP, we generate both training and test sets, ensuring that all instances are satisfiable by design. The training sets are composed of \(15\) instances, split as \(5/5/5\). For the HCP, the easy instances consist of up to \(5\) persons (\(\mathord{\sim} 50\) things), the moderate instances of up to \(50\) persons (\(\mathord{\sim} 500\) things), and the hard instances of up to \(500\) persons (\(\mathord{\sim} 5\,000\) things). The hardness assessments reflect the results of [13] on clingo’s performance. Likewise, for the E-DFJSP, the easy instances involve up to \(10\) jobs (\(\mathord{\sim} 60\) operations), the moderate up to \(50\) jobs (\(\mathord{\sim} 300\) operations), and the hard up to \(500\) jobs (\(\mathord{\sim}3\,000\) operations). This is in accordance with [25] where scheduling problems were classified as large-scale if they comprise at least \(1\,000\) operations.

We designed the test sets to contain an overproportional number of hard instances ranging from large to very large size, in accordance with research question [rq3:scalability], i.e., investigating the scalability of the evolved code. Specifically, we used a split of \(6/6/24\), where the \(24\) hard cases comprise up to \(3\,000\) persons (\(\mathord{\sim} {30\,000}\) things) for the HCP and up to \(1\,000\) jobs (\(\mathord{\sim} 6\,000\) operations) for the E-DFJSP, thus going significantly beyond what is commonly already considered hard.

5.2 Experiments↩︎

Each experiment was conducted on a machine equipped with an AMD EPYC 7H12 64-core Processor, with RAM usage restricted to 32 GB. Timeouts for evolved programs and solvers to find a solution for any problem were set to 600 s.

5.2.0.1 Training.

Since OpenEvolve+CheckMate is inherently non-deterministic, each evolutionary training run can produce a different best program \(p^*\). To account for this variability, we performed four independent training runs for each case study (Sec. 4), yielding four corresponding best programs \(p^*\).

Each problem has a specific prompt \(D\) and formal specification \(F\). Exclusively for CCP, due to its hardness, (i) \(D\) includes the Failure Protocol (Sec. 3.2.0.1), and (ii) \(F\) is exploited to pinpoint violated constraints returned by the verifier whenever its verdict for a candidate solution equals incorrect.

While most parameters were kept at OpenEvolve’s default values, the following problem-specific settings were used: (i) the number of evolutionary iterations (\(50\) for HCP, \(75\) for CCP, \(100\) for E-DFJSP, or, for brevity \(50/75/100\)), (ii) the number of islands (\(3/5/5\)), and (iii) the migration interval (\(10/10/15\)) to promote greater diversity between evolved programs. CheckMate’s early stopping parameter \(k\) (Sec. 3.1) was set to \(3\). For all case studies, program evaluation criteria include built-in measures of code complexity and diversity, quantifying program length and (textual) differences. In addition, HCP’s and CCP’s criteria set contains the correctness, runtime, and memory usage scores. In contrast, E-DFJSP contains the quality and tardiness scores to guide the evolution more prominently towards programs that yield high-quality solutions. To balance performance, efficiency, and cost  [11], we used as LLMs GPT-5 for 60% of queries and GPT-5-mini for the remaining 40%.

5.2.0.2 Testing.

Each training run outputs a best program \(p^*\), which was evaluated using CheckMate (standalone; without OpenEvolve) on the described test set (Sec. 5.1). To illustrate the performance variability across the four training runs, we focus on \(p^*_L\) and \(p^*_H\). Here, \(p^*_L\)(\(p^*_H\)) denotes the evolved program that attains the lowest (highest) combined score on the test set, largely driven by the overall solving percentage.

5.2.0.3 Comparison with the baseline solvers and verifiers.

To compare our evolved programs against state-of-the-art approaches, we executed top-performing solvers as standalone solving engines for each problem. For HCP and CCP, we employed clingo with the original formal specifications (HCP [13]; CCP [24]), as it demonstrated strong solving performance in tests compared to a leading CP solver OR-Tools [6]. For E-DFJSP, we used CP-Optimizer, following the results reported in [2], together with a formal specification extending that of [15] ([15]) in terms of a more general energy consumption formulation.

5.3 Synopsis of the Best Evolved Programs↩︎

The synopses of the best evolved programs were produced through a manual analysis conducted by the authors.

5.3.0.1 HCP.

HCP’s \(p^*_H\) begins by verifying available capacities by computing the minimum number of cabinets and rooms required under the ownership and capacity constraints and checks whether they exist. It proceeds greedily and deterministically, sorting things, cabinets and rooms and grouping them by owner, which enforces the ordering constraint. The program produces a correct configuration whenever sufficient resources exist, without exploring alternative assignments.

5.3.0.2 CCP.

CCP’s \(p^*_H\) combines heuristic-guided search with constraint-aware pruning and bounded backtracking to construct correct configurations over a state space of partial color, bin, and area assignments. Instead of exhaustively enumerating possibilities, the program incrementally builds a complete assignment while discarding infeasible branches early based on capacity, path, and area constraints, and applying deterministic ordering for repeatability. The procedure is not purely greedy—rejected assignments may be revisited through limited backtracking—yet it avoids full search by steering decisions via deterministic heuristics.

5.3.0.3 E-DFJSP.

E-DFJSP’s \(p^*_H\) consists of a greedy scheduler that first determines the set of eligible workers for each machine and, for every cut-machine pair, selects the best machine parameters by choosing the one with minimum processing time and, in case of ties, lower energy consumption. Jobs are ordered using the Earliest Due Date (EDD) heuristic to reduce total tardiness, and operations are scheduled respecting precedence constraints. Per task, all feasible machine-worker-mode combinations are evaluated to minimize total completion time, processing energy, and resulting machine makespan. The program maintains sorted calendars for machines, considering the interval from load start to unload completion, and for workers, who are required only during setup operations. Finally, it outputs a correct schedule together with the corresponding objective values.

5.4 Results and Discussion↩︎

Tab. 1 summarizes the overall and difficulty-wise solving percentage for \(p^*_L\), \(p^*_H\), and the corresponding state-of-the-art solver (\(\mathit{SOL}\)) across the three selected case studies. For HCP and E-DFJSP, both \(p^*_L\) and \(p^*_H\) solve all instances, whereas for CCP they solve \(82\%\) and \(89\%\), respectively. In contrast, \(\mathit{SOL}\)s perform well on easy instances but degrade substantially on the moderate and hard ones, achieving \(28\%\), \(65\%\), and \(61\%\) overall on HCP, CCP, and E-DFJSP, respectively. This indicates that both \(p^*_L\) and \(p^*_H\) are competitive and consistently outperform traditional solvers on harder instances, underscoring the scalability of our approach.

The cactus plots depicted in Figs. 2, 3, and 4 compare correctness, memory usage (top panel), and runtime (bottom panel) between \(p^*_H\) and \(\mathit{SOL}\) for each problem. Instances are ordered by increasing memory usage of \(\mathit{SOL}\).

5.4.0.1 HCP.

Fig. 2 shows a clear performance gap on HCP. While both approaches handle the easy instances, clingo’s memory usage increases sharply at instance 11 and remains near saturation, leading to repeated timeouts (13 times), out-of-memory events (8 times), and internal errors (5 times) on all harder instances. In contrast, \(p^*_H\) maintains negligible memory (average: 281 MB) and runtime (average: 0.08 s) throughout and produces no incorrect solutions. Overall, \(p^*_H\) solves all instances with orders-of-magnitude lower resource usage, indicating superior scalability.

5.4.0.2 CCP.

As can be seen from Fig. 3, \(p^*_H\) manifests consistently negligible runtimes while clingo exhibits three different runtime behaviors. More specifically, clingo solves 28 instances within 10 s and 23 instances between 10 s and the 10 min time limit, while 28 instances remain unsolved. In contrast, \(p^*_H\) solves 89% of the instances with consistently low memory and runtime, 546 MB and 0.12 s on average. Given this high performance, which applies to all four best programs, even a parallel portfolio solver combining all of them is practical and achieves a 100% solving rate across all training and test instances. This yields two key findings: (i) the best program \(p^*_H\) solves more instances and exhibits a much lower resource usage than the state-of-the-art solver, and (ii) a portfolio of all four evolved programs can, to the best of our knowledge, for the first time, successfully solve all CCP instances from [14].

5.4.0.3 E-DFJSP.

Fig. 4 compares \(p^*_H\) against CP Optimizer (CPO) for E-DFJSP. With regard to the solving rate, \(p^*_H\) is successful 100 % of the time on the test instances, whereas CPO fails to produce any solution on 14 of the 18 hardest ones due to 6 timeouts and 8 memory exhaustions. Regarding memory consumption, the two approaches exhibit comparable behavior on the easy and moderate instances; for the hard ones, however, CPO’s space requirements escalate. In terms of runtime, \(p^*_H\) requires an average of 1.26 s across all instances to find a solution, whereas CPO either fails to produce any solution or achieves, if at all, only marginally better quality scores despite using the entire time budget. In fact, CPO finds the optimum only for the easiest instance (10 jobs, 1 machine). Notably, for all instances with \(200\) jobs or more, \(p^*_H\) outperforms CPO on tardiness—the objective of highest priority—by 49% on average. Furthermore, the state-of-the-art solver cannot solve most instances with at least 500 jobs within 10 min, while \(p^*_H\) always succeeds in less than 4 s.

5.4.1 Training and Checking Costs↩︎

The cost in API fees was at most € 20 per training run and below € 200 overall. Times per training run ranged from 1 to 16 hours, depending on the number of iterations and the efficiency of the generated programs. CheckMate’s average and, respectively, worst-case costs for checking the correctness of outputs of best evolved programs \(p^*_H\) amounted to 3.01 s / 0.11 s / 1.93 s and 18.28 s / 0.32 s / 5.13 s per test instance for HCP / CCP / E-DFJSP.

6 Related Work↩︎

6.0.0.1 Combinatorial and optimization problems.

Modern symbolic AI methods utilize declarative formalisms, such as Answer Set Programming [26], Constraint Programming [27], or Mixed Integer Programming [28], to address complex combinatorial and optimization problems. These approaches decouple problem specification from search algorithms, enabling domain-independent solvers to find optimal or near-optimal solutions using advanced techniques like conflict-driven clause learning and constraint propagation. However, large industrial problem instances significantly reduce solver performance in practice [25], [29]. To improve performance, research has focused on three directions [30]: (i) developing domain-specific heuristics, (ii) improving problem encodings, and (iii) configuring existing or learning new problem-specific algorithms. While designing any of these approaches requires significant domain expertise and manual effort, it has been observed that machine learning (ML) methods can simplify this challenge in many industrial cases where problem instances share similar patterns.

For the first direction, various ML techniques have been proposed to learn effective heuristics from, e.g., problem instances or solving traces, using supervised or reinforcement learning methods [31], [32]. Injected into a solver, learned heuristics can significantly enhance its performance in the target domain. In the second direction, ML has been used to generate or optimize problem encodings, e.g., by adding symmetry-breaking or implied constraints [33], [34], or finding problem decompositions [35]. In the third direction, ML approaches were first used to develop portfolio solvers capable of automatically configuring existing solvers for specific problem instances [36]. More recently, deep learning methods have been proposed to solve combinatorial problems in an end-to-end fashion [30], learning to predict (approximate) solutions directly without invoking solvers at inference time.

Our approach can roughly be classified in the third direction, as we aim to automatically generate problem-specific solving algorithms. Unlike prior work that relies on deep learning models, we employ evolutionary computation combined with LLMs to synthesize code. This enables us to generate interpretable and verifiable algorithms, rendering our approach more flexible without compromising performance across different combinatorial and optimization problems.

6.0.0.2 Code generation for combinatorial optimization.

Code evolution with LLMs has recently emerged as a particularly relevant research topic in combinatorial optimization. Early frameworks, such as FunSearch [37], focused on evolving heuristics for Cap Set and Bin Packing problems. Subsequent works, such as Evolution of Heuristics [38], expanded the scope to a wider range of problems, such as online bin-packing, traveling salesman, and flow shop scheduling. Furthermore, AlphaEvolve [11] and its open-source implementations, such as OpenEvolve [12], ShinkaEvolve [39], DeepEvolve [40], and CodeEvolve [41], have applied code evolution to a variety of domains, focusing on the previously mentioned problems, as well as matrix multiplication, the minimum overlap problem, and kissing numbers in 11 dimensions. The aforementioned approaches neither explicitly mention formal verification nor utilize software testing, but rely on handcrafted solution checkers. More recently, the authors of [42] applied AlphaEvolve to 67 mathematical problems, and, in a few cases, verified the program-generated solutions using AlphaProof [43] and Lean [44]. Notably, SATLUTION [45] evolves entire code repositories to produce variants of SAT solvers, which operate at the propositional level. Differently, CheckMate employs first-order specifications to verify the correctness of candidate solutions for the given problem instances. Therefore, CheckMate addresses an open point in prior work by providing an automated declarative verification approach that guarantees the correctness of returned solutions.

7 Conclusions↩︎

The OpenEvolve+CheckMate framework showed the great potential to automatically synthesize problem-solving algorithms implemented in Python. The system needs no information on how to construct solutions. It relies only on what defines a correct (optimal) solution and a set of representative instances. The obtained programs can efficiently tackle large and challenging instances from the practical use cases of Siemens and voestalpine that are currently out of reach for state-of-the-art solvers. Our analysis demonstrates that the generated algorithms can successfully solve difficult real-world (a) combinatorial and (b) optimization problems such as configuration and scheduling, thereby addressing [rq1:solving]. The evolved programs significantly outperform state-of-the-art solvers on hard instances, addressing [rq2:vs-sota]. Finally, the results highlight strong scalability: both in terms of increasing problem size, as tested on the HCP and E-DFJSP, and in terms of increasing problem hardness, as examined with regard to the CCP. This addresses [rq3:scalability] and confirms the practical viability of our approach.

Future research should explore several promising directions to further evaluate the approach and enhance its applicability and robustness. For example, by using CheckMate to verify the outputs of synthesized programs, we ensure solution correctness per instance, while establishing their overall correctness remains important future work. Moreover, we will conduct systematic ablation studies to quantify the contribution of every CheckMate component.

Acknowledgments↩︎

This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/COE12 and the Austrian Research Promotion Agency (FFG) FO999910235 (SAELING) and 930480ATRIA (ATRIA).

References↩︎

---

1. The first three authors contributed equally and are listed in alphabetical order. The same holds for the last three authors.↩︎

2. On early stopping, unevaluated instances are deemed incorrect.↩︎

3. Normalization must ensure the maximization of each score. For decision problems, we assign a trivial quality score of \(1\) to any correct solution, whereas for optimization problems, we require lower and upper bounds for each objective of every instance for scoring.↩︎

4. https://www.voestalpine.com/↩︎