用张量网络生成优化求解背包问题，效果媲美传统方法。
Generative-enhanced optimization for knapsack problems: an industry-relevant study
- 用张量网络生成满足约束的可行解，提升求解效率。
- 在60个实例上表现与模拟退火相当，解质量稳定。
- 适合工业场景中需快速求解复杂约束优化的用户。
优化在物流、航空、制造、化工、医药和保险等行业中至关重要，最优解可带来显著成本节约与效率提升。近年来，张量网络（TN）因其类量子建模能力受到关注。最近提出的张量网络生成增强优化（TN-GEO）利用生成建模高效采样满足约束的可行解。对称张量网络（STN）可编码特定优化约束，有助于求解过程。本文研究了TN与STN-GEO在多背包问题中的适用性，该问题要求每个物品分配至可用背包。我们为从业者提供具体使用指南，并分析其缩放行为与超参数依赖性。在60个不同问题实例上进行基准测试，结果表明TN-GEO与STN-GEO的解质量与模拟退火相当。
原文摘要 · Abstract (English)
Optimization is a crucial task in various industries such as logistics, aviation, manufacturing, chemical, pharmaceutical, and insurance, where finding the best solution to a problem can result in significant cost savings and increased efficiency. Tensor networks (TNs) have gained prominence in recent years in modeling classical systems with quantum-inspired approaches. More recently, TN generative-enhanced optimization (TN-GEO) has been proposed as a strategy which uses generative modeling to efficiently sample valid solutions with respect to certain constraints of optimization problems. Moreover, it has been shown that symmetric TNs (STNs) can encode certain constraints of optimization problems, thus aiding in their solution process. In this work, we investigate the applicability of TN- and STN-GEO to an industry relevant problem class, a multi-knapsack problem, in which each object must be assigned to an available knapsack. We detail a prescription for practitioners to use the TN-and STN-GEO methodology and study its scaling behavior and dependence on its hyper-parameters. We benchmark 60 different problem instances and find that TN-GEO and STN-GEO produce results of similar quality to simulated annealing.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。