8
$\begingroup$

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

Improve this question
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Pseudonym Mar 8 '13 at 0:55
  • $\begingroup$ 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. $\endgroup$ – James Osborn Mar 8 '13 at 13:21
  • $\begingroup$ 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. $\endgroup$ – Aron Ahmadia Mar 9 '13 at 15:10
  • 1
    $\begingroup$ @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. $\endgroup$ – Pseudonym Mar 11 '13 at 4:38
  • $\begingroup$ 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. $\endgroup$ – James Osborn Mar 13 '13 at 8:51
1
$\begingroup$

It would seem like you'd want to take advantage of the structure of the problem that items can only be used toward one promotion. That means that if you've found a solution that uses as many promotions as possible, the only way to do better is to find another solution which takes one or more promotions plus the unassigned items and swaps them with another set of promotions and unused items of higher value.

For example, you might start the previous example with (1,2) and (3,4), for 16. You could then check that (1,3) and (2,4) leads to 18, and the swap should be made.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.