# Neural Knapsack

Hi,

I am working on a problem which is similar to Knapsack problem. I am trying to solve this using neural networks.

As per the problem statement, I have large number of products for multiple countries. Revenue numbers for these products in each country is shared with us. Task is to select top 10% of products for each country as per revenue. (There is a further constraint but I will explain it if I can resolve this simple problem using NN first). Product count varies across countries i.e Country 1 may have 500 products, Country 2 may have 300 products etc. Therefore, top 50 products have to be selected for country 1 and top 30 products have to be selected for country 2.
To me each country is a seperate knapsack problem and can be solved independently. Hence I consider data for each country as single sample for NN.

To solve this through neural network I have tried using both supervised and unsupervised approach. Strictly speaking this will be a unsupervised approach as we may not have actual optimal solution already. But since this is exploration of NN capability, I do have optimal solution already.

To solve this using NN supervised way: I have started with assumption that maximum products for any country can be only X ex 800.

Therefore Input layer of Network will have fixed neurons.

I have given 2 things as input for each sample:

Revenue of each product for a country. If country 1 has 500 products then input will be 500 columns of revenue and since expected input is 800 then rest 300 neurons will get zero as value.
Capacity (Capacity being maximum SKUs that can get selected). So for country 1 this value will be 50.
In net, input layer has count of neurons equal to = max product count + 1 neuron for Capacity.

This is followed by couple of hidden layers with relu activation and finally output layer with sigmoid funnction.

Output layer has max count of products as neurons i.e. 800. If output has value near 1, then that product is selected else it is not selected.

I have tried couple of iterations but NN does not learn Knapsack solution at all.

Capacity constraint is not at considered across countries. i.e in output across countries same count of products get selected.
Also same neurons of output layer have value near 1 for all rows.

Ideally in output for each country, count of selected products should vary based on capacity input and most certainly different products (i.e output neurons) should get select. Neither of this is happening.

Can anyone suggest how I should structure my input and output for this problem? How capacity should be given as input?
The difference between this problem structure and perhaps doing classification on numeric data is that input neuron 1 , neuron 2 etc are not fixed features i.e. best product can be anywhere amongst the input neurons across countries. Therefore, even standarizing columns do not make sense. I did standarize rows though, but that did not work either.

I have taken guidance from this solution https://gist.github.com/shshemi/a16893b885bb2b31da9c9839619e5a65 but it does not work for my problem statement.