Torkil Kollsker vart ph.d. á DTU

Mánadagin 19. oktober vardi Torkil Kollsker ph.d.-ritgerð sína um amboð til at optimera arbeiðið við LEGO konstruktiónum. Heitið á ritgerðini er: ”Mathematical Models and Algorithms for Optimisation of the LEGO Construction Problem”. 

Torkil hevur verið innskrivaður á DTU - Department of Technology, Management and Economics.

Høvuðsvegleiðari var Thomas Jacob Riis Stidsen, lektari, og hjávegleiðari var Mathias Stolpe, professari, báðir á DTU.

Í metingarnevndini vóru:
David Pisinger, professari á DTU
José Fernando Oliveira, professari á Porto University, Portugal
Mattias Schevenels, lektari á KU Leuven, Belgium
Jesper Larsen, professari á DTU leiddi verjuna.

Samandráttur

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 mixed-integer 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.

Mynd: privatmynd