# What is the correct formulation of this "shopping bag" optimization problem, and how can I solve it efficiently?

I'm looking at finding a solution to the following problem, but I'm having trouble formulating it sensibly, and then finding an appropriate algorithm to solve it.

Consider a list of items placed in a shopping bag: 1, 2, 3, 4...

Each item can be part of one or more promotions: A, B, C, D

We wish to apply the set of promotions such that we maximise the value of the discount, that no item is allowed to participate in more than one promotion, but each promotion could be applied more than once.

Promotions can be defined in a number of ways, but for now I'm just considering a type of 'Buy 2 qualifying items, save X', I'm hopeful I'll be able to generalise from here.

My example would be:

• Promotion A - Buy 2 Save 8
• Promotion B - Buy 2 Save 10
• Promotion C - Buy 2 Save 6

• Item 1 - Eligible for A, B

• Item 2 - Eligible for B
• Item 3 - Eligible for A, C
• Item 4 - Eligible for B, C

It's quite easy to see here that the correct application of promotions is A to Item 1, 3 and B to 2, 4. This gives a total discount of 18.

In a larger case it becomes difficult, hence needing to solve algorithmically.

I've tried the following:

1. List all the possible combinations of Promotions we could apply.
2. Discard any that are obviously poor (e.g. a direct copy of a promotion with a higher value).
3. Apply any that have no overlap with other promotions (e.g. If Item 1 and 2 are only valid for promotion A, then apply that promotion).
4. Take the remaining set and attempt a branch-and-bound type search on the results.

However, this can take a long time (for large sets with similar discounts).

I feel this is a type of Knapsack or Assignment problem, but I can't write it sensibly. Without being able to write it sensibly I can't solve it.

Is this a recognised variant of a problem? Any help attacking it would be greatly appreciated, especially with psuedo-code to help solve it

• The data can be expressed as a bipartite graph. If each promotion could be applied at most once, then it would be a maximum weight bipartite graph matching problem, which is very well understood. So what you want, I think, is a relaxed form of that problem. This might help you find something in the literature. Commented Mar 8, 2013 at 0:55
• So if for now we assume that each promotion could only be applied once, how would you form the graph? I've tried a couple of ways but can't see how you'd maintain the constraint to only allow a Promotion to be applied if it was considered valid. Commented Mar 8, 2013 at 13:21
• You could form this problem as an 0-1 Integer Program, then use either an open source or commercial solver to tackle the larger versions of it. Commented Mar 9, 2013 at 15:10
• @James Osborn: Consider a bipartite graph where there is an edge between every promotion and every item. If it's valid to apply that promotion to that item, the weight on the edge is the "gain". Otherwise, the weight on the edge is zero. Then, you find a maximum weight match, and discard any edges with weight zero. Basically, you let the match happen, but make it clear to the optimisation algorithm that you don't gain anything by it. Commented Mar 11, 2013 at 4:38
• Just a quick update, thanks for the help so far. I've not had much of a chance to look at the solutions yet, but it's given me some good places to look. Commented Mar 13, 2013 at 8:51