Everyday Hard Optimization Problems (EHOP)

EHOP是一个包含日常生活中NP难优化问题的数据集，这些问题以自然语言表达。数据集基于三个研究较为广泛的问题：图着色、背包问题和旅行商问题，每个问题都有八个变体，包括标准教材形式、现实生活中的伪装版本以及问题公式反转的版本。数据集旨在探究大型语言模型在面对现实世界问题和教材问题时的解决能力差异。

EHOP is a dataset containing NP-hard optimization problems from daily life, all expressed in natural language. The dataset is built upon three extensively studied problems: graph coloring, the knapsack problem, and the traveling salesman problem. Each of these problems includes eight variants, including standard textbook formulations, real-world disguised versions, and inversely formulated problem instances. This dataset aims to investigate the disparities in problem-solving capabilities of large language models when facing real-world problems versus textbook-style problems.

搜集汇总

数据集介绍

构建方式

数据集EHOP（Everyday Hard Optimization Problems）的构建方式涉及将常见的NP-hard优化问题以自然语言的形式表达出来。该数据集包含了三种基本问题：图着色、背包问题和旅行商问题。每个问题实例都被设计成三种不同的形式：教科书形式、现实生活情境形式以及规则反转形式。教科书形式的问题表述类似于计算机科学教材中的描述，现实生活情境形式则将问题包装成可能出现在日常生活中的实际问题，而规则反转形式则通过轻微改变问题表述来颠覆问题的解决方案。

特点

EHOP数据集的特点在于其多样性，它不仅包含了标准的问题表述，还包括了现实生活中的应用场景以及规则反转的变体。这种设计允许研究者评估语言模型在解决不同形式的问题时的表现差异。此外，EHOP数据集还包括了不同规模的实例，使得研究者可以观察模型在处理不同难度问题时的表现。

使用方法

使用EHOP数据集时，研究者可以评估不同语言模型在解决NP-hard优化问题时的能力。这可以通过多种提示策略进行，例如直接提示解决方案、链式思维提示、以及将问题转换为整数线性规划并使用专门的工具解决。通过比较不同模型在不同问题形式和规模上的表现，可以深入理解语言模型在问题解决和推理方面的能力。

背景与挑战

背景概述

在现实世界中，人们经常面临各种NP难度的优化问题，如家庭度假计划、航班机组人员排班等。这些问题虽然常见，但解决起来却相当困难。为了探索大型语言模型（LLMs）是否能够帮助非专业人士解决这类问题，研究人员亚历克斯·杜赫诺夫斯基、艾莉·帕夫利克和亚历山大·科勒创建了一个名为Everyday Hard Optimization Problems (EHOP)的数据集。EHOP包含用自然语言表达的NP难度优化问题，包括教科书形式的公式、现实生活中可能出现的问题版本，以及规则颠倒的变体。EHOP旨在帮助评估LLMs在解决实际问题时的表现，并为推理与复述之间的辩论提供新的证据。

当前挑战

EHOP数据集面临的主要挑战在于，当前的大规模语言模型在解决教科书问题方面表现出色，但在解决现实生活中的问题时却遇到了困难。这表明LLMs可能只是在复述训练数据中出现的解决方案，而不是真正理解并解决新问题。此外，EHOP数据集的实例大小有限，且基于三个经典的教科书问题，这限制了其在真实世界场景中的预测能力。为了提高LLMs的泛化能力，需要将问题解决过程明确地纳入训练流程中，并探索对话系统在实际问题解决中的应用。

常用场景

经典使用场景

EHOP数据集被设计来评估大型语言模型（LLMs）在解决日常生活中的NP难优化问题上的能力。该数据集包括图着色、背包和旅行商问题的教科书版本、现实世界版本以及反向版本，旨在探究LLMs是否能够进行系统性问题解决还是仅仅从训练数据中适应解决方案。EHOP的经典使用场景是在自然语言处理和人工智能领域的研究中，用于测试LLMs在理解、解释和解决自然语言表述的NP难优化问题方面的能力。

衍生相关工作

EHOP数据集的发布引发了一系列相关的研究工作。一些研究者在EHOP的基础上进行了扩展，增加了更多类型的NP难优化问题，例如车辆路径问题、调度问题和资源分配问题。此外，一些研究者还开发了新的评估指标和方法，以更全面地评估LLMs在解决NP难优化问题方面的能力。这些衍生工作进一步推动了LLMs在通用问题解决领域的研究和应用。

数据集最近研究

最新研究方向

Everyday Hard Optimization Problems (EHOP) 数据集的最新研究方向主要聚焦于大型语言模型（LLMs）在解决NP-hard优化问题方面的能力。该研究通过比较LLMs在处理教科书问题和现实生活中的问题时的表现，探讨了LLMs是否真的在进行系统性推理，或者它们是否只是从训练数据中适应解决方案。研究发现，LLMs在解决教科书问题方面表现更好，但在解决现实生活中的问题时则表现较差。这表明LLMs在遇到新的问题时，其泛化能力有限，更倾向于适应训练中见过的解决方案。这一发现对LLMs在解决现实世界问题方面的应用提出了挑战，并指出了LLMs未来发展的方向，即需要提高其在面对新问题时的泛化能力。

相关研究论文

• EHOP: A Dataset of Everyday NP-Hard Optimization Problems

  Saarland University · 2025年