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

Yuyang Liu

cs.AIMar 19, 2026

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

Authors: Yuyang Liu

Organizations: Independent Researcher, Shenzhen, China

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

Figures & tables

Method	GPU	Univ. Enc.	AOS	Op. Ext.	Python	New Problem
MIP (SCIP/CBC)	$\times$	$\times$	$\times$	$\times$	$\checkmark$	Math modeling
OR-Tools Routing	$\times$	$\times$	$\times$	$\times$	$\checkmark$	Not supported
cuOpt [ 17 ]	$\checkmark$	$\times$	$\times$	$\times$	$\checkmark$	VRP/MILP only
GPU-ACO [ 4 ]	$\checkmark$	$\times$	$\times$	$\times$	$\times$	Rewrite kernel
ALNS [ 23 ]	$\times$	$\checkmark$	$\checkmark$	$\checkmark$	$\times$	Custom op. pairs
GPU-EA [ 26 ]	$\checkmark$	Partial	$\times$	$\times$	$\times$	Partial rewrite

Table 1: Feature comparison of cuGenOpt with existing approaches.

Figure 1: cuGenOpt system architecture. The framework provides three-layer abstraction: user interface (Python API and CUDA problem definition), core components (adaptive search and operator management), and GPU execution engine (L2-aware memory management and CUDA kernels).

Figure 2: GPU parallel execution model. The population is distributed across CUDA blocks (P blocks = population size). Within each block, 128 threads sample candidate moves in parallel, perform block-level reduction to find the best move, and thread 0 executes accept/reject decision. Shared memory holds current solution, operator weights, and reduction buffer.

Level	Scope	Representative Operators
Element	Single element	swap, insert, reverse (Perm); flip (Binary); random_reset (Int)
Segment	Contiguous segment	or-opt, 3-opt (Perm); seg_flip (Binary); seg_reset (Int)
Row	Entire row	row_swap, row_split, row_merge (encoding-agnostic)
Crossover	Two solutions	OX crossover (Perm); uniform crossover (Binary/Int)

Table 2: Search operator hierarchy.

Scale	3-opt ( $O(n^{3})$ )	or-opt ( $O(n^{2})$ )	LNS	LNS cap
Small ( $D_{2}\leq 100$ )	0.50	0.80	0.006	0.02
Medium ( $100<D_{2}\leq 250$ )	0.30	0.70	0.004	0.01
Large ( $D_{2}>250$ )	0.05	0.30	0.001	0.005

Table 3: Scale-driven operator weight presets.

Figure 3: Adaptive Operator Selection (AOS) mechanism. Each CUDA block maintains local statistics (usage count and improvement count) for each operator. Every 10 batches, weights are updated via EMA based on observed effectiveness. The two-level structure controls both K-step (number of operators per iteration) and sequence-level (specific operator) selection probabilities.

GPU	SMs	Max Shared Mem/Block	Architecture
Tesla T4	40	64 KB	Turing (sm_75)
Tesla V100	80	96 KB	Volta (sm_70)
A800/A100	108	164 KB	Ampere (sm_80)
H20/H100	132	228 KB	Hopper (sm_90)

Table 4: Maximum shared memory per block across GPU generations.

Figure 4: L2 cache-aware population sizing. The framework automatically adjusts population size to fit the working set into L2 cache, preventing cache thrashing. For TSP n=1000 (working set 3.8 MB), V100 (L2=6 MB) selects pop=32, while A800 (L2=40 MB) can support larger populations.

Figure 5: JIT compilation pipeline. User-provided CUDA code snippets (objective and constraints) are injected into a template, compiled via nvcc, and executed as a subprocess. SHA-256 hashing enables compilation caching. The entire process is transparent to users, appearing as a standard Python function call.

