cuGenOpt: A GPU-Accelerated General-Purpose Metaheuristic Framework for Combinatorial Optimization

• URL: http://arxiv.org/abs/2603.19163v1
• Date: Thu, 19 Mar 2026 17:19:21 GMT
• Title: cuGenOpt: A GPU-Accelerated General-Purpose Metaheuristic Framework for Combinatorial Optimization
• Abstract summary: cuGenOpt is a general-purpose metaheuristic framework that addresses all three dimensions simultaneously.<n>At the engine level, cuGenOpt adopts a unified encoding abstraction (permutation, binary, integer), a two-level operator selection mechanism, and hardware-aware resource management.<n>Experiments show cuGenOpt suites outperforms general MIP solvers by orders of magnitude, competitive quality against specialized solvers, and attains 4.73% gap on TSP-442 within 30s.
• Score: 12.89168708039677
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Combinatorial optimization problems arise in logistics, scheduling, and resource allocation, yet existing approaches face a fundamental trade-off among generality, performance, and usability. We present cuGenOpt, a GPU-accelerated general-purpose metaheuristic framework that addresses all three dimensions simultaneously. At the engine level, cuGenOpt adopts a "one block evolves one solution" CUDA architecture with a unified encoding abstraction (permutation, binary, integer), a two-level adaptive operator selection mechanism, and hardware-aware resource management. At the extensibility level, a user-defined operator registration interface allows domain experts to inject problem-specific CUDA search operators. At the usability level, a JIT compilation pipeline exposes the framework as a pure-Python API, and an LLM-based modeling assistant converts natural-language problem descriptions into executable solver code. Experiments across five thematic suites on three GPU architectures (T4, V100, A800) show that cuGenOpt outperforms general MIP solvers by orders of magnitude, achieves competitive quality against specialized solvers on instances up to n=150, and attains 4.73% gap on TSP-442 within 30s. Twelve problem types spanning five encoding variants are solved to optimality. Framework-level optimizations cumulatively reduce pcb442 gap from 36% to 4.73% and boost VRPTW throughput by 75-81%. Code: https://github.com/L-yang-yang/cugenopt

Related papers

• A Reproducible Software Workflow for Unanchored Approximate MUB Optimization: A Case Study in Dimension Six [5.114953719334754]
  The workflow is designed for portable execution across CPU, Apple MPS, and HPC backends.<n>We optimize unanchored configurations across 100 random seeds for basis counts n = 3, 4, 5, 6 in complex128 and complex64 arithmetic.<n>We embed the representative d = 6, n = 4 transition unitaries into three-qubit 8x8 unitaries and execute the resulting circuits on the 156-qubit Heron processor ibm-marrakesh.
  arXiv  Detail & Related papers  (2026-07-12T07:24:25Z)
• optimize_anything: A Universal API for Optimizing any Text Parameter [98.42497715725356]
  We show a single AI-based optimization system-supporting single-task search, multi-task search with cross-problem transfer, and generalization to unseen inputs.<n>We show for the first time that text optimization with LLM-based search is a general-purpose problem-solving paradigm.
  arXiv  Detail & Related papers  (2026-05-19T10:18:12Z)
• From AI Assistant to AI Scientist: Autonomous Discovery of LLM-RL Algorithms with LLM Agents [51.12380889298618]
  POISE is a framework for automated discovery of policy optimization algorithms for language models.<n>PoISE maintains a structured, genealogically linked archive linking proposals, executable implementations, standardized evaluations, and natural-language reflections.
  arXiv  Detail & Related papers  (2026-03-25T05:19:23Z)
• Resource-Efficient Iterative LLM-Based NAS with Feedback Memory [49.44875022114861]
  Neural Architecture Search (NAS) automates network design, but conventional methods demand substantial computational resources.<n>We propose a closed-loop pipeline leveraging large language models (LLMs) to iteratively generate, evaluate, and refine convolutional neural network architectures.
  arXiv  Detail & Related papers  (2026-03-12T16:00:22Z)
