Approximating Solutions to the Knapsack Problem using the Lagrangian
  Dual Framework
Mitchell Keegan Mahdi Abolghasemi
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.