# Approximating Solutions to the Knapsack Problem using the Lagrangian Dual Framework

arXiv: https://arxiv.org/abs/2312.03413 · HTML: https://mlsanity.com/paper/2312.03413/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 18 references that are in the map.
- First posted on arXiv 6 Dec 2023.

## Builds on (most cited first, 12 of 12)

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Training Spiking Neural Networks Using Lessons From Deep Learning](https://mlsanity.com/paper/2109.12894/) (2021)
- [DC3: A learning method for optimization with hard constraints](https://mlsanity.com/paper/2104.12225/) (2021)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Predicting AC Optimal Power Flows: Combining Deep Learning and Lagrangian Dual Methods](https://mlsanity.com/paper/1909.10461/) (2019)
- [Lagrangian Duality for Constrained Deep Learning](https://mlsanity.com/paper/2001.09394/) (2020)
- [Learning Hard Optimization Problems: A Data Generation Perspective](https://mlsanity.com/paper/2106.02601/) (2021)
- [Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method](https://mlsanity.com/paper/2110.06365/) (2021)
- [Teaching the Old Dog New Tricks: Supervised Learning with Constraints](https://mlsanity.com/paper/2002.10766/) (2020)
- [Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size](https://mlsanity.com/paper/2005.14105/) (2020)
- [State-of-the-art predictive and prescriptive analytics for IEEE CIS 3rd Technical Challenge](https://mlsanity.com/paper/2112.03595/) (2021)
- [How to effectively use machine learning models to predict the solutions for optimization problems: lessons from loss function](https://mlsanity.com/paper/2105.06618/) (2021)

## Abstract (arXiv)

The Knapsack Problem is a classic problem in combinatorial optimisation. Solving these problems may be computationally expensive. Recent years have seen a growing interest in the use of deep learning methods to approximate the solutions to such problems. A core problem is how to enforce or encourage constraint satisfaction in predicted solutions. A promising approach for predicting solutions to constrained optimisation problems is the Lagrangian Dual Framework which builds on the method of Lagrangian Relaxation. In this paper we develop neural network models to approximate Knapsack Problem solutions using the Lagrangian Dual Framework while improving constraint satisfaction. We explore the problems of output interpretation and model selection within this context. Experimental results show strong constraint satisfaction with a minor reduction of optimality as compared to a baseline neural network which does not explicitly model the constraints.