论文标题
基于包含的最大解决方案的0-1背包问题的功能
Features for the 0-1 knapsack problem based on inclusionwise maximal solutions
论文作者
论文摘要
几十年来，关于0-1背包问题的研究导致了非常有效的算法，这些算法能够迅速解决大型问题实例以达到最佳性。这促使研究人员还调查了是否存在相对较小的问题实例，这些实例是否对现有求解器很难，并研究了哪些特征是其硬度的特征。以前，作者提出了一类新的硬0-1背包问题实例，并证明了所谓的包容性最大解决方案（IMS）的性质可能是此类重要的硬度指标。在当前的论文中，我们制定了与任意0-1 knapsack问题实例有关的几个新的计算挑战性问题。基于先前工作的概括以及有关IMS的新结构结果，我们制定了用于解决这些问题的多项式和伪人类时间算法。由此，我们得出了一组14个计算昂贵的功能，我们在大约540个CPU小时内对超级计算机上的两个大数据集进行了计算。我们表明，所提出的功能包含与问题实例的经验硬度有关的重要信息，该信息通过训练机器学习模型从文献中缺少的问题中缺少，这些模型可以准确地预测各种0-1 knapsack问题实例的经验硬度。使用实例空间分析方法，我们还表明，硬0-1背包问题实例聚集在实例空间的相对密集区域周围，并且在实例空间的简单和硬部分中的几个功能都不同。
Decades of research on the 0-1 knapsack problem led to very efficient algorithms that are able to quickly solve large problem instances to optimality. This prompted researchers to also investigate whether relatively small problem instances exist that are hard for existing solvers and investigate which features characterize their hardness. Previously the authors proposed a new class of hard 0-1 knapsack problem instances and demonstrated that the properties of so-called inclusionwise maximal solutions (IMSs) can be important hardness indicators for this class. In the current paper, we formulate several new computationally challenging problems related to the IMSs of arbitrary 0-1 knapsack problem instances. Based on generalizations of previous work and new structural results about IMSs, we formulate polynomial and pseudopolynomial time algorithms for solving these problems. From this we derive a set of 14 computationally expensive features, which we calculate for two large datasets on a supercomputer in approximately 540 CPU-hours. We show that the proposed features contain important information related to the empirical hardness of a problem instance that was missing in earlier features from the literature by training machine learning models that can accurately predict the empirical hardness of a wide variety of 0-1 knapsack problem instances. Using the instance space analysis methodology, we also show that hard 0-1 knapsack problem instances are clustered together around a relatively dense region of the instance space and several features behave differently in the easy and hard parts of the instance space.