• Protean Compiler: An Agile Framework to Drive Fine-grain Phase Ordering [2.5829132714658067]
  Protean Compiler is an agile framework to enable LLVM with built-in phase-ordering capabilities at a fine-grained scope.<n>The framework also comprises a complete library of more than 140 handcrafted static feature collection methods at varying scopes.<n>This paper showcases speedup gains of up to 4.1% on average and up to 15.7% on select Cbench applications wrt LLVM's O3.
  arXiv  Detail & Related papers  (2026-02-05T19:24:05Z)
• QiMeng-NeuComBack: Self-Evolving Translation from IR to Assembly Code [52.66657751895655]
  Large Language Models (LLMs) offer a compelling new paradigm: Neural Compilation.<n>This paper introduces NeuComBack, a novel benchmark dataset specifically designed for IR-to-assembly compilation.<n>We propose a self-evolving prompt optimization method that enables LLMs to evolve their internal prompt strategies.
  arXiv  Detail & Related papers  (2025-11-03T03:20:26Z)
• EquiBench: Benchmarking Large Language Models' Reasoning about Program Semantics via Equivalence Checking [58.15568681219339]
  We introduce EquiBench, a new benchmark for evaluating large language models (LLMs)<n>This task directly tests a model's ability to reason about program semantics.<n>We evaluate 19 state-of-the-art LLMs and find that in the most challenging categories, the best accuracies are 63.8% and 76.2%, only modestly above the 50% random baseline.
  arXiv  Detail & Related papers  (2025-02-18T02:54:25Z)
• All-to-all reconfigurability with sparse and higher-order Ising machines [0.0]
  We introduce a multiplexed architecture that emulates all-to-all network functionality. We show that running the adaptive parallel tempering algorithm demonstrates competitive algorithmic and prefactor advantages. scaled magnetic versions of p-bit IMs could lead to orders of magnitude improvements over the state of the art for generic optimization.
  arXiv  Detail & Related papers  (2023-11-21T20:27:02Z)
• INR-Arch: A Dataflow Architecture and Compiler for Arbitrary-Order Gradient Computations in Implicit Neural Representation Processing [66.00729477511219]
  Given a function represented as a computation graph, traditional architectures face challenges in efficiently computing its nth-order gradient. We introduce INR-Arch, a framework that transforms the computation graph of an nth-order gradient into a hardware-optimized dataflow architecture. We present results that demonstrate 1.8-4.8x and 1.5-3.6x speedup compared to CPU and GPU baselines respectively.
  arXiv  Detail & Related papers  (2023-08-11T04:24:39Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• QFactor: A Domain-Specific Optimizer for Quantum Circuit Instantiation [0.8258451067861933]
  We introduce a domain-specific algorithm for numerical optimization operations used by quantum circuit instantiation, synthesis, and compilation methods. QFactor uses a tensor network formulation together with analytic methods and an iterative local optimization algorithm to reduce the number of problem parameters.
  arXiv  Detail & Related papers  (2023-06-13T21:51:20Z)
• Towards making the most of NLP-based device mapping optimization for OpenCL kernels [5.6596607119831575]
  We extend the work of Cummins et al., namely Deeptune, that tackles the problem of optimal device selection ( CPU or GPU) for accelerated OpenCL kernels. We propose four different models that provide enhanced contextual information of source codes. Experimental results show that our proposed methodology surpasses that of Cummins et al. work, providing up to 4% improvement in prediction accuracy.
  arXiv  Detail & Related papers  (2022-08-30T10:20:55Z)
• Towards Accurate and Compact Architectures via Neural Architecture Transformer [95.4514639013144]
  It is necessary to optimize the operations inside an architecture to improve the performance without introducing extra computational cost. We have proposed a Neural Architecture Transformer (NAT) method which casts the optimization problem into a Markov Decision Process (MDP) We propose a Neural Architecture Transformer++ (NAT++) method which further enlarges the set of candidate transitions to improve the performance of architecture optimization.
  arXiv  Detail & Related papers  (2021-02-20T09:38:10Z)

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.