RedAHD: Reduction-Based End-to-End Automatic Heuristic Design with Large Language Models

• URL: http://arxiv.org/abs/2505.20242v1
• Date: Mon, 26 May 2025 17:21:16 GMT
• Title: RedAHD: Reduction-Based End-to-End Automatic Heuristic Design with Large Language Models
• Authors: Nguyen Thach, Aida Riahifar, Nathan Huynh, Hau Chan,
• Abstract summary: We propose a novel end-to-end framework, named RedAHD, that enables these LLM-based design methods to operate without the need of humans.<n>More specifically, RedAHD employs LLMs to automate the process of reduction, i.e., transforming the COP at hand into similar COPs that are better-understood.<n>Our experimental results, evaluated on six COPs, show that RedAHD is capable of designing or improved results over the state-of-the-art methods with minimal human involvement.
• Score: 14.544461392180668
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving NP-hard combinatorial optimization problems (COPs) (e.g., traveling salesman problems (TSPs) and capacitated vehicle routing problems (CVRPs)) in practice traditionally involves handcrafting heuristics or specifying a search space for finding effective heuristics. The main challenges from these approaches, however, are the sheer amount of domain knowledge and implementation efforts required from human experts. Recently, significant progress has been made to address these challenges, particularly by using large language models (LLMs) to design heuristics within some predetermined generalized algorithmic framework (GAF, e.g., ant colony optimization and guided local search) for building key functions/components (e.g., a priori information on how promising it is to include each edge in a solution for TSP and CVRP). Although existing methods leveraging this idea have shown to yield impressive optimization performance, they are not fully end-to-end and still require considerable manual interventions. In this paper, we propose a novel end-to-end framework, named RedAHD, that enables these LLM-based heuristic design methods to operate without the need of GAFs. More specifically, RedAHD employs LLMs to automate the process of reduction, i.e., transforming the COP at hand into similar COPs that are better-understood, from which LLM-based heuristic design methods can design effective heuristics for directly solving the transformed COPs and, in turn, indirectly solving the original COP. Our experimental results, evaluated on six COPs, show that RedAHD is capable of designing heuristics with competitive or improved results over the state-of-the-art methods with minimal human involvement.

Related papers

• Large Language Models for Design Structure Matrix Optimization [4.513609458468522]
  In complex engineering systems, the interdependencies among components or development activities are often modeled and analyzed using Design Structure Matrix (DSM)<n>Reorganizing elements within a DSM to minimize feedback loops and enhance modularity or process efficiency constitutes a challenging optimization problem in engineering design and operations.<n>In this study, we explore the potential of Large Language Models (LLMs) for helping solve such CO problems by leveraging their capabilities for advanced reasoning and contextual understanding.
  arXiv  Detail & Related papers  (2025-06-11T13:53:35Z)
• STRCMP: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization [18.162186876640764]
  Combinatorial optimization (CO) problems, central to operation research and theoretical computer science, present significant computational challenges due to their NP-hard nature.<n>We propose STRCMP, a novel structure-aware algorithm discovery framework that systematically integrates structure priors to enhance solution quality and solving efficiency.<n>Our framework combines a graph neural network (GNN) for extracting structural embeddings from CO instances with an LLM conditioned on these embeddings to identify high-performing algorithms in the form of solver-specific codes.
  arXiv  Detail & Related papers  (2025-05-22T15:37:42Z)
• REMS: a unified solution representation, problem modeling and metaheuristic algorithm design for general combinatorial optimization problems [3.067143391336441]
  Combinatorial optimization problems (COPs) with discrete variables and finite search space are critical across numerous fields.<n>We introduce a resource-centered modeling and solving framework (REMS) for the first time.<n>REMS can model these COPs within the unified paradigm and effectively solve them with the designed metaheuristic algorithms.
  arXiv  Detail & Related papers  (2025-05-21T11:21:58Z)
• Efficient Heuristics Generation for Solving Combinatorial Optimization Problems Using Large Language Models [52.538586230181814]
  Recent studies exploited Large Language Models (LLMs) to autonomously generates for solving Combinatorial Optimization Problems (COPs)<n>The absence of task-specific knowledge in prompts often leads LLMs to provide unspecific search directions, obstructing derivation of well-performings.<n>We propose the Hercules algorithm, which leverages our designed Core Abstraction Prompting (CAP) method to abstract the core components from elite HGs and incorporate them as prior knowledge in prompts.
  arXiv  Detail & Related papers  (2025-05-19T02:20:46Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  Reinforcement Learning (RL) has emerged as a powerful tool for neural optimization, enabling models learns that solve complex problems without requiring expert knowledge.<n>Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast action spaces.<n>We propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling.
  arXiv  Detail & Related papers  (2025-05-13T16:47:00Z)
• Deep Insights into Automated Optimization with Large Language Models and Evolutionary Algorithms [3.833708891059351]
  Large Language Models (LLMs) and Evolutionary Algorithms (EAs) offer promising new approach to overcome limitations and make optimization more automated. LLMs act as dynamic agents that can generate, refine, and interpret optimization strategies. EAs efficiently explore complex solution spaces through evolutionary operators.
  arXiv  Detail & Related papers  (2024-10-28T09:04:49Z)
• Unsupervised Training of Diffusion Models for Feasible Solution Generation in Neural Combinatorial Optimization [7.85458999849461]
  We present IC/DC, an unsupervised CO framework that directly trains a diffusion model from scratch.<n>We train our model in a self-supervised way to minimize the cost of the solution while adhering to the problem-specific constraints.<n> IC/DC achieves state-of-the-art performance relative to existing NCO methods on the Parallel Machine Scheduling Problem (PMSP) and Asymmetric Traveling Salesman Problem (ATSP)
  arXiv  Detail & Related papers  (2024-10-15T06:53:30Z)
• In-context Demonstration Matters: On Prompt Optimization for Pseudo-Supervision Refinement [71.60563181678323]
  Large language models (LLMs) have achieved great success across diverse tasks, and fine-tuning is sometimes needed to further enhance generation quality.<n>To handle these challenges, a direct solution is to generate high-confidence'' data from unsupervised downstream tasks.<n>We propose a novel approach, pseudo-supervised demonstrations aligned prompt optimization (PAPO) algorithm, which jointly refines both the prompt and the overall pseudo-supervision.
  arXiv  Detail & Related papers  (2024-10-04T03:39:28Z)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)
• Learning Reward and Policy Jointly from Demonstration and Preference Improves Alignment [58.049113055986375]
  We develop a single stage approach named Alignment with Integrated Human Feedback (AIHF) to train reward models and the policy.<n>The proposed approach admits a suite of efficient algorithms, which can easily reduce to, and leverage, popular alignment algorithms.<n>We demonstrate the efficiency of the proposed solutions with extensive experiments involving alignment problems in LLMs and robotic control problems in MuJoCo.
  arXiv  Detail & Related papers  (2024-06-11T01:20:53Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  We introduce an NN-based solver to significantly narrow the gap with advanced metaheuristics. First, we propose direction-aware facilitating attention model (DaAM) to incorporate directionality into the embedding process. Second, we design a supervised reinforcement learning scheme that involves supervised pre-training to establish a robust initial policy.
  arXiv  Detail & Related papers  (2024-03-11T02:17:42Z)

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.