Component	Specification
GPU platforms (cuGenOpt)
Tesla T4	40 SMs, 64 KB shared/block, 4 MB L2, 320 GB/s
V100-SXM2	80 SMs, 96 KB shared/block, 6 MB L2, 900 GB/s
V100S-PCIE	80 SMs, 96 KB shared/block, 6 MB L2, 1134 GB/s
A800-SXM4	108 SMs, 164 KB shared/block, 40 MB L2, 2039 GB/s
CPU platform (baselines)

Table 5: Experimental environment.

Instance	cuGenOpt	SCIP	CBC	Winner
eil51 ( $n{=}51$ )	0.00%	69.5%	31.2%	cuGenOpt
ch150 ( $n{=}150$ )	0.34%	709.9%	infeasible	cuGenOpt
A-n32-k5 ( $n{=}32$ )	0.00%	56.8%	—	cuGenOpt

Table 6: cuGenOpt vs. MIP solvers (gap%, 60 s, Tesla T4).

Instance	$n$	cuGenOpt	OR-Tools	Winner
eil51	51	0.00%	0.00%	Tie
kroA100	100	0.00%	0.00%	Tie
ch150	150	0.34%	0.54%	cuGenOpt
tsp225	225	2.30%	$-$ 0.61%	OR-Tools
lin318	318	5.16%	2.85%	OR-Tools
pcb442	442	4.75%	1.87%	OR-Tools

Table 7: cuGenOpt vs. OR-Tools Routing (gap%, 60 s, Tesla T4).

Figure 6: Baseline comparison across TSP instances. cuGenOpt dominates general MIP solvers (SCIP/CBC) across all scales, with gaps 100-2000× smaller. Against specialized routing solvers (OR-Tools Routing with GLS metaheuristic), cuGenOpt is competitive at small-medium scale ( $n\leq 150$ ) but trails at large scale ( $n>200$ ).

Scenario A: Priority constraints
Metric	cuGenOpt	OR-Tools
Priority violations	0	17
Scenario B: Nonlinear cost
Nonlinear cost	826.67	874.30

Table 8: Custom scenario comparison (A-n32-k5, 60 s, Tesla T4).

Instance	$n$	T4	V100	A800	T4 g/s	V100 g/s	A800 g/s
eil51	51	0.09	0.00	0.00	4,160	3,307	4,821
kroA100	100	0.14	0.05	0.02	5,717	2,361	3,115
ch150	150	2.02	0.78	1.14	1,698	1,613	2,135
tsp225	225	2.82	2.82	3.50	1,781	3,102	2,344
lin318	318	3.61	3.51	6.49	996	1,470	1,149
pcb442	442	6.15	5.29	4.73	621	805	1,348

Table 9: Three-GPU TSP comparison (mean gap%, 30 s, 5 seeds).

Figure 7: Cross-hardware solution quality comparison (30s, gap%). Three memory regimes emerge: (1) Shared memory regime ( $n\leq 100$ ): A800’s 164KB shared memory enables best quality. (2) L2 cache regime (n=150-225): A800’s adaptive large population (P=128) hurts convergence despite ample L2. (3) DRAM regime ( $n\geq 318$ ): A800’s 40MB L2 and 2TB/s bandwidth achieve best quality at large scale.

Problem	$n$	Solution	Time (s)	Gens/s
TSP	300	8,156.07	4.2	1,190
TSP	1000	77,691.52	15.3	327
VRP	150	4,504.37	3.8	1,316
VRP	500	56,732.55	10.1	495
VRP	1000	163,426.00	18.7	267

Table 10: Large-scale problem results (V100S, 5000 generations).

Problem	$n$	1 GPU	2 GPUs	Improv.	CUDA Graph
TSP	150	4,504.37	4,395.03	+2.43%	Enabled
TSP	300	8,156.07	8,054.83	+1.24%	Enabled
TSP	1000	77,691.52	74,962.60	+3.51%	Enabled
TSP	1000	43,888.89	43,600.11	+0.66%	Disabled
VRP	50	4,569.13	4,473.00	+2.10%	Enabled
VRP	500	56,732.55	55,624.84	+1.95%	Enabled

