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. Fur- ther, 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 con- structions showing the efficacy of the proposed algorithm when compared with two recent approaches from the literature.

Kollsker, T., Malaguti, E. (2021). Models and algorithms for optimising two-dimensional LEGO constructions. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 289(1), 270-284 [10.1016/j.ejor.2020.07.004].

Models and algorithms for optimising two-dimensional LEGO constructions

Malaguti, Enrico
2021

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. Fur- ther, 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 con- structions showing the efficacy of the proposed algorithm when compared with two recent approaches from the literature.
2021
Kollsker, T., Malaguti, E. (2021). Models and algorithms for optimising two-dimensional LEGO constructions. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 289(1), 270-284 [10.1016/j.ejor.2020.07.004].
Kollsker, Torkil; Malaguti, Enrico
File in questo prodotto:
File Dimensione Formato  
OCCA_article 2REV_SUBMITTED.pdf

Open Access dal 08/10/2022

Descrizione: post
Tipo: Postprint
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione - Non commerciale - Non opere derivate (CCBYNCND)
Dimensione 1.95 MB
Formato Adobe PDF
1.95 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/850081
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 3
social impact