Many combinatorial optimisation problems hide algebraic structures that, once exposed, shrink the search space and improve the chance of finding the global optimal solution. We present a general framework that (i) identifies algebraic structure, (ii) formalises operations, (iii) constructs quotient spaces that collapse redundant representations, and (iv) optimises directly over these reduced spaces. Across a broad family of rule-combination tasks (e.g., patient subgroup discovery and rule-based molecular screening), conjunctive rules form a monoid. Via a characteristic-vector encoding, we prove an isomorphism to the Boolean hypercube {0,1}n with bitwise OR, so logical AND in rules becomes bitwise OR in the encoding. This yields a principled quotient-space formulation that groups functionally equivalent rules and guides structure-aware search. On real clinical data and synthetic benchmarks, quotient-space-aware genetic algorithms recover the global optimum in 48% to 77% of runs versus 35% to 37% for standard approaches, while maintaining diversity across equivalence classes. These results show that exposing and exploiting algebraic structure offers a simple, general route to more efficient combinatorial optimisation.
Figures & tables
E=Ck∈C:∣Ck∣≥minPts,k=0⋃{argxi∈Ckmaxf(xi)}
Algorithm 1 Genetic Algorithm: Standard vs. Quotient-Aware Comparison
Scenario
Method
Runs
Mean
Std
Time
Fitness
Dev
(s)
Real Data
GA (With Quotient Space)
1152
82.63
52.41
46.6
(No Numeric)
GA (No Quotient Space)
1152
79.52
50.38
20.7
BO (With Quotient Space)
1296
53.41
44.56
13.9
BO (No Quotient Space)
1295
53.36
44.55
14.0
Greedy Algorithm
540
58.10
46.10
0.88
Table 1: Performance Summary Across All Experimental Scenarios
Scenario
Method
Mean
Median
% of Cases Achieving
Ratio
Ratio
Global Optimum
Real Data
GA (With Quotient Space)
0.9937
1.0000
77.26%
(No Numeric)
GA (No Quotient Space)
0.9635
0.9791
34.64%
BO (With Quotient Space)
0.6554
0.6253
2.55%
BO (No Quotient Space)
0.6574
0.6218
2.47%
Greedy Algorithm
0.7069
0.7095
2.78%
Table 2: Global Optimum Achievement Analysis by Method
Figure 1: Genetic Algorithm Performance Comparison: Real Data With vs Without Quotient Space Learning across Feature Configurations. The side-by-side comparison demonstrates consistent improvements when quotient space learning is incorporated into GA methods across both categorical-only (a) and mixed categorical-numeric (b) feature scenarios.
Figure 2: Bayesian Optimisation Performance Comparison: With vs Without Quotient Space Learning across Feature Configurations. In contrast to GA methods, BO approaches show mixed and inconsistent results from quotient space learning integration across both feature scenarios, suggesting that the Hamming distance kernel and quotient space approach may be less optimal for BO-based discrete optimisation in this domain.
Figure 3: Comprehensive Stability Analysis for Real Clinical Data without Numeric Features. Solution diversity metrics reveal that quotient space learning maintains exploration capabilities while improving convergence quality even with simplified feature spaces.
Figure 4: Comprehensive Stability Analysis for Real Clinical Data with Numeric Features. (a) Coefficient of variation analysis demonstrates reduced variability in quotient-space-aware GA, indicating enhanced algorithmic stability in mixed feature spaces. (b) Number of unique solutions with continuous data is not appropriate as continuous threshold encoding can generate mathematically distinct but clinically equivalent rules (e.g., x > 12.5 vs x > 12.501), artificially inflating diversity measures without corresponding clinical significance.
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
Scientific discovery is fundamentally an optimization problem, defined by a vast state space'' of theories and experiments, and an evaluation criterion based on quality, novelty, and validity. Large language models (LLMs) have enabled automated exploration of this state space, but we argue that simultaneous modification of the evaluation criteria is equally important. Here, we propose formalizing research as meta-optimization, where the optimization objective itself is also being optimized. Our key contribution is consensus objective aggregation,'' where a portfolio of LLM-generated objective functions is combined via correlation-weighted voting, allowing the evaluation criterion to evolve alongside the solutions. We apply this framework to algorithm discovery for planted 3-SAT problems based on digital memcomputing machines. The leading solver from the consensus search reduces median integration steps by more than 38× relative to a tuned baseline at 2,560 variables. Objective ablations show that a well-chosen fixed expert objective can also discover strong solvers, while consensus supplies a stable ranking that mitigates reward hacking behaviors. By bringing objective engineering into the discovery loop, this framework offers a practical route toward more adaptable automated research.
Yuan-Hang Zhang, Chesson Sipling, Massimiliano Di Ventra
We introduce qtBench, a benchmark of 29 open problems in algebraic combinatorics. These problems ask for a simple combinatorial algorithm that explains given polynomial coefficients or identities. To help AI agents search for such algorithms, we provide a scaffold for playing with combinatorial objects, countering cheating attempts, and testing candidate solutions. To explore how far frontier AI systems can go on these problems, we collaborated with OpenAI, whose researchers obtained proposed solutions to several of them. This highlights bigger meta-problems: is AI discovery at scale ethical? How should these results be released? How should proof digestion be organized? We discuss these questions and give our views.
Eugenio Cainelli, Lorenzo Luccioli, Alessandro Iraci +1
Inspired by long-standing open problems in algebraic combinatorics, we show that modern machine learning can meaningfully contribute to verifiable mathematical discoveries. In particular, we focus on the construction of simple mathematical functions under exact distributional constraints, a setting we formalize as Simple Learning Under Rigid Proportions (SLURP). We tackle this problem by introducing two methods: MapSeek-Functional, which models the desired function alternating pseudo-labeling and supervised training steps; and MapSeek-Symbolic, designed to directly produce symbolic formulas. We successfully apply both methods to a research problem in algebraic combinatorics, discovering a new combinatorial interpretation of the q,t-Narayana polynomials arising from representation theory. To our knowledge, this is the first such interpretation based on noncrossing partitions. Using one discovered statistic, we find a combinatorial proof of the symmetry of these polynomials in a previously unsolved case. To streamline verification and reproducibility, we release all code, including a formalization of all the mathematical discoveries of this paper in Lean 4.
Eugenio Cainelli, Lorenzo Luccioli, Alessandro Iraci +2
University of Bologna · Pegaso University · University of Pisa