Discovering Heuristics with Large Language Models (LLMs) for Mixed-Integer Programs: Single-Machine Scheduling

📄 arXiv: 2510.24013v1 📥 PDF

作者: İbrahim Oğuz Çetinkaya, İ. Esra Büyüktahtakın, Parshin Shojaee, Chandan K. Reddy

分类: cs.AI, cs.LG, cs.NE, math.CO, math.OC

发布日期: 2025-10-28

💡 一句话要点

利用大型语言模型发现单机调度启发式算法，显著提升求解效率。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 单机调度 启发式算法 大型语言模型 组合优化 总延迟

📋 核心要点

  1. 单机总延迟问题（SMTT）是NP-hard问题，传统启发式算法在求解大规模实例时存在局限性。
  2. 利用大型语言模型（LLM）自动发现新的启发式算法，旨在提升SMTT问题的求解效率和质量。
  3. 实验表明，LLM发现的EDDC和MDDC算法在不同规模的SMTT问题上均优于或媲美现有算法。

📝 摘要（中文）

本研究利用大型语言模型（LLM）发现了新的启发式算法，为调度和组合优化文献做出了贡献。研究重点是单机总延迟（SMTT）问题，该问题旨在通过在单个处理器上对n个作业进行排序来最小化总延迟，给定处理时间和截止日期。我们开发并评估了两种由LLM发现的新型启发式算法，即EDD Challenger（EDDC）和MDD Challenger（MDDC），它们受到著名的最早截止日期（EDD）和修改截止日期（MDD）规则的启发。与先前采用更简单的基于规则的启发式算法的研究不同，我们使用严格的标准评估了LLM发现的算法，包括SMTT的混合整数规划（MIP）公式得出的最优性差距和求解时间。我们将它们在各种作业规模（20、100、200和500个作业）上的性能与最先进的启发式算法和精确方法进行了比较。对于超过100个作业的实例，MIP和动态规划等精确方法在计算上变得难以处理。在最多500个作业的情况下，EDDC改进了经典的EDD规则和文献中另一种广泛使用的算法。MDDC始终优于传统的启发式算法，并且在较大和更复杂的实例上与精确方法相比仍具有竞争力。这项研究表明，即使在资源有限的情况下，有效配置的人机-LLM协作也可以为NP-hard约束组合优化生成可扩展的、高性能的启发式算法。

🔬 方法详解

问题定义：论文研究的是单机总延迟（SMTT）问题，目标是在给定作业的处理时间和截止日期的情况下，找到一个作业排序，使得所有作业的总延迟最小。现有方法，特别是传统的启发式算法，在大规模问题实例上表现不佳，难以在合理时间内找到高质量的解。精确方法，如混合整数规划（MIP）和动态规划，虽然可以找到最优解，但计算复杂度高，难以处理大规模问题。

核心思路：论文的核心思路是利用大型语言模型（LLM）的强大推理和生成能力，自动发现新的、更有效的启发式算法。LLM通过学习大量的文本数据，可以捕捉到问题内在的规律和模式，从而生成具有良好性能的启发式规则。这种方法避免了人工设计启发式算法的繁琐过程，并有可能发现人类难以想到的新策略。

技术框架：整体框架包括以下几个阶段：1) 问题定义和数据准备：明确SMTT问题的定义，并准备用于训练和评估LLM的数据集。2) LLM提示工程：设计合适的提示语，引导LLM生成启发式算法。3) 启发式算法生成：利用LLM生成候选的启发式算法。4) 算法评估和选择：使用一系列SMTT问题实例评估候选算法的性能，并选择最优的算法。5) 算法优化：对选定的算法进行进一步的优化，以提高其性能。

关键创新：最重要的技术创新点在于利用LLM自动发现启发式算法。与传统的人工设计启发式算法相比，这种方法具有更高的效率和潜力。LLM可以从大量数据中学习，并生成具有良好泛化能力的启发式规则。此外，LLM还可以根据问题的特点，生成定制化的启发式算法，从而进一步提高求解效率。

关键设计：论文中，EDDC和MDDC算法是基于LLM生成的。EDDC算法是对经典EDD规则的改进，MDDC算法是对MDD规则的改进。具体的改进方式由LLM自动生成，无需人工干预。论文还详细描述了如何使用MIP公式来评估启发式算法的性能，并使用最优性差距和求解时间作为评价指标。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，LLM发现的EDDC算法在高达500个作业的实例上优于经典的EDD规则和文献中另一种广泛使用的算法。MDDC算法始终优于传统的启发式算法，并且在较大和更复杂的实例上与精确方法相比仍具有竞争力。对于超过100个作业的实例，精确方法在计算上变得难以处理，而MDDC算法仍然能够找到高质量的解。

🎯 应用场景

该研究成果可应用于各种调度和组合优化问题，例如生产调度、资源分配、车辆路径规划等。通过利用LLM自动发现启发式算法，可以显著提高求解效率和质量，从而降低成本、提高效率，并为企业决策提供更好的支持。未来，该方法有望扩展到更复杂的优化问题，并与其他人工智能技术相结合，实现更智能化的决策。

📄 摘要（原文）

Our study contributes to the scheduling and combinatorial optimization literature with new heuristics discovered by leveraging the power of Large Language Models (LLMs). We focus on the single-machine total tardiness (SMTT) problem, which aims to minimize total tardiness by sequencing n jobs on a single processor without preemption, given processing times and due dates. We develop and benchmark two novel LLM-discovered heuristics, the EDD Challenger (EDDC) and MDD Challenger (MDDC), inspired by the well-known Earliest Due Date (EDD) and Modified Due Date (MDD) rules. In contrast to prior studies that employed simpler rule-based heuristics, we evaluate our LLM-discovered algorithms using rigorous criteria, including optimality gaps and solution time derived from a mixed-integer programming (MIP) formulation of SMTT. We compare their performance against state-of-the-art heuristics and exact methods across various job sizes (20, 100, 200, and 500 jobs). For instances with more than 100 jobs, exact methods such as MIP and dynamic programming become computationally intractable. Up to 500 jobs, EDDC improves upon the classic EDD rule and another widely used algorithm in the literature. MDDC consistently outperforms traditional heuristics and remains competitive with exact approaches, particularly on larger and more complex instances. This study shows that human-LLM collaboration can produce scalable, high-performing heuristics for NP-hard constrained combinatorial optimization, even under limited resources when effectively configured.