I am trying to come up with a solution to the following to assist our sales guys with product selections;

We have various kits available, each kit has 4 numeric variables.

Different kits have different component quantities that cannot be changed,

ie. kit 1 might have 6A, 6B, 10C, 10D components, whilst kit 2 might have 2A, 2B, 5C, 5D there are many kits but the values of each of the 4 components cannot be changed, therefore the optimum selection of kits needs to be chosen.

If a customer requires 12A, 8B, 10C, 8D, it is clear from this example that we would need 1 x kit 1 and 1 x kit 2, it is acceptable to have too many of any components but not less than, we want to find the optimal combinations to find the most competitive solution.

I have been looking at knapsack code examples but these don't seem to fit my problem as they are looking at a single requirement result, i.e max size not 4 results in my case where each of the 4 requirements must be met.

I would appreciate if any one can give me a nudge in the right direction. Perhaps a code example to get me going.

Many thanks.

# kit Combination Calculator

Page 1 of 1## 9 Replies - 980 Views - Last Post: 19 January 2018 - 11:23 AM

##
**Replies To:** kit Combination Calculator

### #2

## Re: kit Combination Calculator

Posted 18 January 2018 - 01:52 PM

Wouldn't it be a fairly straight forward search? Which kit has X, which has Y, which has W, then pull some snazzy SQL distinct to make that list the kits needed.

### #3

## Re: kit Combination Calculator

Posted 18 January 2018 - 01:54 PM

I am trying to come up with a solution to the following to assist our sales guys with product selections;

We have various kits available, each kit has 4 numeric variables.

Different kits have different component quantities that cannot be changed,

ie. kit 1 might have 6A, 6B, 10C, 10D components, whilst kit 2 might have 2A, 2B, 5C, 5D there are many kits but the values of each of the 4 components cannot be changed, therefore the optimum selection of kits needs to be chosen.

If a customer requires 8A, 6B, 11C, 8D, it is clear from this example that we would need 1 x kit 1 and 1 x kit 2, it is acceptable to have too many of any components but not less than, we want to find the optimal combinations to find the most competitive solution.

I have been looking at knapsack code examples but these don't seem to fit my problem as they are looking at a single requirement result, i.e max size not 4 results in my case where each of the 4 requirements must be met.

I would appreciate if any one can give me a nudge in the right direction. Perhaps a code example to get me going.

Many thanks.

We have various kits available, each kit has 4 numeric variables.

Different kits have different component quantities that cannot be changed,

ie. kit 1 might have 6A, 6B, 10C, 10D components, whilst kit 2 might have 2A, 2B, 5C, 5D there are many kits but the values of each of the 4 components cannot be changed, therefore the optimum selection of kits needs to be chosen.

If a customer requires 8A, 6B, 11C, 8D, it is clear from this example that we would need 1 x kit 1 and 1 x kit 2, it is acceptable to have too many of any components but not less than, we want to find the optimal combinations to find the most competitive solution.

I have been looking at knapsack code examples but these don't seem to fit my problem as they are looking at a single requirement result, i.e max size not 4 results in my case where each of the 4 requirements must be met.

I would appreciate if any one can give me a nudge in the right direction. Perhaps a code example to get me going.

Many thanks.

### #4

## Re: kit Combination Calculator

Posted 18 January 2018 - 02:02 PM

Thanks for your reply, but I don't think so although I have limited SQL knowledge, the requirement is likely to always require multiple kits and its about finding the best combinations;

Even if I just looked at the first component if the requirement was 50 and I have kits which comprise 10,5 or 2 then its clear I would need 5 x 10 kit or 20 x 5 kit or 25 x 2 kit, clearly the best selection would be 5 x 10, but the result may be different for the other 3 components which will then alter the first selection. and so the 20 x 5 might work better for the other components within the kit.

Even if I just looked at the first component if the requirement was 50 and I have kits which comprise 10,5 or 2 then its clear I would need 5 x 10 kit or 20 x 5 kit or 25 x 2 kit, clearly the best selection would be 5 x 10, but the result may be different for the other 3 components which will then alter the first selection. and so the 20 x 5 might work better for the other components within the kit.

### #5

## Re: kit Combination Calculator

Posted 18 January 2018 - 02:55 PM

Sounds more like a bin packing problem. Anyway, knapsack is a special case of bin packing.

