CODEWITHSUNDEEP
optimizationmathematical-optimization
r3nw0rp
r3nw0rp

Reputation: 71

Optimization - choosing subset of sets which minimises the cost

What would be an efficient way to solve such a problem:

We have many possible entities (for example: products, medical tests). The entities are offered in packages, buying item A, B,C in a package costs less than buying them separately (items might or might not be sold separately, if they are they have some price). We are interested only in a couple of items and we want to find what is the best combination of single products and/or packages of products to buy all our required items for a minimal cost (we don't really care if we buy any products not from our list or not, they have zero value to us). The content of packages can overlap (for example item A can be offered in several different packages and could be also offered on its own).

The most native way would be to compute a power set (all possible subsets) but this doesn't allow the solution to scale well.

What would be an efficient exact or approximate/heuristic solution?

Upvotes: 0

Views: 327

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

You can do this in an optimization model.

Say we have as input data:

----     14 SET c  items+combos

c1,    c2,    c3,    A ,    B ,    C 


----     14 SET i  single items

A,    B,    C


----     14 PARAMETER p  prices

c1 30,    c2 18,    c3 18,    A  10,    B  12,    C  15


----     14 PARAMETER cc  combo content

             A           B           C

c1           1           1           1
c2           1           1
c3           2
A            1
B                        1
C                                    1


----     14 PARAMETER demand  items needed

A 7,    B 4,    C 3

Now we solve the simple mixed integer programming (MIP) model:

enter image description here

The results look like:

----     36 VARIABLE buy.L  items+combos to buy

c1 3,    c2 1,    c3 1,    A  1


----     36 VARIABLE cost.L                =      136.000

In some cases we will buy more than needed (if the discounts are high enough). If you have some value for items bought exceeding the demand then the model becomes a little bit more complicated.

Both high-performance commercial and open source MIP solvers are readily available. They will solve models of this type to global optimality very efficiently (even for larger data sets with many items and many combos). Compared to your "powerset" algorithm, to me this approach looks much more attractive. MIP solvers are not approximations, but they typically only need to explore a very small fraction of all possible feasible integer solutions.

Upvotes: 1

Related Questions