Mark Bouwman: Algorithms for Cheaper LEGO

Event Details

Besides the official LEGO sets there are many fan-created designs online. To build these custom designs you need to buy individual parts online. Concentrated on two larger platforms there are thousands of stores offering parts. An interesting optimisation problem arises: which distribution of parts over the stores is the cheapest, also considering shipping costs? In the literature this is known as the Internet Shopping Optimisation Problem (ISOP). In this talk I will present ISOP, a proof that it is NP-Hard and a range of algorithms for obtaining (near) optimal solutions. Additionally, I will present my own algorithm, which combines a number of techniques, and show that it is effective in finding cheap stores for buying LEGO.