Table 11: Multi-GPU comparison (2×V100S, 5000 generations, mean of 3 runs).

Figure 8: Multi-GPU improvement across problem scales. TSP shows increasing benefit with scale, reaching 3.51% at n=1000 (CUDA Graph enabled). CUDA Graph configuration significantly affects effectiveness (3.51% vs 0.66%). VRP effectiveness depends on both scale and problem feasibility.

Config	Vehicles	1 GPU	2 GPUs	Improv.
Insufficient	24	266,471.97	266,471.97	0.00%
Adequate	80	56,732.55	55,624.84	1.95%

Table 12: VRP configuration impact on multi-GPU effectiveness (n=500).

Problem	Encoding	Optimal	cuGenOpt	5/5 hit
TSP5	Perm	18	18.00	✓
Knapsack6	Binary	30	30.00	✓
Assign4	Perm	13	13.00	✓
Schedule3x4	Binary	21	21.00	✓
CVRP10	Perm-MR	200	200.00	✓
LoadBal8	Integer	14	14.00	✓

Table 13: Generality validation (12 problems, 5 encodings, 2000 generations).

Instance	Problem	T4	V100	A800	T4 g/s	V100 g/s	A800 g/s
nug12	QAP	0.00	0.00	0.00	8,197	14,285	15,121
tai15a	QAP	0.004	0.004	0.00	6,605	12,854	13,530
ft06	JSP	0.00	0.00	0.00	1,622	4,930	4,956
ft10	JSP	0.84	0.84	0.47	519	1,538	1,725
knapPI_1	Knapsack	0.00	0.00	0.00	2,965	6,107	11,215
R101	VRPTW	2.12	2.44	2.09	2,060	2,507	2,039

Table 14: Standard benchmark results (mean gap%, 30 s, 5 seeds).

Version	Gap%	Gens/s	Description
Baseline	36.35	116	Random init, per-gen AOS update
+Heuristic init + AOS freq	6.32	395	Bidirectional init, AOS interval $1\to 10$
+Profile weights	5.78	408	L1 prior-driven operator presets
+Pop. adaptation	6.15	625	Pop $64\to 32$ , gens/s +53%
Cross-hardware (same code)
V100	5.29	805	Pop=32, L2=6 MB

Table 15: Cumulative optimization ablation on pcb442.

Figure 9: Cumulative optimization impact on pcb442 (Tesla T4, 30s). Heuristic initialization provides the largest improvement (-82% gap). AOS update frequency optimization boosts throughput by 240%. Profile-driven weights and population adaptation further refine solution quality and throughput. Final configuration achieves 6.15% gap at 625 gens/s.

Instance	Before g/s	After g/s	$\Delta$ g/s	$\Delta$ gap
R101	1,150	2,060	+79%	$-$ 0.29 pp
C101	1,140	1,997	+75%	$-$ 1.53 pp
RC101	1,133	2,047	+81%	$-$ 0.83 pp

Table 16: Shared memory extension impact on VRPTW (T4, 30 s).

Instance	Limit	Built-in only	+Custom	Improvement
TSP-50	1 s	0.00%	0.00%	—
TSP-100	2 s	0.42%	0.37%	$-$ 12%
TSP-150	3 s	1.85%	1.22%	$-$ 34%

Table 17: User-defined operator effect (RTX 3080 Ti, 5 seeds).

Weights	Distance	Vehicles	Gap%	Time(s)	Gens
$[0.9,0.1]$	784.00	5.00	0.0%	0.4	1000

Table 18: Weighted mode results on bi-objective VRP (A-n32-k5). Tesla V100S, 1000 generations, seed=42.

Priority	Tolerance	Distance	Vehicles	Gap%
$[\text{dist},\text{veh}]$	$[100,0]$	962.00	5.00	22.7%
$[\text{dist},\text{veh}]$	$[50,0]$	814.00	5.00	3.8%
$[\text{veh},\text{dist}]$	$[0,100]$	1644.00	5.00	109.7%

