We study online service with one maximum-waiting-time charge per service batch. The persistent server endpoint prevents a phase-by-phase comparison with the offline optimum: an offline schedule may merge many online phases, share movement globally, and finish at unrelated endpoints. Our main contribution is a metric-independent \emph{group--trajectory certificate framework} that restores such a comparison. For ordered request groups in disjoint time windows, a certificate value is bounded both by the window length and by the metric Steiner cost of the group. After normalizing the offline schedule into consecutive arrival blocks, strictly interior groups are charged to offline delay, while boundary groups induce connectors of congestion at most two along the offline trajectory. One color class therefore has certificate sum at most $2\OPT$; a parity decomposition yields $\sum_h C_h\le4\OPT$. Consequently, any phase rule whose cost is at most $\alpha C_h$ is $4\alpha$-competitive. For visible service, this theorem yields deterministic ratios $10$ on a line, $12$ on a weighted tree, and $20$ on an arbitrary finite metric; the last algorithm is polynomial and uses a phase-local terminal-MST envelope, while an exact metric-Steiner oracle gives ratio $12$. Structurally, elective and automatic schedules can have different event structures but equal offline optimal values. The common value is computable exactly in polynomial time on lines and explicitly represented weighted trees, whereas exact optimization on arbitrary finite metrics is NP-hard. Finally, we use spatial blindness---announced requests whose locations are revealed only when visited---as a stress test: dyadic exploration preserves a constant ratio on a known finite line, while a single hidden request on a star forces a loss linear in its degree.
Tianhan Lu, Runtian Ren, Shengcai Liu et al.· 0 citations
Tool-using large language model (LLM) agents produce long, multi-turn trajectories, making gradient-based post-training memory-intensive. Evolution strategies (ES) enable memory-efficient full-parameter post-training without backpropagation and can eventually match the performance of gradient-based reinforcement learning (RL). However, resource-constrained settings typically offer only a few GPUs, so the high GPU-hour requirements of ES translate into prohibitively long training times. To address this, we introduce Cooperative Parameter-subspace Evolution Strategy (CoPES), a cooperative coevolutionary method that decomposes the full parameter space into lower-dimensional subspaces and searches over them cooperatively to improve optimization efficiency. We post-train a Qwen3.5-4B tool-using agent for the math task and evaluate it on five benchmarks of varying difficulty. Under the GPU-hour budget of full-parameter GRPO's best validation checkpoint, CoPES recovers 92% of GRPO's validation-accuracy gain, versus 67% for standard ES, while its theoretical GPU memory requirement is less than one-eighth that of full-parameter GRPO. It consistently outperforms standard ES and LoRA-based GRPO on all evaluated pass@k metrics across the five benchmarks. Additional experiments further show the advantage of CoPES on the question-answering task. These results demonstrate an improved trade-off between memory requirements and training time for agentic LLM post-training under resource constraints. The code is open-sourced in https://github.com/MetaronWang/CoPES
Zhiyuan Wang, Shengcai Liu, Jiahao Wu et al.· 1 citation
OptiDSL is proposed, a framework that shifts the focus from rigid MILP formulations to domain-specific language (DSL) representations, and enables seamless integration with a diverse library of specialized solvers, ranging from traditional heuristics to modern learning-based methods.
Shaofeng Zhang, Hongyuan Su, Qing Peng et al.· 0 citations
The potential gain metric is proposed, a novel metric that eliminates the need for reference solutions and consistently outperforms state-of-the-art LLM-ACP baselines, notably achieving a 19.76% relative improvement for TSP Greedy Constructive portfolios.
Shaofeng Zhang, Shengcai Liu, Zhiyuan Wang et al.· 0 citations
Large language model-based automated heuristic design (LLM-AHD) has shown strong potential in discovering effective heuristics for combinatorial optimization problems. However, existing methods primarily optimize a single heuristic, whereas practical optimization frameworks often rely on multiple interacting components. Directly extending single-heuristic methods is challenging because early component selection can overlook components with late potential, while independent evolution ignores inter-component dependencies. We propose MuEvo, an LLM-driven framework for evolving heuristic ensembles under ensemble-level feedback. MuEvo combines Dynamic Component Management, which uses short-budget probing and a reversible lifecycle to revise component priorities throughout the search, with LLM-Driven Co-Evolution, which coordinates component populations through Multi-Ensemble Evaluation, Cross-Component Information Sharing, Relation-Guided Pair Evolution, and Adaptive Budget Allocation. We evaluate MuEvo on selection hyper-heuristics and componentized ant colony optimization across four combinatorial optimization domains. Results show that MuEvo consistently improves human-designed frameworks and outperforms representative multi-component extensions of state-of-the-art LLM-AHD methods, demonstrating its effectiveness across both controller-mediated heuristic pools and functionally differentiated algorithmic components.
Haoze Lv, Ning Lu, Shengcai Liu et al.· 0 citations