Shopping basket discounts

PhilipElson · #1 (**permalink**) 05-03-08, 13:17

Yes yes, this topic has been covered several times. But really they have been simple % reductions or actual £ reductions. I am talking about multi-buy reductions (buy one get one free), and about collective items (buy these trousers worth £10 and this jacket worth £15 for £20).

So, this is my database setup:
- Products define the RRP, and supplier
- Products_sub defines the colour, size & barcode

- Basket defines the time of beginning a sale (and when it is complete if it gets completed)
- Basket_sub defines the items in the basket along with their quantity, and price at which the item is being sold (not same as RRP or discount price as this could be manually over-ridden for courtesy of a customer i.e round down that £100.15 bill to £100)

- Discount defines a discount which stores the type of discount and the value of the discount (discount type 1 for example reduces the price by Discount.value whereas discount type 3 reduces the price by % of Discount.value)
- Discount_sub defines what items are in the discount

NOTE: this setup, by design, means that we can have various discounts for one particular item, however only one discount per item per sale.

The problem therefore is figuring out, using SQL, the way to find the combination of discounts in a basket which generate the lowest total

By hand this is a ball-ache in itself!

I include the structure and some mock data from the database

Code:

--
-- Table structure for table `basket`
--

CREATE TABLE IF NOT EXISTS `basket` (
  `BasketID` mediumint(9) NOT NULL auto_increment,
  `Expiry` timestamp NOT NULL default CURRENT_TIMESTAMP on update CURRENT_TIMESTAMP,
  `UserID` mediumint(9) NOT NULL default '1',
  `Completed` tinyint(1) NOT NULL default '0',
  PRIMARY KEY  (`BasketID`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=27 ;

--
-- Dumping data for table `basket`
--

INSERT INTO `basket` (`BasketID`, `Expiry`, `UserID`, `Completed`) VALUES
(2, '2007-10-07 00:00:42', 0, 0),
(3, '2007-10-07 00:00:08', 0, 0);

-- --------------------------------------------------------

--
-- Table structure for table `basket_sub`
--

CREATE TABLE IF NOT EXISTS `basket_sub` (
  `BasketItemID` mediumint(9) NOT NULL auto_increment,
  `BasketID` mediumint(9) NOT NULL default '0',
  `ItemID` mediumint(9) NOT NULL default '0',
  `Qty` smallint(6) NOT NULL default '1',
  `UnitPrice` decimal(10,2) NOT NULL default '0.00',
  PRIMARY KEY  (`BasketItemID`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=54 ;

--
-- Dumping data for table `basket_sub`
--

INSERT INTO `basket_sub` (`BasketItemID`, `BasketID`, `ItemID`, `Qty`, `UnitPrice`) VALUES
(3, 2, 4, 21, '0.00'),
(4, 2, 3, 7, '0.00'),
(5, 2, 1, -2, '0.00'),
(51, 2, 5, 1, '0.00'),
(52, 3, 2, 1, '0.00'),
(53, 3, 5, 1, '0.00');

-- --------------------------------------------------------

--
-- Table structure for table `discounts`
--

CREATE TABLE IF NOT EXISTS `discounts` (
  `DiscountID` smallint(6) NOT NULL auto_increment,
  `DiscountName` text NOT NULL,
  `DiscountType` smallint(6) NOT NULL COMMENT 'EXPLAIN HERE THE TYPES, ALSO EXPLAIN IN LOGIC',
  `DiscountValue` mediumint(9) NOT NULL,
  PRIMARY KEY  (`DiscountID`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=4 ;

--
-- Dumping data for table `discounts`
--

INSERT INTO `discounts` (`DiscountID`, `DiscountName`, `DiscountType`, `DiscountValue`) VALUES
(1, 'Reduce price by 15', 1, 15),
(2, 'Multibuy, when a customer gets this dicount they pay 20 instead of the RRP', 2, 20),
(3, 'Half price sale (ie percentage discount)', 3, 50);

-- --------------------------------------------------------

--
-- Table structure for table `discounts_sub`
--

CREATE TABLE IF NOT EXISTS `discounts_sub` (
  `DiscountID` smallint(6) NOT NULL,
  `ItemID` bigint(20) NOT NULL
) ENGINE=MyISAM DEFAULT CHARSET=latin1;

--
-- Dumping data for table `discounts_sub`
--

INSERT INTO `discounts_sub` (`DiscountID`, `ItemID`) VALUES
(1, 3),
(2, 2),
(2, 5),
(3, 3);

-- --------------------------------------------------------

--
-- Table structure for table `products`
--

CREATE TABLE IF NOT EXISTS `products` (
  `ProductID` mediumint(9) NOT NULL auto_increment,
  `Added` timestamp NOT NULL default CURRENT_TIMESTAMP on update CURRENT_TIMESTAMP,
  `Updated` timestamp NOT NULL default '0000-00-00 00:00:00',
  `Heading` text NOT NULL,
  `Description` text NOT NULL,
  `Price` bigint(20) NOT NULL,
  PRIMARY KEY  (`ProductID`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=4 ;

--
-- Dumping data for table `products`
--

INSERT INTO `products` (`ProductID`, `Added`, `Updated`, `Heading`, `Description`, `Price`) VALUES
(1, '2008-05-03 19:09:37', '2007-10-10 16:51:07', 'Dinner Jacket', 'asd', 100),
(2, '2008-05-02 19:54:12', '2007-10-08 13:00:08', 'Horrible Coat', 'Horrible coat, you really wouldn''t like to buy....\nOr would you?\n\n\n\n\n\n\n\n\n\n\n', 500),
(3, '2008-05-03 19:09:45', '2007-10-08 12:49:55', 'Xmas Socks', 'We have ample of these just after Xmas time.', 50);

-- --------------------------------------------------------

--
-- Table structure for table `products_sub`
--

CREATE TABLE IF NOT EXISTS `products_sub` (
  `ItemID` bigint(20) NOT NULL auto_increment,
  `ProductID` mediumint(9) NOT NULL,
  `Detail1` text NOT NULL,
  `Detail2` text,
  PRIMARY KEY  (`ItemID`)
) ENGINE=MyISAM  DEFAULT CHARSET=latin1 AUTO_INCREMENT=6 ;

--
-- Dumping data for table `products_sub`
--

INSERT INTO `products_sub` (`ItemID`, `ProductID`, `Detail1`, `Detail2`) VALUES
(1, 1, 'Small', NULL),
(2, 1, 'Large', NULL),
(3, 2, 'Pink', 'Small'),
(4, 2, 'Black', 'Large'),
(5, 2, 'Horrendous', 'Need to get rid of');

My logic so far has eluded me, here is the query that I am trying at the moment, although this gets me nowhere near where I need to be.

Code:

SELECT basket.BasketID, discounts.DiscountID, basket_sub.BasketItemID, basket_sub.ItemID,
(CASE discounts.DiscountType
WHEN 2 THEN 
IF((SELECT COUNT(DISTINCT a1.ItemID) FROM discounts_sub a1
	LEFT JOIN basket_sub a2 ON a2.ItemID = a1.ItemID
	LEFT JOIN basket a3 ON a2.BasketID = a3.BasketID
	WHERE basket.BasketID=a2.BasketID AND discounts_sub.DiscountID=a1.DiscountID
)
=(SELECT COUNT(DISTINCT a1.ItemID) FROM discounts_sub a1 WHERE discounts_sub.DiscountID=a1.DiscountID),IF(products_sub.ItemID=(SELECT DISTINCT a1.ItemID FROM discounts_sub a1 WHERE discounts_sub.DiscountID=a1.DiscountID limit 1),discounts.DiscountValue,products.Price),products.Price)

WHEN 1 THEN products.Price- discounts.DiscountValue
WHEN 3 THEN products.Price/100 * (100-discounts.DiscountValue)
ELSE '-'
END
)
AS Price,
discounts.DiscountID FROM basket_sub
LEFT JOIN products_sub ON basket_sub.ItemID = products_sub.ItemID
LEFT JOIN products ON products_sub.ProductID = products.ProductID
LEFT JOIN basket ON basket_sub.BasketID = basket.BasketID
LEFT JOIN discounts_sub ON basket_sub.ItemID = discounts_sub.ItemID
LEFT JOIN discounts ON discounts.DiscountID = discounts_sub.DiscountID
WHERE basket.BasketID=2

Basically what I am trying to achieve with discount type 2 is to look through the discounts_sub check that all the products in there are in the basket, calculate the discount (ok that bit is done)...
THEN
Compare with other combinations of discounts to give the overall cheapest total to the basket

Sorry this post is so long...
This is my first post & I'm self taught so go easy on the jargon please.

Thanks in advance

sco08y · #2 (**permalink**) 05-03-08, 17:24

Let me see if I'm understanding the problem here:

1. Your input is a basket with a bag (i.e. a multiset) of items.
2. You can substitute coupons for certain combinations of items.
3. Further stipulate that for items that lack a coupon, we can assume that there is an identity coupon that is simply 1 of that item and costs the same.
4. From 2 and 3, we conclude that there exists at least one bag of coupons that is equivalent to any bag of items.
5. Thus a possible "deal" is the bag of coupons that is equivalent to the original basket.
6. We are trying to find the deal that has the lowest total price.

sco08y · #3 (**permalink**) 05-03-08, 17:51

Okay, add some further assumptions: 1. a basket is not going to be incredibly huge, 2. there will generally be only a handful of coupons that actually apply.

sco08y · #4 (**permalink**) 05-03-08, 18:39

The exhaustive search is going to list every possible coupon that applies and how many times it could possibly apply. So say our basket is: 4 apples, 4 bananas and 4 oranges. And we have these coupons: A: 2 apples, save $1. B: 2 bananas, save $2. C: 1 apple, 1 banana, 1 orange, save $2.50.

The possibilities are:

Code:

A  B  C  Savings
0  0  0  0
0  0  1  2.5
0  0  2  5
0  0  3  7.5
0  0  4  10
0  1  0  2
0  1  1  4.5
0  1  2  7
0  2  0  4
1  0  0  1
1  0  1  3.5
1  0  2  6
1  1  0  3
1  1  1  5.5
1  1  2  8
1  2  0  5
2  0  0  2
2  1  0  4
2  2  0  6

That would get ugly, and it's unnecessarily complex given that in most cases coupons don't conflict with each other.

Another method would be the greedy search...

sco08y · #5 (**permalink**) 05-03-08, 19:20

Here's a simple greedy algorithm in Perl. You can adjust how hard it looks by setting the global variable $prune. In general, though, it finds the best deal every time I've tried it with $prune at 1.

Now, if you set $prune to 1, the algorithm becomes iterative. So you can do that in SQL, using a stored procedure. But it doesn't *guarantee* the best discount, it's a heuristic that assumes grabbing the biggest discount in each iteration is the best strategy.

If you set $prune high enough, it becomes an exhaustive depth-first search, and it will take forever for a reasonably large cart.

Code:

use strict;

my %items = (apple => 2, banana =>3, orange=>2.5, cereal=>4, milk=>3, cheese=>3.5, candy=>2);

my @coupons = ({apple => 2, save=>1}, {banana=>2, save=>1}, {milk=>3, save=>3}, 
	{apple=>1, banana=>1, orange=>1, save=>2.5});

@coupons = sort { $b->{save} <=> $a->{save} } @coupons;

my(%basket);
$basket{$_} = int(rand() * 10) for keys %items;

our $prune;

sub greedy {
	my(%basket) = %{$_[0]};
	my(%deal) = $_[1] ? %{$_[1]} : map(($_, 0), 0..$#coupons);
	print "--greedy starts--\n";
	print "Current deal:\n";
	print "  Coupon $_ x $deal{$_}\n" for sort keys %deal;
	print "Current basket:\n";
	print "  $_ x $basket{$_}\n" for sort keys %basket;
	
	my @tries;
	coupon: for my $cn (0..$#coupons) {
		my $c = $coupons[$cn];
		for my $i (keys %$c) {
			next if $i eq "save";
			next coupon unless exists $basket{$i} && $basket{$i} >= $c->{$i};
		}
		push @tries, $cn;
	}
	print "Coupons to pick from: ".scalar(@tries)."\n";	
	my(@deals) = (\%deal);
	# Prune most of the searching...
	@tries = @tries[0..($prune-1)] if @tries > $prune;
	for my $t (@tries) {
		my(%testdeal) = (%deal);
		$testdeal{$t}++;
		my $c2 = $coupons[$t];
		my(%testbasket) = (%basket);
		for my $i (keys %$c2) {
			next if $i eq "save";
			$testbasket{$i} -= $c2->{$i};
		}
		push @deals, greedy(\%testbasket, \%testdeal);
	}
	# Figure out which deal saved the most.
	my @saves;
	for my $d (@deals) {
		my $s = 0;
		for my $c3 (keys %$d) {
			$s += $coupons[$c3]->{save} * $d->{$c3};
		}
		push @saves, $s;
	}
	my @order = sort { $saves[$b] <=> $saves[$a] } 0..$#saves;
	print "best savings so far: $saves[$order[0]]\n";
	print "--greedy ends --\n";
	return $deals[$order[0]];
}

my $s = 0;
$prune = 2;
my $deal1 = greedy(\%basket);
$prune = 1;
my $deal2 = greedy(\%basket);
print "First deal found (prune 2):\n";
my $c;
for $c (sort keys %$deal1) {
	print "  Coupon $c x $deal1->{$c}\n";
	$s += $coupons[$c]->{save} * $deal1->{$c};
}
print "Saved $s\n";
print "Second deal found (prune 1):\n";
$s = 0;
for $c (sort keys %$deal2) {
	print "  Coupon $c x $deal2->{$c}\n";
	$s += $coupons[$c]->{save} * $deal2->{$c};
}
print "Saved $s\n";
print "Done!";

PhilipElson · #6 (**permalink**) 05-04-08, 05:50

Thanks so much for your effort sco08y, the basic message that I got from your answer is that the discount structure that I have at the moment is good until I allow multi-buys of different items, i.e. 1 banana and 1 orange saves $1.

Personally would you alter the database structure in anyway?

Here is a list of discounts that I might like to implement in the future:
- Buy one apple get one free
- Buy one pear get a banana half price
- Buy one peach at 25% discount
- Buy one plum and save $1
- Buy one coconut and one lemon for $5

Out of interest is it possible to make SQL (in this case MySQL) return all the permutations of discounts (I know that this exhaustive search is not a good method, and I don't plan to use it...just out of interest)?

For any newbies like me who didn't understand exhaustive & greedy searches:
http://forge.mysql.com/wiki/How_does...austive_search

So now the hard part for me, how to I try a heuristic greedy search in MySQL?
Or does it require that I use perl (actually I would try to use python, since that is what I am using in this project)?

By the way your script was brilliant...I have spent about 10 minutes just hitting return to see if the prune level 1 is always good enough. It was when I kept

Code:

int(rand() * 10)

but when I kicked it up to * 20 it regularly missed the spot (this is quite understandable considering the number of possible permutations)

sco08y · #7 (**permalink**) 05-10-08, 23:56

Quote:

Originally Posted by PhilipElson

Thanks so much for your effort sco08y, the basic message that I got from your answer is that the discount structure that I have at the moment is good until I allow multi-buys of different items, i.e. 1 banana and 1 orange saves $1.

Yes, that introduces pretty much all the complexity.

Quote:

Personally would you alter the database structure in anyway?

Here is a list of discounts that I might like to implement in the future:
- Buy one apple get one free
- Buy one pear get a banana half price
- Buy one peach at 25% discount
- Buy one plum and save $1
- Buy one coconut and one lemon for $5

My main issue is this: the simplest way to represent a coupon is basically "a list of items, how much you save." And that works unless you have something like "buy one x, get one x free" which is dependent on the price of x.

The nice thing about SQL, though, is you can have three different tables representing different types of coupons and one stored query that gloms it all together into a single format. So, definitely, offload that complexity to the DBMS where it belongs.

Honestly, I can't see anything wrong with your database structure. I don't use surrogate keys as much, but that's a preference more than anything.

Quote:

Out of interest is it possible to make SQL (in this case MySQL) return all the permutations of discounts (I know that this exhaustive search is not a good method, and I don't plan to use it...just out of interest)?

Multi-dimensional stuff like permutations is tricky to do in SQL because it either involves recursion or iteration to handle it. So, in a simple query, probably not. In a stored procedure, sure.

Quote:

So now the hard part for me, how to I try a heuristic greedy search in MySQL?
Or does it require that I use perl (actually I would try to use python, since that is what I am using in this project)?

Python would be fine for this algorithm. I think perl and python tend to solve the same or similar problems, which is why I haven't bothered to learn python. If you're fairly familiar with Python, I'll bet you could translate the code.

You could do a version in SQL because SQL is actually far better at manipulating these sorts of data structures. However, I'm skeptical of how well most DBMSs handle recursion. If you set prune to 1, you can rewrite the algorithm as a loop.

Quote:

By the way your script was brilliant...I have spent about 10 minutes just hitting return to see if the prune level 1 is always good enough. It was when I kept

Code:

int(rand() * 10)

but when I kicked it up to * 20 it regularly missed the spot (this is quite understandable considering the number of possible permutations)

Thanks... it was definitely one of those things where I thought "Christ, I've already spent thirty minutes on this post, why not thirty more?!"

PhilipElson · #8 (**permalink**) 05-11-08, 03:13

Sco08y your help has been superb, I really appreciate you spending that much time on my post! I will post my solution when I get one.

Regards
Phil Elson

Internet Services

Web Development

Digital Marketing

Consumer Tech