Models and algorithms for optimising two-dimensional LEGO constructions

Torkil Kollsker, Enrico Malaguti*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

The LEGO Construction Problem is the problem of deciding which bricks to place where in a predefined LEGO construction. The input consists of coloured voxels that each correspond to the size of a LEGO unit, such that all LEGO bricks are multiples of this LEGO unit. A solution to the LEGO Construction Problem is feasible if all bricks are within the design domain, the bricks do not overlap, the bricks satisfy the colour constraints, and all bricks connect into a stable construction. In this article, we propose an automated approach for optimising LEGO constructions, and in particular, we focus on 2D constructions. We introduce mathematical programming formulations of the problem as well as a fast constructive heuristic algorithm that is very efficient for constructing regular walls. Further, we integrate the models and the heuristic into a matheuristic algorithm, where the heuristic algorithm defines most of the construction, in particular, large elements that require regular patterns, while the mathematical models are used to tackle critical parts of the construction and to ensure the overall stability of the result. The article concludes with computational experiments on regular and irregular constructions showing the efficacy of the proposed algorithm when compared with two recent approaches from the literature.
Original languageEnglish
JournalEuropean Journal of Operational Research
Volume289
Issue number1
Pages (from-to)270-284
ISSN0377-2217
DOIs
Publication statusPublished - 2020

Keywords

  • Cutting
  • LEGO construction problem
  • Mathematical models
  • Matheuristic
  • Structural integrity

Fingerprint Dive into the research topics of 'Models and algorithms for optimising two-dimensional LEGO constructions'. Together they form a unique fingerprint.

Cite this