Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation

• URL: http://arxiv.org/abs/2412.10163v1
• Date: Fri, 13 Dec 2024 14:25:27 GMT
• Title: Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation
• Authors: Federico Julian Camerota Verdù, Lorenzo Castelli, Luca Bortolussi,
• Abstract summary: We introduce Limited Rollout Beam Search (LRBS), a beam search strategy for deep reinforcement learning (DRL) based optimization improvements.<n>We show that LRBS significantly enhances both in-distribution performance and generalization to larger problem instances.<n>We also employ our search strategy for offline and online adaptation of the pre-trained improvement policy, leading to improved search performance.
• Score: 0.40964539027092917
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce Limited Rollout Beam Search (LRBS), a beam search strategy for deep reinforcement learning (DRL) based combinatorial optimization improvement heuristics. Utilizing pre-trained models on the Euclidean Traveling Salesperson Problem, LRBS significantly enhances both in-distribution performance and generalization to larger problem instances, achieving optimality gaps that outperform existing improvement heuristics and narrowing the gap with state-of-the-art constructive methods. We also extend our analysis to two pickup and delivery TSP variants to validate our results. Finally, we employ our search strategy for offline and online adaptation of the pre-trained improvement policy, leading to improved search performance and surpassing recent adaptive methods for constructive heuristics.

Related papers

• Advancing CMA-ES with Learning-Based Cooperative Coevolution for Scalable Optimization [12.899626317088885]
  This paper introduces LCC, a pioneering learning-based cooperative coevolution framework. LCC dynamically schedules decomposition strategies during optimization processes. It offers certain advantages over state-of-the-art baselines in terms of optimization effectiveness and resource consumption.
  arXiv  Detail & Related papers  (2025-04-24T14:09:22Z)
• RL-finetuning LLMs from on- and off-policy data with a single algorithm [53.70731390624718]
  We introduce a novel reinforcement learning algorithm (AGRO) for fine-tuning large-language models. AGRO leverages the concept of generation consistency, which states that the optimal policy satisfies the notion of consistency across any possible generation of the model. We derive algorithms that find optimal solutions via the sample-based policy gradient and provide theoretical guarantees on their convergence.
  arXiv  Detail & Related papers  (2025-03-25T12:52:38Z)
• Make Optimization Once and for All with Fine-grained Guidance [78.14885351827232]
  Learning to Optimize (L2O) enhances optimization efficiency with integrated neural networks. L2O paradigms achieve great outcomes, e.g., refitting, generating unseen solutions iteratively or directly. Our analyses explore general framework for learning optimization, called Diff-L2O, focusing on augmenting solutions from a wider view.
  arXiv  Detail & Related papers  (2025-03-14T14:48:12Z)
• BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization [17.694852175354555]
  Preference Optimization for Combinatorial Optimization (POCO) is a training paradigm that leverages solution preferences via objective values. POCO is architecture-agnostic, enabling integration with existing NCO models, and establishes preference optimization as a principled framework for optimization.
  arXiv  Detail & Related papers  (2025-03-10T17:45:30Z)
• Discovering Preference Optimization Algorithms with and for Large Language Models [50.843710797024805]
  offline preference optimization is a key method for enhancing and controlling the quality of Large Language Model (LLM) outputs. We perform objective discovery to automatically discover new state-of-the-art preference optimization algorithms without (expert) human intervention. Experiments demonstrate the state-of-the-art performance of DiscoPOP, a novel algorithm that adaptively blends logistic and exponential losses.
  arXiv  Detail & Related papers  (2024-06-12T16:58:41Z)
• Primitive Agentic First-Order Optimization [0.0]
  This work presents a proof-of-concept study combining primitive state representations and agent-environment interactions as first-order reinforcement learning. The results show that elementary RL methods combined with succinct partial state representations can be used as optimizeds manage complexity in RL-based optimization.
  arXiv  Detail & Related papers  (2024-06-07T11:13:38Z)
• Unleashing the Potential of Large Language Models as Prompt Optimizers: An Analogical Analysis with Gradient-based Model Optimizers [108.72225067368592]
  We propose a novel perspective to investigate the design of large language models (LLMs)-based prompts. We identify two pivotal factors in model parameter learning: update direction and update method. In particular, we borrow the theoretical framework and learning methods from gradient-based optimization to design improved strategies.
  arXiv  Detail & Related papers  (2024-02-27T15:05:32Z)
• Acceleration in Policy Optimization [50.323182853069184]
  We work towards a unifying paradigm for accelerating policy optimization methods in reinforcement learning (RL) by integrating foresight in the policy improvement step via optimistic and adaptive updates. We define optimism as predictive modelling of the future behavior of a policy, and adaptivity as taking immediate and anticipatory corrective actions to mitigate errors from overshooting predictions or delayed responses to change. We design an optimistic policy gradient algorithm, adaptive via meta-gradient learning, and empirically highlight several design choices pertaining to acceleration, in an illustrative task.
  arXiv  Detail & Related papers  (2023-06-18T15:50:57Z)
• Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimization [42.92248233465095]
  We propose a simple but effective method, called symmetric replay training (SRT), which can be easily integrated into various Deep reinforcement learning (DRL) methods. Our method leverages high-reward samples to encourage exploration of symmetric regions without additional online interactions - free. Experimental results demonstrate the consistent improvement of our method in sample efficiency across diverse DRL methods applied to real-world tasks.
  arXiv  Detail & Related papers  (2023-06-02T05:34:01Z)
• Provable Reward-Agnostic Preference-Based Reinforcement Learning [61.39541986848391]
  Preference-based Reinforcement Learning (PbRL) is a paradigm in which an RL agent learns to optimize a task using pair-wise preference-based feedback over trajectories. We propose a theoretical reward-agnostic PbRL framework where exploratory trajectories that enable accurate learning of hidden reward functions are acquired.
  arXiv  Detail & Related papers  (2023-05-29T15:00:09Z)
• Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning [4.374837991804085]
  We introduce a Deep Reinforcement Learning based approach called DR-ALNS that selects operators, adjusts parameters, and controls the acceptance criterion throughout the search. We evaluate the proposed method on a problem with orienteering weights and time windows, as presented in an IJCAI competition. The results show that our approach outperforms vanilla ALNS, ALNS tuned with Bayesian optimization, and two state-of-the-art DRL approaches.
  arXiv  Detail & Related papers  (2022-11-01T21:33:46Z)
• Sample-Efficient, Exploration-Based Policy Optimisation for Routing Problems [2.6782615615913348]
  This paper presents a new reinforcement learning approach that is based on entropy. In addition, we design an off-policy-based reinforcement learning technique that maximises the expected return. We show that our model can generalise to various route problems.
  arXiv  Detail & Related papers  (2022-05-31T09:51:48Z)

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.