Algorithm for choosing products for a given set of features at minimum cost?

Question

I have a list of products and a list of features. Each product has its own cost and delivers its own subset of the features.

I would like an algorithm such that I tell it which of the features I require and it will tell me the set of products I need to buy to get all of those features at the lowest total combined cost.

Does anyone have a recipe for doing something like that? I'd like to have it in JavaScript.

Answer 1

This is the (weighted) set cover problem. The easiest, surprisingly effective way to optimize instances that can't be brute forced is to run an integer program solver. For example, Iain Dunning has written one called SimplexJS in JavaScript. (The basic functionality seems to be there, but there are no frills (e.g., a presolver, cutting planes, or sparse linear algebra), and the apparent lack of license or documentation might not be to your liking. I'm sure that there are alternatives.)

The Wikipedia link above presents an abstract formulation of set cover. More concretely, let's suppose there are products A, B, C, D, where the relevant feature sets and prices are

A: {1, 2, 3}, 9.99
B: {2, 4}, 7.99
C: {3, 4}, 6.99
D: {4, 5}, 8.99 .

We make binary variables xA, xB, xC, xD, one for each product. The variable xA is 1 if we buy A, and 0 if we don't. Our objective is

minimize 9.99 xA + 7.99 xB + 6.99 xC + 8.99 xD .

For every feature, we have a constraint requiring us to buy a product with the feature.

1: xA >= 1
2: xA + xB >= 1
3: xA + xC >= 1
4: xB + xC + xD >= 1
5: xD >= 1

Given a suitable library, you just have to write code to translate the instance into a program like this and call the solver.

If you need to roll your own library for whatever reason, you're going to have to learn about branch and bound and the (dual) simplex method. The best search strategy for solving to optimality is depth-first search with best-first backtracking. The end product will be a few hundred lines of fairly intricate code.