Algebraic Structure Discovery for Real World Combinatorial Optimisation Problems: A General Framework from Abstract Algebra to Quotient Space Learning

• URL: http://arxiv.org/abs/2604.04941v1
• Date: Tue, 10 Mar 2026 23:47:16 GMT
• Title: Algebraic Structure Discovery for Real World Combinatorial Optimisation Problems: A General Framework from Abstract Algebra to Quotient Space Learning
• Abstract summary: Many optimisation problems hide algebraic structures that, once exposed, shrink the search space and improve the chance of finding the global optimal solution.<n>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.<n>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.
• Score: 7.0641522149099485
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Imputation Meets Clustering: Exploiting Latent Subgroup Structure for Missing Data Recovery [52.29866804948133]
  We propose CAGI (Cluster-Aware Generative Imputation), a framework that reformulates clustering and imputation as a mutually reinforcing co-optimization process.<n>Experiments on 14 benchmark datasets with 15 representative baselines demonstrate the superiority of CAGI.
  arXiv  Detail & Related papers  (2026-07-08T02:50:02Z)
• Ternary Gamma Semirings: From Neural Implementation to Categorical Foundations [0.14504054468850663]
  This paper establishes a theoretical framework connecting neural network learning with abstract algebraic structures.<n>We first present a minimal counterexample demonstrating that standard neural networks completely fail on compositional generalization tasks.<n>We prove that this learned feature space constitutes a finite commutative ternary $$-semiring, whose ternary operation implements the majority vote rule.
  arXiv  Detail & Related papers  (2026-03-15T14:56:33Z)
• Structural Segmentation of the Minimum Set Cover Problem: Exploiting Universe Decomposability for Metaheuristic Optimization [1.1011268090482575]
  The Minimum Set Cover Problem (MSCP) is a classical NP-hard optimization problem with numerous applications in science and engineering.<n>We investigate the concept of emphuniverse segmentability in the MSCP and analyze how intrinsic structural decomposition can be exploited to enhance intrinsic optimization.
  arXiv  Detail & Related papers  (2026-01-29T14:02:48Z)
• From Polynomials to Databases: Arithmetic Structures in Galois Theory [0.0]
  We develop a framework for classifying Galois groups of irreducible degree-7s over$mathbbQ$, combining explicit resolvent methods with machine learning techniques.<n>A database of over one million normalizedive project septics is constructed, each annotated with invariants$J_0, dots, J_4$ derived from binary transvections.
  arXiv  Detail & Related papers  (2025-11-20T18:29:38Z)
• Hierarchies for Semidefinite Optimization in $\mathcal{C}^\star$-Algebras [0.0]
  This paper presents a way for finite-dimensional relaxations of general cone programs on $mathcalCstar$-algebras. We show that well-known hierarchies for generalized problems like NPA but also Lasserre's hierarchy and to some extend symmetry reductions of generic SDPs.
  arXiv  Detail & Related papers  (2023-09-25T09:01:30Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• Exclusive Group Lasso for Structured Variable Selection [10.86544864007391]
  A structured variable selection problem is considered. A composite norm can be properly designed to promote such exclusive group sparsity patterns. An active set algorithm is proposed that builds the solution by including structure atoms into the estimated support.
  arXiv  Detail & Related papers  (2021-08-23T16:55:13Z)
• Learning Algebraic Recombination for Compositional Generalization [71.78771157219428]
  We propose LeAR, an end-to-end neural model to learn algebraic recombination for compositional generalization. Key insight is to model the semantic parsing task as a homomorphism between a latent syntactic algebra and a semantic algebra. Experiments on two realistic and comprehensive compositional generalization demonstrate the effectiveness of our model.
  arXiv  Detail & Related papers  (2021-07-14T07:23:46Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  We present a new class of geometrically-driven optimization algorithms on the orthogonal group $O(d)$. We show that our methods can be applied in various fields of machine learning including deep, convolutional and recurrent neural networks, reinforcement learning, flows and metric learning.
  arXiv  Detail & Related papers  (2020-03-30T15:37:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.