Mathematical Models and Algorithms for Optimisation of the LEGO Construction Problem

Torkil Kollsker

Research output: Book/ReportPh.D. thesisResearch

Abstract

This thesis develops mathematical models and algorithms for optimisation of the LEGO construction problem. This optimisation framework aims to aid a designer in creating a LEGO construction. The designer defines the shape and colours of an object and selects a set of available LEGO bricks. The optimisation framework then decides the placement of the LEGO bricks such that they combine into a stable LEGO construction that resembles the designed object. The literature on the LEGO construction problem has grown since the first article in 1998. However, it has not yet focused on arranging the LEGO bricks systematically to ensure visually pleasing brick configurations. It has only considered LEGO bricks having the same height even though using various brick heights is essential for creating diverse LEGO constructions. Furthermore, it has not taken into account that some LEGO brick dimensions do not come in all colours. Notably, most methods in the literature rely on having the 1×1 LEGO brick available. This thesis proposes constructive heuristics and mixedinteger linear programming to ensure a systematic and feasible placement of LEGO bricks and plates.

Ensuring the structural integrity of a LEGO construction is paramount. This thesis discusses methods from the literature as well as new methods for quantifying structural integrity. The findings of this thesis show that the most promising method is a static limit analysis used with quadratic programming. Because of very high computation times, this thesis proposes a heuristic that aggregates a selection of variables and constraints to reduce the model size. The results show significant time reductions. The main finding of this thesis is to combine combinatorial optimisation with structural optimisation. The combinatorial part of the problem deals with deciding the placement of the LEGO bricks, and the structural part of the problem deals with distributing the forces between the bricks. While the literature has extensively studied these parts separately, both parts are mutually dependent. This thesis proposes an efficient framework for finding brick
configurations that are in static equilibrium. Due to the relatively fast computations, a practitioner can use this optimisation framework as an interactive tool for designing LEGO constructions. The difficult part of the problem is not to cover the entire construction with LEGO bricks. For most LEGO constructions, many feasible brick configurations exist. Instead, the hardest part is to place the LEGO bricks such that they satisfy the structural integrity and aesthetics of the construction. These quantities complicate the problem in two ways. First, they are computationally expensive and difficult to define, respectively. Second, they depend on the interaction between the bricks. This interdependency amongst the bricks makes it difficult to decompose the problem into smaller and more tangible parts. This thesis uses strategies that are used in practice to ensure both structural integrity and aesthetics. To validate the structural integrity of the LEGO
construction, this thesis uses the static limit analysis. However, this analysis does not account for all external load cases. Future research could improve the approximations of structural integrity and aesthetics.

This thesis mainly focuses on solid LEGO construction. However, hollow constructions are lighter and thus allow for creating more diverse LEGO construction. Future research could incorporate hollowing strategies into the optimisation
framework. While this thesis does not solve the LEGO construction problem, it fills some of the gaps in the literature. Furthermore, it improves the current workflow for creating LEGO constructions.
Original language English
Number of pages 252 Published - 2020

Fingerprint

Dive into the research topics of 'Mathematical Models and Algorithms for Optimisation of the LEGO Construction Problem'. Together they form a unique fingerprint.