EHOP: A Dataset of Everyday NP-Hard Optimization Problem

该数据集用于日常NP难优化问题的实验，包含图着色、背包问题和旅行商问题等问题的实例和解决方案。

原始信息汇总

EHOP: 日常NP难优化问题数据集

数据集概述

EHOP数据集专注于日常生活中的NP难优化问题，包含用于实验的代码和数据集。该数据集旨在通过实验探索不同模型在解决NP难问题上的表现。

数据集结构

每个问题的包结构如下：

• model: 问题实例和解决方案的表示。
• generator: 生成问题实例的功能。
• llm: 基于LLM（大语言模型）的求解器。
• symbolic: 符号求解器。
• alt: 替代（通常为次优）求解器。

每个问题都会创建base目录中定义的类的子类，详细交互方式可参考base目录中的文档字符串和注释。

实验复现

环境要求

• Python版本 >= 3.10。
• 安装必要的依赖包：pip install -r requirements.txt。
• 使用Llama模型进行评估时，需通过Hugging Face获取模型访问权限并下载模型（Llama-3.1-70B-Instruct模型页面：https://huggingface.co/meta-llama/Llama-3.1-70B-Instruct）。
• 使用GPT模型进行评估时，需设置OpenAI API密钥为环境变量。

运行实验

给定问题（graph_coloring、knapsack或traveling_salesman）、模型（gpt或llama）和（子）数据集（random或hard），可通过以下命令运行实验： bash python main.py configs/<problem>/<model>-<dataset>.jsonnet

例如，使用GPT-4o在hard数据集的knapsack问题上运行实验： bash python main.py configs/knapsack/gpt-hard.jsonnet

注意事项

• 运行Llama实验时，需在配置文件中提供下载模型的路径。
• 避免同时使用相同模型运行random和hard数据集的实验，建议顺序运行并重命名结果文件。

自定义实验

• 实验配置文件：可通过创建自定义的.jsonnet文件来运行自定义实验，格式与提供的示例相同。
• 数据集生成：可使用问题目录中的generator.py文件生成自定义问题实例。

AI搜集汇总

数据集介绍

构建方式

EHOP数据集的构建围绕日常生活中的NP难优化问题展开，涵盖了图着色、背包问题和旅行商问题等多个经典优化场景。每个问题的实例通过`generator`模块生成，确保数据集的多样性和复杂性。数据集的结构化设计包括`model`、`llm`、`symbolic`和`alt`等模块，分别用于表示问题实例、基于大语言模型的求解器、符号求解器以及替代求解器，从而为研究提供了丰富的实验基础。

特点

EHOP数据集的特点在于其专注于日常生活中的NP难优化问题，涵盖了随机和困难两种子数据集，分别用于测试模型在不同复杂度下的表现。数据集提供了多种求解器选项，包括基于大语言模型（如GPT和Llama）的求解器以及符号求解器，为研究者提供了灵活的对比实验平台。此外，数据集的实例命名规则一致，便于结果的组织和分析，同时支持自定义实验配置和数据集生成，进一步增强了其可扩展性和实用性。

使用方法

使用EHOP数据集时，研究者需确保Python版本≥3.10，并通过`pip install -r requirements.txt`安装依赖包。实验通过命令行运行，指定问题类型、模型和子数据集即可启动。例如，运行GPT-4o在背包问题的困难数据集上的实验，需执行`python main.py configs/knapsack/gpt-hard.jsonnet`。对于Llama模型，需提前下载模型并配置路径。为避免结果文件冲突，建议按顺序运行实验，并妥善管理结果文件。此外，研究者可通过自定义`.jsonnet`文件和`generator.py`脚本，灵活调整实验配置和生成新的问题实例。

背景与挑战

背景概述

EHOP数据集聚焦于日常生活中的NP难优化问题，旨在为研究者提供一个涵盖多种经典优化问题的实验平台。该数据集由Saarland大学的研究团队于近期创建，主要研究人员包括计算机科学领域的专家。数据集的核心研究问题在于如何通过生成多样化的优化问题实例，评估不同求解器（如基于大语言模型和符号求解器）的性能。EHOP数据集的推出，为优化算法研究提供了新的实验基准，推动了该领域在理论与实践中的进一步发展。

当前挑战

EHOP数据集面临的挑战主要体现在两个方面。首先，在解决领域问题上，NP难优化问题本身具有极高的计算复杂度，如何设计高效的求解器以应对大规模问题实例是一个关键挑战。其次，在数据集构建过程中，生成具有代表性的问题实例（如随机实例和困难实例）需要平衡问题的多样性与复杂性，这对数据生成算法提出了较高要求。此外，如何确保不同求解器在相同问题实例上的公平比较，也是实验设计中的一大难点。

常用场景

经典使用场景

EHOP数据集广泛应用于解决日常生活中的NP难优化问题，如旅行商问题、背包问题和图着色问题。这些问题的复杂性使得它们在计算机科学和运筹学领域具有重要的研究价值。通过提供标准化的数据集和实验框架，EHOP为研究人员提供了一个统一的平台，用于评估和比较不同优化算法的性能。

实际应用

在实际应用中，EHOP数据集被广泛用于物流规划、资源分配和网络优化等领域。例如，在物流规划中，旅行商问题的解决方案可以帮助企业优化配送路线，降低运输成本。在资源分配中，背包问题的解决方案可以用于最大化资源利用率。这些应用展示了EHOP数据集在解决现实世界复杂问题中的巨大潜力。

衍生相关工作

EHOP数据集衍生了许多经典的研究工作，特别是在基于大语言模型（LLM）和符号求解器的优化算法领域。例如，研究人员利用EHOP数据集开发了基于GPT和Llama模型的优化算法，这些算法在解决复杂优化问题时表现出色。此外，EHOP还为其他相关领域的研究提供了数据支持，如自动推理和智能决策系统。