There is nothing that says that the weights of the items in the knapsack are restricted to a single dimension. You could just as easily have a one dimensional weight or value, or have a 4 dimensional vector.

There is nothing that says that the weights of the items in the knapsack are restricted to a single dimension. You could just as easily have a one dimensional weight or value, or have a 4 dimensional vector.

### #6

## Re: kit Combination Calculator

Posted 18 January 2018 - 03:50 PM

Moving over into Computer Science this looks to be language agnostic...

### #7

## Re: kit Combination Calculator

Posted 18 January 2018 - 11:40 PM

Skydiver is correct- this is a generalization of the bin-packing or knapsack problems. Your problem is certainly NP-Hard. However, you can formulate this problem as an Integer Programming problem. Granted, IP is NP-Hard, there are sophisticated IP solvers that are pretty good in practice. They aren't always optimal, but it's good enough. Excel has one such solver.

First, denote [n] = { 1, 2, ..., n }. I will use this notation as shorthand. For each i \in [n], denote x

Now to discuss the constraints. For i \in [n] and j \in { A, B, C, D }, denote y

Note that x_{i} * y_{i_{j}} is the number of part j that the customer gets through kit i. We add this quantity up over all such kits.

We also have the constraints that each x_{i} >= 0 and each x_{i} is an integer. You will need to spell these out for an IP solver.

First, denote [n] = { 1, 2, ..., n }. I will use this notation as shorthand. For each i \in [n], denote x

_{i}as the number of kits of type i you are giving the customer. Now I imagine you want to minimize the number of kits you give to a customer. So our objective function is:min \sum_{i=1}^{n} x_{i}

Now to discuss the constraints. For i \in [n] and j \in { A, B, C, D }, denote y

_{ij}as the number of part j's in kit i. (So y_{1A}denotes the number of part A in kit 1). Denote q_{j}as the quantity of part j that the customer wants. This gives rise to the constraints:\sum_{i=1}^{n} y_{i_{j}} * x_{i} >= q_{j} (for all j)

Note that x_{i} * y_{i_{j}} is the number of part j that the customer gets through kit i. We add this quantity up over all such kits.

We also have the constraints that each x_{i} >= 0 and each x_{i} is an integer. You will need to spell these out for an IP solver.

### #8

## Re: kit Combination Calculator

Posted 19 January 2018 - 02:10 AM

Thankyou all for your guidance, i am struggling to find some code examples, all the bin packing and knapsack examples seem to result in less than, we need to meet or exceed the customers requirement for each component.

I appreciate the excel function but i want to write something in c# to add into our sales tool.

I appreciate the excel function but i want to write something in c# to add into our sales tool.

### #9

## Re: kit Combination Calculator

Posted 19 January 2018 - 10:50 AM

I would suggest searching for an LP/IP silver or library that you can use with C#. That is probably the easiest way.

Again, your problem is NP-Hard. You aren’t going to find easy, efficient, and plug-and-chug solutions. If you choose not to go the IP solver route, you will likely have to design an algorithm yourself. Dynamic programming will probably be the most effective technique to minimize the number of kits you have to provide, but a greedy approach will likely take the least amount of time for your computer to execute.

Again, your problem is NP-Hard. You aren’t going to find easy, efficient, and plug-and-chug solutions. If you choose not to go the IP solver route, you will likely have to design an algorithm yourself. Dynamic programming will probably be the most effective technique to minimize the number of kits you have to provide, but a greedy approach will likely take the least amount of time for your computer to execute.

### #10

## Re: kit Combination Calculator

Posted 19 January 2018 - 11:23 AM

... And if you are expecting to have your sales people run the kit solver on their phones, the greedy approach will likely work best for a quickie recommendation.

If you host the solver on your company website, then you can likely go with solutions that require more computing power. Perhaps, I'm geeky, but if I were your customer, I'd like to be able to plug my own values into your company web site and see what values come out. On the other hand, I know that my wife would rather just be presented with 2 or 3 options and she doesn't particularly care how the numbers were produced.

If you host the solver on your company website, then you can likely go with solutions that require more computing power. Perhaps, I'm geeky, but if I were your customer, I'd like to be able to plug my own values into your company web site and see what values come out. On the other hand, I know that my wife would rather just be presented with 2 or 3 options and she doesn't particularly care how the numbers were produced.

Page 1 of 1