Buying lots as an optimization problem

[jxu]

I've been thinking about buying many pieces for MOCs I want to make as cheaply as possible as a classic combinatorial optimization problem, like the kind done by businesses with operations research.

The cheapest approach is not to order individual pieces on-demand but to buy lots and lots in bulk (ex. 10 lb boxes on ebay) and maintain my own stockpile of pieces. But I don't have the time and money currently to maintain my own inventory. (I think every kid dreams of having a giant drawer warehouse of bricks like in https://www.youtube.com/watch?v=2xcGgfOVpPM)

I first thought about this problem when using Bricklink's wanted lists. By default, when clicking "Buy All", the site sorts by stores with unique lots. I think the reasoning is, if I am buying a decent number of lots and I can get it all from one store, then I will only pay for one store's S&H, which has a good chance of being cheaper than buying from two or more stores. Often this is not possible and I need to buy from two, three, four, or more stores. My approach was to buy using a greedy method for unique lots: try to have one store cover say 90% of lots, then have another one or two stores cover the remaining 10%. The idea here is to minimize the number of stores to buy from to minimize S&H costs. But I haven't actually done experiments to see if this is really a good method or not. It could very well be that buying roughly the same proportion of parts from multiple stores ends up cheaper.

Then I found about Bricklink's "Easy Buy" option. Whatever algorithm they use, it usually does a good job in keeping costs low while not buying from too many stores. Some BL stores don't list S&H which can drive up costs, especially for international orders. It doesn't consider Lego's own parts shop which I haven't gotten a chance to use. But it is a lot easier than manually trying combinations.

What really inspired me to think about this algorithmically is Rebrickable's Multi-Buy option. They give you more options to tune the algorithm by providing three starting points: cheapest stores, largest stores, and minimize delivery (you can put in an estimated average delivery cost). In my experience, minimize delivery (almost the same as minimizing number of stores) gives the best total prices. Unfortunately they don't have an option for setting two different delivery costs, one for domestic and one for international, since domestic costs are usually a lot lower. Although they both have access to BL seller data, BL's Easy Buy still seems to do a better job finding combinations.

I wonder if there are any other automatic tools to try to do this price optimization. As a Bricklink seller I have access to their API but I believe that is for my own store. These weighted set cover type problems are computationally hard but with a strict limit on the total number of stores then they become reasonable to solve fairly well (and the trivial O(n^k) solution for choosing k stores from n total). Here's a CS paper on these kinds of problems if you are interested: https://people.cs.umass.edu/~barna/paper/ICDE15_research_131.pdf (I wouldn't have spent so much time thinking about this if Legos weren't so frickin expensive!)

 

 

[jimmynick]

I suppose it was inevitable someone would bring this up! Sometimes I think about the issue of optimizing the purchase of lots on BL and you’re right, it is a hard problem. A very interesting one, too!

Integer-type problems are horrible and I can imagine the space of BL purchases has lots of local minima separated by the choice of when to buy from one more store. Of course it’s easy when one store simply does not sell the item you need!

Perhaps thinking of this as a version of the multiple knapsack problem may help? The following paper touches on the more general problem, including when profits vary: http://cgi.di.uoa.gr/~vassilis/co/MultipleKP.pdf

Not sure I have any more to say except to reiterate in an almost exasperated fashion that this stuff is hard.

2 hours ago, jxu said:

It doesn't consider Lego's own parts shop which I haven't gotten a chance to use.

Honestly I don’t recommend this because LEGO’s parts are almost invariably more expensive than those on BL, and the selection of pieces is weird as well.

[MAB]

There have been numerous ways of doing it in the past. A BL user atxdad wrote a matlab script to do a minimisation, and it was improved on here:

I haven't a clue how they would fare now.

 

I tend to do a manual approach - find out what the most expensive parts are and find out which shops I can buy those in. Then check what parts they have using a wants list, but only add them if the total price of the lot is less than a rough average price for that lot*0.75 plus typical shipping charges. That is, if I can buy the whole lot of the cheaper part and pay shipping from another store and it is still cheaper than the first store with the expensive part, I'll split that part of the order. The *0.75 is because normally many stores will sell below average. Of course it can be amended if necessary. For example, if the average price of a part is 10p, I want 100 and the seller has them for 20p, I won't buy them even though I might be buying a more expensive part already. I might as well buy that lot of 100 from another store and pay shipping. If you know rough prices and likely quantities that other stores will have it can be reasonably quick to do these calculations.

Another way is to do a completely separate wants list for only the cheap parts, so searches are not biased by the expensive parts.

 

[deraven]

14 hours ago, jimmynick said:

Honestly I don’t recommend this because LEGO’s parts are almost invariably more expensive than those on BL, and the selection of pieces is weird as well.

For what it's worth on this bit specifically, my rule is to do a quick check of the Lego Bricks & Pieces price for anything that I'm buying a larger quantity of unless it's dirt-cheap already on Bricklink (or obviously older stuff that Lego isn't likely to stock).  I've found plenty of things that were surprisingly cheaper from Lego (mostly tiles, recently).  Usually the difference per piece isn't much and if I only need a few of them the convenience of Bricklink and faster turn-around time means I don't care about saving the 50 cents, but when I'm buying a few hundred parts of a few types and brand-new from Lego they're a few cents cheaper per part, plus it qualifies for free shipping, that's worth it to me.

[MAB]

10 hours ago, deraven said:

For what it's worth on this bit specifically, my rule is to do a quick check of the Lego Bricks & Pieces price for anything that I'm buying a larger quantity of unless it's dirt-cheap already on Bricklink (or obviously older stuff that Lego isn't likely to stock).  I've found plenty of things that were surprisingly cheaper from Lego (mostly tiles, recently).  Usually the difference per piece isn't much and if I only need a few of them the convenience of Bricklink and faster turn-around time means I don't care about saving the 50 cents, but when I'm buying a few hundred parts of a few types and brand-new from Lego they're a few cents cheaper per part, plus it qualifies for free shipping, that's worth it to me.

I agree. Especially if the part is small but rare in the colour you want, the BL price might be very high and the B+P price might be low.

[jxu]

Since Bricklink is owned by Lego now, ideally they could include Lego's own store prices, but that would interfere with the whole community seller aspect of it.

The Brick Wizard tool is interesting, but according to its website it is broken ever since the Brick link UI change. That means it probably scraped pages instead of using an API because I don't think BL exposes an API for bulk things like that. For a single user, you can scrape on demand, but in the hypothetical situation for many users it would be more efficient (but less for BL) to be constantly crawling all parts pages and maintaining my own database.

I also skimmed the page and I didn't see any description of the algorithm, and I don't feel like mucking around in Matlab code. The author says each additional store adds exponential time so it is likely an exhaustive search algorithm instead of a more clever but significantly more involved approximation algorithm.

 

Edited October 2, 2020 by jxu

[jimmynick]

On 10/1/2020 at 10:39 AM, MAB said:

I agree. Especially if the part is small but rare in the colour you want, the BL price might be very high and the B+P price might be low.

On 9/30/2020 at 11:46 PM, deraven said:

For what it's worth on this bit specifically

You're both right; it's more subtle than I made it out to be. And sometimes there aren't any BL sellers with nearly enough of the part you want, so it's convenient to buy from PAB.

 

[MAB]

8 hours ago, jxu said:

Since Bricklink is owned by Lego now, ideally they could include Lego's own store prices, but that would interfere with the whole community seller aspect of it.

 

 

LEGO have said that it is not their intention to sell parts on BL.