Table 19: Lexicographic mode results on bi-objective VRP (A-n32-k5). Tesla V100S, 1000 generations, seed=42.

Mode	Config	Distance	Vehicles	Max Route
Weighted	$[0.6,0.2,0.2]$	829.00	5.00	238.00
Lexicographic	$[\text{dist},\text{veh},\text{max}]$	881.00	5.00	259.00
Lexicographic	$[\text{veh},\text{dist},\text{max}]$	1543.00	5.00	451.00

Table 20: Tri-objective VRP results (A-n32-k5). Objectives: distance, vehicle count, max route length. Tesla V100S, 1000 generations, seed=42.

Mode	GPU	Distance	Vehicles	Selected
Weighted $[0.7,0.3]$	GPU0	796.00	5.00
	GPU1	784.00	5.00	✓
	Final	784.00	5.00
Lexicographic $[\text{dist},\text{veh}]$	GPU0	840.00	5.00	✓
	GPU1	962.00	5.00
	Final	840.00	5.00

Table 21: Multi-GPU compatibility verification for multi-objective modes (A-n32-k5, 2×V100S).

D1	D2	Size (KB)	Status	Note
24	512	48	Success	—
80	128	40	Success	Optimal balance
160	128	80	Success	Near limit
32	1024	128	Failed	Exceeds limit

Table 22: VRP Solution structure size observations.

Problem size	CUDA Graph enabled	CUDA Graph disabled
$n{=}1000$	Success	Success
$n{=}1200$	Failed (illegal memory)	Success
$n{=}1500$	Failed	Success
$n{=}2000$	Failed	Failed (other issue)

Table 23: CUDA Graph compatibility observations (TSP).

Metaheuristic Optimization

Metaheuristic optimization develops flexible search strategies for finding strong solutions to difficult problems when exact methods are too costly.

See all 115 papers

Generation of Custom Solvers in Rust for Convex Optimization
Sep 12, 2026Hao Zhu, Joschka BoedeckerCode Generation Constrained Optimization
IMBIT//BrainLinks-BrainTools · Department of Computer Science, University of Freiburg
optimize_anything: A Universal API for Optimizing any Text Parameter
May 19, 2026Lakshya A Agrawal, Donghyun Lee, Shangyin Tan +11Black-Box Optimization Large Language Model-Guided Optimization
UC Berkeley USA · MIT USA
Differentiable Initialization-Accelerated CPU-GPU Hybrid Combinatorial Scheduling
Mar 30, 2026Mingju Liu, Jiaqi Yin, Alvaro Velasquez +1Combinatorial Optimization Integer Linear Programming
University of Maryland, College Park, Maryland, USA · University of Colorado, Boulder, Colorado, USA

Sep 12, 2026J/K move · Enter open · S save

Generation of Custom Solvers in Rust for Convex Optimization

Hao Zhu, Joschka Boedecker

IMBIT//BrainLinks-BrainTools · Department of Computer Science, University of Freiburg

Code Generation Constrained Optimization

Open paper AskPDF arXiv

We introduce cvxgenrust, an open-source tool for generating custom Rust code that solves families of parameterized convex optimization problems modeled in CVXPY. cvxgenrust canonicalizes a problem family, extracts affine maps to Clarabel cone-program data, and generates a specialized Rust crate that updates parameters and calls Clarabel natively at runtime. The generated solver can also be exposed to Python and registered as a custom CVXPY solver. Our code generator supports a wide range of convex optimization problems up to semidefinite programs and exponential-cone problems. Numerical experiments show reduced runtime relative to direct CVXPY solves and performance comparable to CVXPYgen on shared problem classes.

Abstract

Metaheuristic Optimization

Explore similar work

Generation of Custom Solvers in Rust for Convex Optimization

optimize_anything: A Universal API for Optimizing any Text Parameter

Differentiable Initialization-Accelerated CPU-GPU Hybrid Combinatorial Scheduling