Knapsack Problem

Knapsack Problem #

The Knapsack Problem is a classic optimization problem where items with weights and values must be selected to maximize total value while respecting a weight constraint.

Recent Literature #

1. A Novel Method to Solve Neural Knapsack Problems ICML, 2021. paper, code

   Li Duanshun and Liu Jing and Lee Dongeun and Seyedmazloom Ali and Kaushik Giridhar and Lee Kookjin and Park Noseong

2. DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization NeurIPS, 2023. paper, code

   Ye, Haoran and Wang, Jiarui and Cao, Zhiguang and Liang, Helan and Li, Yong

3. Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization NeurIPS, 2023. paper

   Grinsztajn, Nathan and Furelos-Blanco, Daniel and Surana, Shikha and Bonnet, Clément and Barrett, Thomas D

4. Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimization NeurIPS, 2023. paper, code

   Chen, Jinbiao and Wang, Jiahai and Zhang, Zizhen and Cao, Zhiguang and Ye, Te and Chen, Siyuan

5. BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization NeurIPS, 2023. paper, code

   Drakulic, Darko and Michel, Sofia and Mai, Florian and Sors, Arnaud and Andreoli, Jean-Marc

6. Neural Multi-Objective Combinatorial Optimization with Diversity Enhancement NeurIPS, 2023. paper, code

   Chen, Jinbiao and Zhang, Zizhen and Cao, Zhiguang and Wu, Yaoxin and Ma, Yining and Ye, Te and Wang, Jiahai

7. Rethinking Neural Multi-Objective Combinatorial Optimization via Neat Weight Embedding ICLR, 2025. paper

   Jinbiao Chen, Zhiguang Cao, Jiahai Wang, Yaoxin Wu, Hanzhang Qin, Zizhen Zhang, Yue-Jiao Gong

8. Approximation algorithms for combinatorial optimization with predictions ICLR, 2025. paper

   Antonios Antoniadis, Marek Elias, Adam Polak, Moritz Venzin