Generative-enhanced optimization for knapsack problems: an industry-relevant study
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910818653700096 |
|---|---|
| author | Vodovozova, Yelyzaveta Awasthi, Abhishek Jones, Caitlin Doetsch, Joseph Wintersperger, Karen Krellner, Florian Riofrío, Carlos A. |
| author_facet | Vodovozova, Yelyzaveta Awasthi, Abhishek Jones, Caitlin Doetsch, Joseph Wintersperger, Karen Krellner, Florian Riofrío, Carlos A. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_04928 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Generative-enhanced optimization for knapsack problems: an industry-relevant study Vodovozova, Yelyzaveta Awasthi, Abhishek Jones, Caitlin Doetsch, Joseph Wintersperger, Karen Krellner, Florian Riofrío, Carlos A. Machine Learning Quantum Physics 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. |
| title | Generative-enhanced optimization for knapsack problems: an industry-relevant study |
| topic | Machine Learning Quantum Physics |
| url | https://arxiv.org/abs/2502.04928 |